Лекция 8

Линейный односвязный список в динамической памяти

Воспользуемся для создания линейного списка шаблон структурой node из 7 лекции:

template<typename T>
struct node
{
    T data;
    node<T>* next;

    node(T data, node<T>* next)
    {
        // this указатель на себя
        this->data = data;
        this->next = next;
    }
};

При объявлении нового экземпляра структуры node, как это описано в предыдущей лекции, этот объект создается в статической памяти. То есть объект n1 будет храниться на стеке:

node<int> n1(5, nullptr);

В реальных программах, ввиду сильной ограниченности размера стека, объекты размещают в динамической памяти.

Как создать node в динамической памяти

node<int>* pn = new node<int>(5, nullptr);

В C++ динамическую память выделяет не конструктор, а оператор new. Конструктор только создает объект в выделенной памяти.

В отличии от .NET в C++ нет сборщика мусора, и ответственным за удаление объекта из динамической памяти, является программист.

В C++ размерная модель объектов, а ссылочную можно моделировать с помощью указателей.

Добавление элемента в начало односвязного списка

node<int>* pn = nullptr;
pn = new node<int>(5, pn);

Операцию добавления первого элемента в односвязный список мы оформим в виде отдельной функции. Создадим шаблон такой функции.

tempate <typename T>
void add_first(node<T>* &pn, T x)
{
    pn = new node<T>(x, pn);
}

Запись node<T>* &pn означает, что pn это ссылка на указатель типа node<T>, и изменения происходящие с ней внутри фунцкии повлияют и на изменение фактического параметра.

node<int>* pn = nullptr;

add_first(pn, 5);
add_first(pn, 3);
...

Создание односвязного списка

Надо обратить внимание на то, что в отличии от шаблона структуры, в шаблоне функции указывать тип не надо, он автоматически выводится по типам фактических параметров.

Где хранить шаблоны функций, структур и классов.

В результате компиляции шаблона генерируется 0 байт, поскольку конкретный тип не указан. Если описать шаблон функции в одном *.cpp файле, то при многофайловой компоновке программы эта функция не будет доступна в другом файле.

Решение. Все шаблоны функций, классов и структур должны быть помещены в заголовочные файлы.

Для шаблонов функций конкретный код генерируется при вызове функции, когда становится известен конкретный тип Т. Подстановка конкретного типа в шаблон называется инстанцированием шаблона. Количество инстанций зависит от количества используемых типов.

В C++ шаблоны компилируются в два этапа:

Компиляция собствено шаблона
Компиляция шаблона инстанцированного конкретным типом.

И на каждом этапе могут возникнуть ошибки.

Отличие шаблонов C++ от обобщений .NET

В С++ компиляция шаблонов проходит в два этапа, а в .NET обобщения компилируются 1 раз.
В С++ в результате компиляции шаблона получается исполняемый код инстанцированных функций, структур и классов. В .NET в результате компиляции обобщения создается исполняемый код самого обобщения т.е в .NET можно создать dll с обобщенным классом.

template<typename T>
T inc(T t)
{
    return t + 1;
}

В C++ разрешаются все действия с типом T, а в .NET и Java запрещаются все действия которые явно не разрешены (разрешения делаются в where).

Student s(...);
inc(s);  // В C++ произойдет ошибка на этапе компиляции
         // А в динамических языках это ошибка времени исполнения

Цикл по односвязному списку

template <typename T>
void print(node<T>* p)
{
    while(p)
    {
        cout << p -> data << ' ';
        p = p -> next;
    }
}

Указатели на функции

В PascalABC.NET работа с указателями на функции осуществляется следующим образом:

type BitOp = function (a, b: real): real;

var op: BinOp;
write(op(3, 5));
op := mult;
write(op(3, 5));

Аналогичный код на C++ выглядит так:

// Указатель на функцию с таким прототипом
typedef double (*BinOp) (double, double);

BinOp bop = &add;
(*bop)(3, 5);


// Или как и описание переменной
double (*op)(double, double)

op = mult;
op(3, 5);    // Так тоже можно вызывать template <typename T>

Действие передаваемое параметром (callback)

template <typename T>
// action — переменная типа "указатель на функцию"
void for_each(node<T>* p, void (*action)(T&))
{
    while(p)
    {
        action(p -> data);
        p = p -> next;
    }
}

void print(int &x)
{
    cout << x << ' ';
}

void inc(int &x)
{
    x++;
}

for_each(pn, print);
for_each(pn, inc);
for_each(pn, print);

В языке C/C++ структурная эквивалентность типов, а не именная.