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

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


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

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

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


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

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


size_t l = length<int>(arr);

// или так:
size_t l = length(arr);

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


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

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


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

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

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


std::vector<int> a;
std::vector<float> b(10);
std::vector<char> c({‘e’, ‘g’, ‘i’});

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

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


for(size_t 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, которая позволяет в более краткой форме получить доступ к значению элемента вектора.

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


template <typename _Tp, typename _Alloc = std::allocator<_Tp>>
class vector : protected _Vector_base<_Tp, _Alloc> { ... };

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

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


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

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


vector<int> my_vec({10, 20, 30});
for(auto i : my_vec) std::cout << i;

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

Упражнения

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

Например, вы уже должны быть знакомы с тем, как реализуются односвязные списки. В отличие от массивов односвязный список не хранит все свои элементы в соседних блоках памяти, поэтому указатель на каждый последующий элемент нужно хранить вместо того, чтобы арифметически расчитывать его позицию, как это делается для массивов. То есть, для односвязного списка реализация методов begin и end через обычные указатели, ничего бы не дала, так как циклы for и for-each используют инкрементирование указателей для перебора элементов контейнера. Это значит, что для такого списка недостаточно сделать методы begin и end, а нужно также перегрузить операторы инкремента, декремента, сложения, вычитания и сравнения указателей. Для самих указателей это сделать крайне сложно, поэтому стоит прибегнуть к стандартному способу решения похожей проблемы: внутри контейнера создать новый тип данных, который ведет себя как указатель, определить для него все вышеперечисленные операции и возвращать методами begin и end объекты этого типа, а не чистые указатели. Попробуйте реализовать такой класс самостоятельно.

Сноски

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

²Итератор (iterator, англ.) – специальный объект, который указывает на отдельный элемент из списка элементов; итератор также может переходить от одного элемента к другому на произвольную дистанцию, используя специальные операторы; в С++ указатели обладают всеми свойствами итератора и полностью аналогичны по своей функциональности итераторам случайного доступа [CPP(e)].