6. Шаблоны функций и классов. Библиотека стандартных шаблонов (STL) (Семинары)

Кафедра Компьютерных методов физики: программирование, первый курс, второй семестрЯзык программирования Си++Иванов А.П., Князева О.С.Семинар 6. Шаблоны функций и классов. Библиотекастандартных шаблонов (STL).1. Шаблоны функцийЧасто бывают ситуации, когда один и тот же алгоритм надо оформить в виде несколькихразличных функций: в зависимости от типа данных, который этот алгоритм долженобрабатывать. Очевидный пример: функция сортировки – алгоритм сортировки опираетсянадвефундаментальныеоперации:сравненияэлементовсортируемойпоследовательности и их перестановки (присваивания). Если эти две операцииопределены для сортируемого типа данных – то алгоритм сортировки записывается в ихтерминах универсально:template <class T> void sort ( T arr[], int size ){for (int i = 0; i < size; i++ ){for (int k = i+1; k < size; k++ ){if ( arr[k] < arr[i] ) {T tmp(arr[i]);arr[i]= arr[k];arr[k]= tmp;}}}}Здесь нам от неизвестного заранее класса T понадобится только наличие копирующегоконструктора (для tmp), оператора «меньше» и оператора присваивания.Для целых и вещественных чисел с этими методами нет никаких проблем, ониопределены, поэтому мы можем сразу воспользоваться этим алгоритмом сортировки дляданных видов чисел:.........int iarr[10] = { 8, 1, 3, 4, 9, 0, 2, 7, 6, 5 };sort( iarr, sizeof(iarr)/sizeof(iarr[0]) );.........double darr[10] = { 8.1, 1.2, 3.3, 4.9, 9.5, 0.4, 2.6, 7.7, 6.8, 5.0 };sort<double>( darr, sizeof(darr)/sizeof(darr[0]) );.........Приведенные варианты записи параметра шаблона равнозначны – в первом случае онвыводится из типа первого аргумента, во втором – указан явно.

Приведенные фрагментыпрограммного кода называются инстанцированием шаблона: соответствующая функциягенерируется из описания шаблона в тот момент, когда компилятор встречает в программессылку на функцию с конкретными параметрами.07.11.20111Кафедра Компьютерных методов физики: программирование, первый курс, второй семестрПараметров в шаблоне может быть несколько, причем некоторые из них могут быть нетипами, а константами произвольного типа:template <class T, int defsize>void sort ( T arr[], int size = defsize ){..................}Для строк операторы присваивания и сравнения придется определить дополнительно,однако, чтобы не «затоптать» операторы присваивания и сравнения для указателей char*(ведь именно они представляют строки в языке Си), то для строк лучше объявить свойсобственный строковый класс, например, на основе вектора для типа char и уже внутриэтого класса – определить операторы «<» и «=».2.

