Шаблоны типов

В предыдущей части был задан вопрос: как найти длину массива, не зная заранее какого типа будут его отдельные элементы? Если рассматривать возможные варианты реализации этого в С++, ответа на вопрос будет как минимум два. Но один из них очень специфичен. Предполагая что длина массива, в первую очередь, нужна для поэлементного поиска в массиве с помощью цикла (чтобы знать, где массив заканчивается), есть встроенный в компилятор способ.


int arr[15] {0};
for (auto i : arr) {}

Такая конструкция цикла называется for-each, и особенность ее в том, что она сама определяет длину переданного контейнера, если он отвечает определенным требованиям. В примере выше массив был объявлен как статический, поэтому его размер известен компилятору, соответственно цикл может определить где массив заканчивается, исходя из заданного размера с помощью арифметики указателей. Особое внимание стоит обратить на ключевое слово auto, которое автоматически определяет тип каждого отдельного элемента массива. Оно является частью реализации выявления типов в С++, что делается с помощью шаблонов типов данных[1].

Чтобы четко себе представить, как работает выявление типов в С++, следует разобраться с “шаблонами”, которые выполняют роль переменных типов. Рассмотрим пример объявления функции:


template <typename T> unsigned int length(const T (&a)[15]);

Здесь встречается три новых синтаксических элемента. Ключевое слово template обозначает начало определения шаблона. В самом общем смысле шаблоны являются отдельными сущностями и делятся на несколько категорий: шаблоны классов, шаблоны функций, шаблоны переменных и т.п. Сами по себе шаблоны никаких операций совершать не могут, компилятор генерирует для них код тогда, когда шаблон инициализируется. В примере выше создается шаблон функции length, который имеет свой список аргументов в угловых скобках. Параметр у этого шаблона всего один – переменная T, которая принимает типы данных в качестве аргумента, что подчеркивается ключевым словом typename. Эта переменная T затем используется в списке аргументов самой функции для обозначения того, что аргумент функции будет такого типа, который передан в качестве аргумента шаблона. Например, для массива int arr[15] {0} вызов выглядел бы так:


unsigned int l = length<int>(arr);
// или 
unsigned int l = length(arr);

Соответственно, массив мог бы содержать элементы любого типа, и компилятор бы позволил определить тип уже в ходе работы программы. Но можно пойти еще дальше. Было бы хорошо, если бы компилятор позволял передавать в эту функцию массивы любой длины, а не заранее заданной в определении функции. Шаблоны позволяют сделать и это.


template <typename T, unsigned int N> unsigned int length(const T (&a)[N]);

Здесь стоит отметить второй параметр в списке аргументов шаблона - имя N, которое должно быть целым беззнаковым числом. Объявив его появляется возможность использовать переменную N в качестве размера массива a – аргумента функции. Полностью функция могла бы выглядеть так.


template <typename T, unsigned N>
unsigned int length(const T (&a)[N])
{
    unsigned int i = 0;
    for (; i < N; ++i);
    return i;
}

Синтаксис стал заметно сложнее для восприятия. Но в определенных ситуациях оно того стоит. Во-первых, это позволяет создавать полностью полиморфные функции без использования наследования. Во-вторых это позволяет изменять тип аргумента в будущем без необходимости изменять саму функцию или все ее вызовы, которые уже есть в программе.

Шаблоны классов устроены по похожему принципу. Сначала рассмотрим их применение на примере одного из самых востребованных классов в С++. В пространстве имен std содержится список различных ключевых слов и типов данных, которые содержатся в различных стандартных библиотеках, которые поставляются вместе с компилятором. Одна из таких библиотек – vector – представляет собой реализацию динамического массива. Как можно догадаться из названия, это альтернатива массивам из языка С, которые создаются на стеке и не изменяют своего размера в ходе работы программы. В отличие от них вектор может “расти” или “уменьшаться” в зависимости от контекста.


#include <vector>

std::vector<int> a;
std::vector<float> b(10);
std::vector<char> c({1, 3, 5});

