Лекция 2
Контейнеры и шаблоны
Шаблоны C++ в отличие от функций, которые позволяют многократного использовать объектный код, предоставляют возможность заново использовать исходные тексты. Шаблоны принадлежат к числу инструментов программирования общего назначения.
В С++ имеется Стандартная Библиотека Шаблонов (STL), которая включает в себя библиотеку шаблонов контейнерных классов.
Контейнер – это объект, который предназначен для хранения других объектов.
Контейнеры
Потребность в контейнерах по-настоящему возникает при создании объектов в динамической памяти (куче) оператором new и их уничтожении оператором delete. В общем случае во время написания программы неизвестно, сколько объектов вам потребуется. Например, информационная система программируется так, чтобы поддерживать множество объектов, но только пользователь (во время выполнения программы) определяет, какие и сколько объектов ему понадобится.
Альтернативное решение, которое использовалось в языке С, – это работа с огромным глобальным массивом объектов.
В C++ выбран другой подход: когда вам потребуется объект, вы создаете его при помощи оператора new и сохраняете указатель в контейнере. Затем указатель извлекается из контейнера, и программа делает с ним что-нибудь полезное. В этом случае создаются только те объекты, которые действительно используются в программе. Итак, в типичной ситуации контейнер содержит указатели на объекты.
Программа создает объекты при помощи оператора new, сохраняет полученные указатели в контейнере и извлекает их позднее, когда с объектом нужно выполнить операцию. Этот подход позволяет создавать наиболее гибкие и универсальные программы.
Общие сведения о шаблонах
А теперь о проблеме. Предположим, что мы создали контейнер IntArray, в котором хранятся целые числа; но нам может потребоваться массив для хранения геометрических фигур, самолетов, растений или еще чего-нибудь. Каждый раз переделывать исходные тексты? Вряд ли это можно назвать разумным решением, тем более в языке, ориентированном на многократное использование кода. В данной ситуации в C++ удобно использовать шаблоны.
Шаблоны – это средство языка C++, предназначенное для кодирования обобщённых алгоритмов, без привязки к некоторым параметрам (например, типам данных, размерам буферов, значениям по умолчанию). Шаблоны C++ позволяют определить семейство функций или классов, которые могут работать с различными типами данных.
Синтаксис шаблонов
Ключевое слово template сообщает компилятору, что в следующем определении класса используется один или несколько заранее неизвестных типов. В тот момент, когда компилятор генерирует код класса на основании шаблона, эти типы должны быть известны, чтобы компилятор мог подставить их на место параметров шаблона.
Для демонстрации синтаксиса рассмотрим небольшой пример, в котором создается массив с автоматической проверкой границ:
//L2:TemplateArray.срр
#include <iostream>
#include <iomanip>
using namespace std;
template<class T, int size=20>
class Array {
T Arr[size]; //значение size не хранится внутри класса,
//но все функции класса могут использовать его // как целочисленную константу.
public:
T& operator[](int index);//перегрузка оператора индексации
};
//Определение функции (вне определения класса)
template<class T, int size>
T& Array<T,size>::operator[](int index) {
if(index >= 0 && index < size)
return Arr[index];
cout<<"Index out of range"<<endl;
system("pause");
exit(-1);
}
int main() {
Array<int> iArr;
Array<float,15> fArr;
for(int i = 0; i < 10; i++) {
iArr[i] = i * i;
fArr[i] = float(i) * 1.5;
}
for(int j = 0; j < 10; j++)
cout <<setw(3)<< j << ": "<<setw(3) << iArr[j]
<< "; " <<setw(5)<< fArr[j] << endl;
system("pause");
}
Аргументы шаблонов не ограничиваются классами; в них также можно передавать встроенные в С++ типы. Значения этих аргументов превращаются в константы времени компиляции для указанного экземпляра шаблона. Таким аргументам даже можно присваивать значения по умолчанию (int size=20).
Класс Array выглядит вполне обычно, если не считать строку
template<class Т>
Эта строка сообщает, что Т является подставляемым параметром, который отражает имя типа. Внутри класса идентификатор Т используется везде, где обычно указывается конкретный тип, хранимый в контейнере.
В Array присваивание и выборка элементов осуществляются одной функцией — перегруженной операторной функцией operator[ ]. Оператор возвращает ссылку (адрес переменной), поэтому результат может находиться по обе стороны от оператора присваивания (то есть быть как l-value и как r- value значением). Если индекс выходит за границы массива, класс выводит сообщение об ошибке.
Функция main() показывает, как легко создаются контейнеры Array для хранения объектов различных типов. Встречая следующие определения, компилятор дважды расширяет шаблон (также говорят: создает экземпляр шаблона) Array и создает два новых сгенерированных класса, которые можно условно обозначить Array_int и Array_float. Разные компиляторы используют разные схемы формирования имен, но имена должны быть различными. Они не видимы для программиста. Объявление массива в программе с использованием шаблона выглядит следующим образом:
Array<int> iArr;
Array<float> fArr;
Эти классы работают точно так же, как при ручной подстановке типов, если не считать того, что они автоматически создаются компилятором при определении объектов iArr и fArr. Повторяющиеся определения классов обходятся компилятором.
Следует иметь в виду, что все функции-члены шаблона класса также должны быть шаблонами функций. Это требование накладывает на функции определенные ограничения. Например, используемые в функции операторы должны быть определены для всех типов данных, которые являются параметрами шаблона.
Заголовочные файлы
Все объявления и определения, относящиеся к шаблону, лучше разместить в заголовочном файле. На первый взгляд кажется, что это противоречит стандартному правилу «Не размещай в заголовочных файлах ничего, что связано с выделением памяти» (из-за ошибок повторного определения на стадии компиляции), однако определения шаблонов занимают особое место. Любая конструкция с префиксом template<...> означает, что компилятор не выделяет память немедленно, а ждет специального распоряжения (то есть создания экземпляра шаблона), при этом в компиляторе и компоновщике реализован механизм исключения множественных определений идентичного шаблона. По этой причине в заголовочный файл почти всегда включаются полные объявление и определение шаблона (это делается для простоты использования).
Некоторые программисты считают, что вынесение всего исходного текста реализации в заголовочный файл нежелательно, поскольку дает возможность изменять (или просто красть) их программный код после покупки библиотеки. Такие опасения имеют основания, но здесь стоит спросить себя: что именно вы продаете, продукт или услугу? Если продукт, то вам следует приложить все усилия к его защите; вероятно, не стоит распространять исходные тексты, а лишь откомпилированный код. Но многие клиенты рассматривают программы как услугу, даже более того, как подписку на услугу. Он предпочитает, чтобы вы сами сопровождали свою программу, а он будет использовать ее в своей работе.
Знакомство с итераторами
Итератором называется объект, который позволяет перебирать содержимое контейнера и в любой момент времени указывает на один из его элементов. Итераторы обеспечивают стандартный механизм обращения к элементам независимо от того, поддерживает ли контейнер прямой доступ к элементам. Итераторы чаще всего используются с контейнерными классами, они занимают важное место в архитектуре стандартных контейнеров C++ и их практическом применении.
Во многих отношениях итератор может рассматриваться как «умный» указатель. И действительно, итераторы поддерживают многие операции, характерные для указателей. Но в отличие от указателей, при проектировании итераторов особое значение придавалось вопросам безопасности, поэтому неприятности типа выхода за пределы массива с ними случаются гораздо реже (а если и случаются, то выявляются гораздо быстрее).
Хотя на первый взгляд перебор сводится к простому «увеличению указателя», на самом деле выполняются более сложные действия. В этом заключается ключевая особенность итераторов: они абстрагируют сложный процесс перемещения между элементами контейнера в нечто, напоминающее простой указатель.
Стандартная библиотека предоставляет различные типобезопасные контейнеры для хранения коллекций связанных объектов. Контейнеры — это шаблоны классов. При объявлении переменной контейнера указывается тип элементов, которые будет содержать контейнер. Контейнеры могут создаваться с использованием списков инициализаторов. Они содержат функции-члены для добавления и удаления элементов и выполнения других операций.
Перебор элементов в контейнере и доступ к отдельным элементам выполняется с помощью итераторов.
Итераторы для всех контейнеров STL имеют общий интерфейс, но каждый контейнер дополнительно может иметь собственные специализированные итераторы. Рассмотрим последовательный контейнер vector и ассоциативный контейнер map.