Шаблоны классовАналогичным образом можно создавать классы, параметризованные типами иликонстантами, например, вектор из ранее приведенного примера:template <class T, int defsize=0> class Vector{protected:T *v;int len;public://==========Конструкторы объектов класса======//// КонструкторVector(int N = defsize) : v(0), len(0){ if (N>0) v = new T[N];if (v) len = N;}.............};Обратите внимание на возможность задания параметров по умолчанию для аргументовшаблона класса, аналогично тому, как это может быть сделано для значений поумолчанию аргументов обычных функций.Теперь мы можем создавать вектора любого типа:Vector<double> dv(100);Vector<char> dv(10);Vector<char*> dv(20);Шаблоны можно и нужно помещать в заголовочные файлы, однако, реализации методовшаблонных классов должны помещаться в этом же заголовочном файле, нельзя разделятьописание класса и реализацию его методов, как это делается при написании обычныхклассов.3. Библиотека стандартных шаблонов (STL)Стандарт языка Си++ включает в себя описание библиотеки стандартных шаблонов(Standard template library, STL), которая включает в себя определения наиболее часто07.11.20112Кафедра Компьютерных методов физики: программирование, первый курс, второй семеструпотребляемых контейнеров (таких, как vector), алгоритмов (например, алгоритмсортировки), которые работают с любыми из этих контейнеров при помощи итераторов(которые являются обобщением понятия «указатель»).Контейнеры, итераторы и алгоритмыКонтейнеры хранят данные, итераторы позволяют адресовать хранимые в контейнерахданные, а алгоритмы (набор из множества шаблонных функций, определенных взаголовочном файле <algorithm>) позволяют при помощи итераторов произвестимассу различных действий с любыми контейнерами: сортировки, поиска и т.п.Кроме шаблонных функций заголовочный файл <algorithm> содержит массуопределений, так называемых функторов: это шаблонные классы, которые, однако, могутвести себя как шаблонные функции за счет того, что в них переопределен operator().Динамический массивДинамический массив позволяет сохранить элементы любого типа в непрерывном участкепамяти и адресоваться к этим элементам по целочисленному индексу.Взятие элемента по индексу занимает константное время, поиск элемента по значению –линейное (по размеру массива) время, вставка нового элемента в середину массива (иудаление элемента из середины) тоже занимает линейное время, а вот добавление новогоэлемента в конец массива (или удаление последнего элемента) в подавляющембольшинстве случаев занимает константное время и лишь изредка – линейное (за счетхранения запаса аллоцированных, но не инициализированных элементов).#include <iostream>#include <vector>................vector<char> v(100);v.resize(4);v[0] = 'a'; v[1] = 'b';v[2] = 'c'; v[3] = '\0';cout << &v[0] << endl << flush;v[3] = 'd';v.push_back('e'); v.push_back('f');v.push_back('\0');cout << &v[0] << endl << flush;v.erase(v.begin()+2, v.begin()+4);v.insert(v.begin()+4, 'g');cout << "size=" << v.size() << ": \"" << &v[0] << "\"" << endl << flush;ДекаДека, в отличие от массива, позволяет вставлять элементы за константное время не тольков конец, но и в начало:#include <deque>................deque<double> d(10);d.push_front(3.14159);07.11.20113Кафедра Компьютерных методов физики: программирование, первый курс, второй семестрВ остальном дека практически идентична массиву.

Как правило, деки используются дляорганизации разного рода очередей.Константное время вставки в начало может быть достигнуто, например, сохранениемнеинициализированного «запаса» не только в хвосте массива, но и в его начале. Реальноеустройство деки гораздо сложнее, но для минимальной реализации достаточно вектораэлементов с указаниями: где в нем начинается инициализированная часть и где этаинициализированная часть заканчивается.СписокДвусвязный список представляет из себя структуру данных, которая помимо хранимогоэлемента заданного типа хранит еще два указателя: на предыдущий и последующийэлементы:struct mylist {mytype x;mylist *prev, *next;};Такая конструкция позволяет вставлять (и удалять) элементы в произвольном местеконтейнера за константное время (все операции сводятся к замене значений несколькихуказателей). Поиск элемента по значению занимает линейное время, доступ к i-тому попорядку элементу – тоже линейное время (в отличие от вектора или деки).

К тому же, накаждый элемент приходятся немалые накладные расходы: представим себе, чтоэлементом списка является символ (один байт), в то же время, для хранения двухуказателей мы вынуждены в каждом элементе выделять еще, минимум, 8 байт.#include <list>................list<const char*> l(10);list<const char*>::iterator it;for( it = l.begin(); it != l.end(); it++ ) {*it = "abc";}l.insert((l.begin()++)++,"def");Операция вставки выполняется за константное время (т.е.

не зависит от количестваэлементов в списке), однако, операция позиционирования на два элемента вперед, как мывидим, будет линейной, т.е. нам физически придется отсчитать все начальные элементыпо очереди, для того, чтобы получить итератор для точки вставки.МножествоМножество (set) позволяет быстро находить хранимые элементы по их значению.«Быстро» означает – не за линейное, а за логарифмическое (по размеру контейнера) время.В предположении, что все хранимые элементы множества (будем называть их ключами)уникальны – можно построить простейшую реализацию множества при помощиотсортированного массива, в котором поиск производится методом дихотомии (деленияпополам).В настоящей реализации множества используется сбалансированное двоичное деревопоиска, в котором в каждом узле, помимо самого хранимого элемента нужного типа,07.11.20114Кафедра Компьютерных методов физики: программирование, первый курс, второй семестрсохраняются еще два указателя: на левое и правое поддеревья.

При этом все ключи,расположенные в левом поддереве данного узла обязаны быть строго меньше ключа,хранимого в текущем узле, а все ключи, расположенные в правом поддереве обязаны бытьстрого больше него.Вставка и удаление элементов в такое дерево занимают тоже логарифмическое время.#include <set>..............set<double> s;s.insert(10.0);..............set<double>::const_iterator sit = s.find(2.71828);multiset<double> ms;ms.insert(10.0);..............multiset<double>::const_iterator msbegin = ms.lower_bound(2.71828);multiset<double>::const_iterator msend= ms.upper_bound(2.71828);multiset отличается от set только тем, что оно допускает хранение произвольногоколичества равных ключей.

Поиск в таком мультимножестве выдает не один итераторнайденного элемента, а пару итераторов, первый из которых указывает на началоподпоследовательности, содержащую ключи, равные заданному, а второй итератор –указывает «за последний элемент» этой подпоследовательности.Ассоциативный контейнерАссоциативный контейнер устроен практически так же, как и множество, однако, каждыйего элемент содержит пару ключ-значение (а не только ключ), то есть, устанавливаетассоциативную связь от ключа к некоторому значению. Ключ и значение могут бытьразными типами и поэтому указываются в параметрах шаблона явно:#include <map>..............map<double,int> m;m[3.14159] = 314;map<double,int>::const_iterator mit = m.find(3.14159);cout << "Key: " << mit->first << "Value: " << mit->second << endl << flush;multimap<double,int> mm;..............multimap<double,int>::const_iterator mmit = mm.lower_bound(2.71828);multimap<double,int>::const_iterator mmend= mm.upper_bound(2.71828);for ( ; mmit != mmend; mmit++ ) {cout << mmit->first << "," << mmit->second << endl << flush;}Аналогично мультимножеству multimap позволяет сохранять в ассоциативномконтейнере элементы (пары ключ-значения) с неуникальными, повторяющимисяключами.07.11.20115Кафедра Компьютерных методов физики: программирование, первый курс, второй семестр1.

ВариантСоздать шаблонную функцию вывода для любого STL-контейнера, параметр шаблона –тип контейнера. Инстанцировать для своего класса, представляющего собой строку,изготовленную из vector<char>.2. ВариантСоздать шаблонную функцию сортировки для STL контейнеров типа vector, параметршаблонной функции передается в параметры шаблона vector, ссылка на который являетсяаргументом этой функции. Инстанцировать vector и функцию его сортировки длямассива строк (где строка – это свой класс, изготовленный из vector<char> спереопределенными операциями необходимыми для работы функции сортировки, т.е.операциями сравнения).3.