Вектор реализует большое количество конструкторов. Выше показаны три разных способа инициализировать объект-вектор: с помощью конструктора по умолчанию, конструктора с параметром типа int и конструктора с параметром типа char[]. В первом случае вектор останется пустым, но в дальнейшем будет принимать только значения типа int. Во втором случае вектор будет инициализирован массивом из 10 значений типа float. В третьем случае вектор будет инициализирован массивом из трех значений типа char, переданных в виде списка инициализации.

Все три объекта обладают несколькими свойствами, которые либо реализованы как свободно доступные методы, либо активизируются в определенных ситуациях автоматически. Например, получить доступ к элементу вектора можно как минимум тремя способами. Первый способ заимствован из языка С – квадратные скобки с индексом нужного элемента, начиная с нуля, например, c[0] – вернет 1. Если элемента по такому индексу не существует, программа прервет свою работу. Второй способ представлен методом at, который также принимает индекс элемента, например, c.at(0) – вернет 1. Если элемента по такому индексу не существует, метод вызовет исключение^*, что также может прервать работу программы. Третий способ связан с использованием указателей на элементы вектора. Вектор не позволяет использовать прямые указатели, взамен предоставляя методы, которые возвращают итераторы на начало или конец вектора: begin и end[2]. Так, инструкция c.end() вернет объект-итератор, который ведет себя как указатель на первый байт за пределами вектора. Например, *c.begin() вернет 1, а *(c.end() - 1) вернет 5.


for(int i = 0; i < c.size(); ++i) c[i];

for(auto i = b.begin(); i != b.end(); ++i) *i;

for(auto i : a) i;

Пример всех трех способов показан выше. В первом случае используется привычный вид цикла for, который генерирует индексы для последующего доступа к нужным элементам. Метод size используется для точного определения текущего размера вектора. Второй способ получает итератор на первый элемент и с помощью оператора инкремента передвигает итератор до последнего элемента (находящегося непосредственно перед байтом итератора b.end()). Третий вариант использует уже знакомую вам форму цикла for-each, которая позволяет в более краткой форме получить доступ к значению элемента вектора.

Чтобы добавить новый элемент в вектор можно использовать несколько методов. Самый простой в использовании – push_back – добавляет заданный элемент в конец вектора. Метод insert добавляет заданный элемент по заданной позиции в векторе (указывается с помощью действительного итератора этого вектора). Аналогично можно удалять элементы из вектора, методами pop_back и erase соответственно.


a.push_back(1);         // {1}
a.insert(a.begin(), 2); // {2, 1}
a.pop_back();           // {2}
a.erase(a.begin());     // {}

Выше показаны примеры использования этих методов. Первая инструкция добавит в пустой вектор значение “1”; вторая инструкция вставит в начало вектора значение “2”, “подвинув” единицу на вторую позицию (вектор будет иметь вид {2, 1}); третья инструкция удалит последний элемент (1) из вектора; наконец, последняя инструкция удалит первый элемент (2) из вектора, и он снова станет пустым.

Если посмотреть на то, как класс std::vector объявлен в заголовочном файле своей библиотеки, некоторые элементы могут вызвать особый интерес.


template <typename _Tp, typename _Alloc = std::allocator<_Tp>> class vector : protected _Vector_base<_Tp, _Alloc>

Как и ожидалось, вектор объявлен как шаблон, причем список аргументов шаблона включает в себя другой шаблон – необязательный параметр _Alloc, который определяет способ выделения памяти для нужд вектора. Вектор не является базовым классом, а наследует часть своих свойств от другого шаблона класса _Vector_base. Исходя из этого описания можно попробовать написать наивную реализацию вектора самостоятельно.

Пока что не стоит обращать внимание на параметр “аллокатор” и просто его игнорировать. Выделение памяти для работы структуры полностью зависит от выбранной стратегии работы с памятью, и она не обязательно должна включать в себя работу с “кучей”. Также нет необходимости наследовать базовый класс из стандартной библиотеки, так как вы не знакомы с деталями его реализации. Исходя из этого ваша реализация вектора могла бы выглядеть примерно так.


template <typename T> struct vector
{
    vector() {}
    template <unsigned int N> vector(const T (&list)[N]) : length((N < 100) ? N : 100)
    {
        for (unsigned int i = 0; i < this->length; ++i)
        {
            this->arr[i] = list[i];
        }
    }
    vector(const unsigned int N) : length((N < 100) ? N : 100) {}
    unsigned int size() { return length; }
    T *begin() { return this->arr; }
    T *end() { return this->arr + this->length; }
private:
    T arr[100]{0};
    unsigned int length{0};
};

Выше показан вариант, который повторяет три способа инициализации вектора, рассмотренных ранее, а также методы begin, end, size – для использования в циклах. В качестве основного механизма вектора выступает массив на 100 значений заданного типа. В качестве итераторов используются указатели на массив. Конструкторы проверяют переданные аргументы для того, чтобы убедиться, что их значения не позволят массиву стать размером больше 100 элементов. Таким образом, становится возможным следующий фрагмент:


vector<int> my_vec({10, 20, 30});
for (auto i : my_vec) printf("%d ", i);

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

Упражнения

Векторы, которые включены в стандартную библиотеку С++, используют “кучу” для увеличения своих размеров при добавлении новых элементов. Стратегия выделения памяти для вектора зависит от конкретного компилятора, но самая распространенная такая стратегия заключается в предварительном выделении памяти “про запас” для того, чтобы не обращаться к куче каждую операцию. Поэтому когда мы говорим о размерах вектора, надо иметь в виду и количество элементов (size), и занимаемую вектором память (capacity).

Так, если вектор пустой, при первом добавлении нового элемента в вектор будет выделено достаточно памяти для одного элемента (size – 1, capacity – 1). При следующей операции добавления элемента в вектор, будет выделено в два раза больше памяти (size – 2, capacity – 2). Соответственно, третья операция удвоит вместимость вектора еще раз ((size – 3, capacity – 4)). Уже четвертая операция не будет нуждаться в дополнительной памяти и т.д. Аналогично работает освобождение памяти; если реальными данными занята только половина доступной вектору памяти, все элементы вектора будут перенесены в сжатую область памяти, где он будет занимать меньше места.

Подумайте как это можно реализовать. Все инструменты, нужные для этого, вам уже знакомы. Главное, что нужно понимать – это механизм увеличения вектора за счет изменения того, куда указывает адрес первого элемента вектора. Другими словами, если вектор надо увеличить или уменьшить, сначала создается новый блок памяти нужного типа, затем туда переносятся все элементы вектора, после чего старый блок памяти освобождается за ненадобностью.

Стоит обратить внимание на вызов операторов new и delete, которые используют квадратные скобки. Если в случае с new это нужно для указания точного размера новой области памяти, то для delete это является “наследственным дефектом” и частенько приводит к ошибкам в программах новичков, которые забывают дописать пустые квадратные скобки при освобождении массива.

Не хватает нескольких важных элементов, ожидаемых от любого массива: оператора прямого доступа (operator[]) и оператора присваивания (operator=). Если тело первого сделать достаточно просто (return this->arr[N]; для любого положительного N, не выходящего за пределы массива arr), то со вторым придется немного повозиться. Есть соблазн просто повторить семантику конструктора копирования, но это было бы ошибкой, так как оператор присваивания вызывается после конструирования объекта, а значит должен исходить из предположения, что в объекте уже могут быть действительные значения. Исключением является случай, когда вектор слева от оператора присваивания по длине совпадает с вектором справа. Тогда достаточно выполнить поэлементное копирование из одного вектора в другой. Попробуйте написать эти два оператора самостоятельно и тщательно проверьте правильность их работы. Например, убедитесь, что оператор доступа может быть как слева, так и справа от оператора присваивания.


vector<int> my_vec({10, 20, 30});
int x = my_vec[1];
my_vec[0] = 100;

Сноски

^*Исключение (exception, англ.) – лингвистический механизм, который служит для взаимодействия процедур внутри программы, в первую очередь, при возникновении ошибок в логике программы.

Источники

“Placeholder type specifiers”, Declarations, C++ language, cppreference.com
Итератор (iterator, англ.) – специальный объект, который указывает на отдельный элемент из списка элементов; итератор также может переходить от одного элемента к другому на произвольную дистанцию, используя специальные операторы; в С++ указатели обладают всеми свойствами итератора и полностью аналогичны по своей функциональности итераторам случайного доступа; “Iterator library”, C++ language, cppreference.com