Ассоциативный массив
Из всех универсальных невстроенных типов самым полезным, по всей видимости, является ассоциативный массив. Его часто называют таблицей (map), а иногда словарем, и он хранит пары значений. Имея одно из значений, называемое ключом, можно получить доступ к другому, называемому просто значением. Ассоциативный массив можно представлять как массив, в котором индекс не обязан быть целым:
template<class K, class V> class Map { // ... public: V& operator[](const K&); // найти V, соответствующее K // и вернуть ссылку на него // ... };
Здесь ключ типа K обозначает значение типа V. Предполагается, что ключи можно сравнивать с помощью операций == и <, так что массив можно хранить в упорядоченном виде. Отметим, что класс Map отличается от типа assoc из §7.8 тем, что для него нужна операция "меньше чем", а не функция хэширования.
Приведем простую программу подсчета слов, в которой используются шаблон Map и тип String:
#include <String.h> #include <iostream.h> #include "Map.h"
int main() { Map<String,int> count; String word;
while (cin >> word) count[word]++;
for (Mapiter<String,int> p = count.first(); p; p++) cout << p.value() << '\t' << p.key() << '\n';
return 0; }
Мы используем тип String для того, чтобы не беспокоиться о выделении памяти и переполнении ее, о чем приходится помнить, используя тип char*. Итератор Mapiter нужен для выбора по порядку всех значений массива. Итерация в Mapiter задается как имитация работы с указателями. Если входной поток имеет вид
It was new. It was singular. It was simple. It must succeed.
программа выдаст
4 It 1 must 1 new. 1 simple. 1 singular. 1 succeed. 3 was.
Конечно, определить ассоциативный массив можно многими способами, а, имея определение Map и связанного с ним класса итератора, мы можем предложить много способов для их реализации. Здесь выбран тривиальный способ реализации. Используется линейный поиск, который не подходит для больших массивов. Естественно, рассчитанная на коммерческое применение реализация будет создаваться, исходя из требований быстрого поиска и компактности представления (см. упражнение 4 из §8.9).
Мы используем список с двойной связью Link:
template<class K, class V> class Map; template<class K, class V> class Mapiter;
template<class K, class V> class Link { friend class Map<K,V>; friend class Mapiter<K,V>; private: const K key; V value;
Link* pre; Link* suc;
Link(const K& k, const V& v) : key(k), value(v) { } ~Link() { delete suc; } // рекурсивное удаление всех // объектов в списке };
Каждый объект Link содержит пару (ключ, значение). Классы описаны в Link как друзья, и это гарантирует, что объекты Link можно создавать, работать с ними и уничтожать только с помощью соответствующих классов итератора и Map. Обратите внимание на предварительные описания шаблонных классов Map и Mapiter.
Шаблон Map можно определить так:
template<class K, class V> class Map { friend class Mapiter<K,V>; Link<K,V>* head; Link<K,V>* current; V def_val; K def_key; int sz;
void find(const K&); void init() { sz = 0; head = 0; current = 0; }
public:
Map() { init(); } Map(const K& k, const V& d) : def_key(k), def_val(d) { init(); } ~Map() { delete head; } // рекурсивное удаление // всех объектов в списке Map(const Map&); Map& operator= (const Map&);
V& operator[] (const K&);
int size() const { return sz; } void clear() { delete head; init(); } void remove(const K& k);
// функции для итерации
Mapiter<K,V> element(const K& k) { (void) operator[](k); // сделать k текущим элементом return Mapiter<K,V>(this,current); } Mapiter<K,V> first(); Mapiter<K,V> last(); };
Элементы хранятся в упорядоченном списке с двойной связью. Для простоты ничего не делается для ускорения поиска (см. упражнение 4 из §8.9). Ключевой здесь является функция operator[]():
template<class K, class V> V& Map<K,V>::operator[] (const K& k) { if (head == 0) { current = head = new Link<K,V>(k,def_val); current->pre = current->suc = 0; return current->value; }
Link<K,V>* p = head; for (;;) { if (p->key == k) { // найдено current = p; return current->value; }
if (k < p->key) { // вставить перед p (в начало) current = new Link<K,V>(k,def_val); current->pre = p->pre; current->suc = p; if (p == head) // текущий элемент становится начальным head = current; else p->pre->suc = current; p->pre = current; return current->value; }
Link<K,V>* s = p->suc; if (s == 0) { // вставить после p (в конец) current = new Link<K,V>(k,def_val); current->pre = p; current->suc = 0; p->suc = current; return current->value; } p = s; } }
Операция индексации возвращает ссылку на значение, которое соответствует заданному как параметр ключу. Если такое значение не найдено, возвращается новый элемент со стандартным значением. Это позволяет использовать операцию индексации в левой части присваивания. Стандартные значения для ключей и значений устанавливаются конструкторами Map. В операции индексации определяется значение current, используемое итераторами.
Реализация остальных функций-членов оставлена в качестве упражнения:
template<class K, class V> void Map<K,V>::remove(const K& k) { // см. упражнение 2 из §8.10 }
template<class K, class V> Map<K,V>::Map(const Map<K,V>& m) { // копирование таблицы Map и всех ее элементов }
template<class K, class V> Map& Map<K,V>::operator=(const Map<K,V>& m) { // копирование таблицы Map и всех ее элементов }
Теперь нам осталось только определить итерацию. В классе Map есть функции-члены first(), last() и element(const K&), которые возвращают итератор, установленный соответственно на первый, последний или задаваемый ключом-параметром элемент. Сделать это можно, поскольку элементы хранятся в упорядоченном по ключам виде.
Итератор Mapiter для Map определяется так:
template<class K, class V> class Mapiter { friend class Map<K,V>;
Map<K,V>* m; Link<K,V>* p;
Mapiter(Map<K,V>* mm, Link<K,V>* pp) { m = mm; p = pp; } public: Mapiter() { m = 0; p = 0; } Mapiter(Map<K,V>& mm);
operator void*() { return p; }
const K& key(); V& value();
Mapiter& operator--(); // префиксная void operator--(int); // постфиксная Mapiter& operator++(); // префиксная void operator++(int); // постфиксная };
После позиционирования итератора функции key() и value() из Mapiter выдают ключ и значение того элемента, на который установлен итератор.
template<class K, class V> const K& Mapiter<K,V>::key() { if (p) return p->key; else return m->def_key; }
template<class K, class V> V& Mapiter<K,V>::value() { if (p) return p->value; else return m->def_val; }
По аналогии с указателями определены операции ++ и -- для продвижения по элементам Map вперед и назад:
Mapiter<K,V>& Mapiter<K,V>::operator--() //префиксный декремент { if (p) p = p->pre; return *this; }
void Mapiter<K,V>::operator--(int) // постфиксный декремент { if (p) p = p->pre; }
Mapiter<K,V>& Mapiter<K,V>::operator++() // префиксный инкремент { if (p) p = p->suc; return *this; }
void Mapiter<K,V>::operator++(int) // постфиксный инкремент { if (p) p = p->suc; }
Постфиксные операции определены так, что они не возвращают никакого значения. Дело в том, что затраты на создание и передачу нового объекта Mapiter на каждом шаге итерации значительны, а польза от него будет не велика.
Объект Mapiter можно инициализировать так, чтобы он был установлен на начало Map:
template<class K, class V> Mapiter<K,V>::Mapiter(Map<K,V>& mm) { m == &mm; p = m->head; }
Операция преобразования operator void*() возвращает нуль, если итератор не установлен на элемент Map, и ненулевое значение иначе. Значит можно проверять итератор iter, например, так:
void f(Mapiter<const char*, Shape*>& iter) { // ... if (iter) { // установлен на элемент таблицы } else { // не установлен на элемент таблицы }
// ... }
Аналогичный прием используется для контроля потоковых операций ввода-вывода в §10.3.2.
Если итератор не установлен на элемент таблицы, его функции key() и value() возвращают ссылки на стандартные объекты.
Если после всех этих определений вы забыли их назначение, можно привести еще одну небольшую программу, использующую таблицу Map. Пусть входной поток является списком пар значений следующего вида:
hammer 2 nail 100 saw 3 saw 4 hammer 7 nail 1000 nail 250
Нужно отсортировать список так, чтобы значения, соответствующие одному предмету, складывались, и напечатать получившийся список вместе с итоговым значением:
hammer 9 nail 1350 saw 7 ------------------- total 1366
Вначале напишем функцию, которая читает входные строки и заносит предметы с их количеством в таблицу. Ключом в этой таблице является первое слово строки:
template<class K, class V> void readlines(Map<K,V>&key) { K word; while (cin >> word) { V val = 0; if (cin >> val) key[word] +=val; else return; } }
Теперь можно написать простую программу, вызывающую функцию readlines() и печатающую получившуюся таблицу:
main() { Map<String,int> tbl("nil",0); readlines(tbl);
int total = 0; for (Mapiter<String,int> p(tbl); p; ++p) { int val = p.value(); total +=val; cout << p.key() << '\t' << val << '\n'; }
cout << "--------------------\n"; cout << "total\t" << total << '\n'; }
Итерация
В классе slist_base нет функций для просмотра списка, можно только вставлять и удалять элементы. Однако, в нем описывается как друг класс slist_base_iter, поэтому можно определить подходящий для списка итератор. Вот один из возможных, заданный в том стиле, какой был показан в §7.8:
class slist_base_iter { slink* ce; // текущий элемент slist_base* cs; // текущий список public: inline slist_base_iter(slist_base& s); inline slink* operator()() };
slist_base_iter::slist_base_iter(slist_base& s) { cs = &s; ce = cs->last; }
slink* slist_base_iter::operator()() // возвращает 0, когда итерация кончается { slink* ret = ce ? (ce=ce->next) : 0; if (ce == cs->last) ce = 0; return ret; }
Исходя из этих определений, легко получить итераторы для Slist и Islist. Сначала надо определить дружественные классы для итераторов по соответствующим контейнерным классам:
template<class T> class Islist_iter;
template<class T> class Islist { friend class Islist_iter<T>; // ... };
template<class T> class Slist_iter;
template<class T> class Slist { friend class Slist_iter<T>; // ... };
Обратите внимание, что имена итераторов появляются без определения их шаблонного класса. Это способ определения в условиях взаимной зависимости шаблонов типа.
Теперь можно определить сами итераторы:
template<class T> class Islist_iter : private slist_base_iter { public: Islist_iter(Islist<T>& s) : slist_base_iter(s) { }
T* operator()() { return (T*) slist_base_iter::operator()(); } };
template<class T> class Slist_iter : private slist_base_iter { public: Slist_iter(Slist<T>& s) : slist_base_iter(s) { } inline T* operator()(); };
T* Slist_iter::operator()() { return ((Tlink<T>*) slist_base_iter::operator()())->info; }
Заметьте, что мы опять использовали прием, когда из одного базового класса строится семейство производных классов (а именно, шаблонный класс). Мы используем наследование, чтобы выразить общность классов и избежать ненужного дублирования функций. Трудно переоценить стремление избежать дублирования функций при реализации таких простых и часто используемых классов как списки и итераторы. Пользоваться этими итераторами можно так:
void f(name* p) { Islist<name> lst1; Slist<name> lst2;
lst1.insert(p); lst2.insert(p); // ...
Islist_iter<name> iter1(lst1); const name* p; while (p=iter1()) { list_iter<name> iter2(lst1); const name* q; while (q=iter2()) { if (p == q) cout << "найден" << *p << '\n'; } } }
Есть несколько способов задать итератор для контейнерного класса. Разработчик программы или библиотеки должен выбрать один из них и придерживаться его. Приведенный способ может показаться слишком хитрым. В более простом варианте можно было просто переименовать operator()() как next(). В обоих вариантах предполагается взаимосвязь между контейнерным классом и итератором для него, так что можно при выполнении итератора обработать случаи, когда элементы добавляются или удаляются из контейнера. Этот и некоторые другие способы задания итераторов были бы невозможны, если бы итератор зависел от функции пользователя, в которой есть указатели на элементы из контейнера. Как правило, контейнер или его итераторы реализуют понятие "установить итерацию на начало" и понятие "текущего элемента".
Если понятие текущего элемента предоставляет не итератор, а сам контейнер, итерация происходит в принудительном порядке по отношению к контейнеру аналогично тому, как поля связи принудительно хранятся в объектах из контейнера. Значит трудно одновременно вести две итерации для одного контейнера, но расходы на память и время при такой организации итерации близки к оптимальным. Приведем пример:
class slist_base { // ... slink* last; // last->next голова списка slink* current; // текущий элемент public: // ... slink* head() { return last?last->next:0; } slink* current() { return current; } void set_current(slink* p) { current = p; } slink* first() { set_current(head()); return current; } slink* next(); slink* prev(); };
Подобно тому, как в целях эффективности и компактности программы можно использовать для одного объекта как список с принудительной связью, так и список без нее, для одного контейнера можно использовать принудительную и непринудительную итерацию:
Неявная передача операций
В примере из предыдущего раздела объекты Comparator на самом деле никак не использовались в вычислениях. Это просто "искусственные" параметры, нужные для правильного контроля типов. Введение таких параметров достаточно общий и полезный прием, хотя и не слишком красивый. Однако, если объект используется только для передачи операции (как и было в нашем случае), т.е. в вызываемой функции не используется ни значение, ни адрес объекта, то можно вместо этого передавать операцию неявно:
template<class T> void sort(Vector<T>& v) { unsigned n = v.size();
for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (Comparator<T>::lessthan(v[j],v[j-1])) { // меняем местами v[j] и v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } }
В результате мы приходим к первоначальному варианту использования sort():
void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) {
sort(vi); // sort(Vector<int>&); sort(vc); // sort(Vector<String>&); sort(vi2); // sort(Vector<int>&); sort(vs); // sort(Vector<char*>&); }
Основное преимущество этого варианта, как и двух предыдущих, по сравнению с исходным вариантом в том, что часть программы, занятая собственно сортировкой, отделена от частей, в которых находятся такие операции, работающие с элементами, как, например lessthan. Необходимость подобного разделения растет с ростом программы, и особенный интерес это разделение представляет при проектировании библиотек. Здесь создатель библиотеки не может знать типы параметров шаблона, а пользователи не знают (или не хотят знать) специфику используемых в шаблоне алгоритмов. В частности, если бы в функции sort() использовался более сложный, оптимизированный и рассчитанный на коммерческое применение алгоритм, пользователь не очень бы стремился написать свою особую версию для типа char*, как это было сделано в §8.4.1. Хотя реализация класса Comparator для специального случая char* тривиальна и может использоваться и в других ситуациях.
Параметры шаблона типа
Параметр шаблона типа не обязательно должен быть именем типа (см. §R.14.2). Помимо имен типов можно задавать строки, имена функций и выражения-константы. Иногда бывает нужно задать как параметр целое:
template<class T, int sz> class buffer { T v[sz]; // буфер объектов произвольного типа // ... };
void f() { buffer<char,128> buf1; buffer<complex,20> buf2; // ... }
Мы сделали sz параметром шаблона buffer, а не его объектов, и это означает, что размер буфера должен быть известен на стадии трансляции, чтобы его объекты было можно размещать, не используя свободную память. Благодаря этому свойству такие шаблоны как buffer полезны для реализации контейнерных классов, поскольку для последних первостепенным фактором, определяющим их эффективность, является возможность размещать их вне свободной памяти. Например, если в реализации класса string короткие строки размещаются в стеке, это дает существенный выигрыш для программы, поскольку в большинстве задач практически все строки очень короткие. Для реализации таких типов как раз и может пригодиться шаблон buffer.
Каждый параметр шаблона типа для функции должен влиять на тип функции, и это влияние выражается в том, что он участвует по крайней мере в одном из типов формальных параметров функций, создаваемых по шаблону. Это нужно для того, чтобы функции можно было выбирать и создавать, основываясь только на их параметрах:
template<class T> void f1(T); // нормально template<class T> void f2(T*); // нормально template<class T> T f3(int); // ошибка template<int i> void f4(int[][i]); // ошибка template<int i> void f5(int = i); // ошибка template<class T, class C> void f6(T); // ошибка template<class T> void f7(const T&, complex); // нормально template<class T> void f8(Vector< List<T> >); // нормально
Здесь все ошибки вызваны тем, что параметр-тип шаблона никак не влияет на формальные параметры функций.
Подобного ограничения нет в шаблонах типа для классов. Дело в том, что параметр для такого шаблона нужно указывать всякий раз, когда описывается объект шаблонного класса. С другой стороны, для шаблонных классов возникает вопрос: когда два созданных по шаблону типа можно считать одинаковыми? Два имени шаблонного класса обозначают один и тот же класс, если совпадают имена их шаблонов, а используемые в этих именах параметры имеют одинаковые значения (с учетом возможных определений typedef, вычисления выражений-констант и т.д.). Вернемся к шаблону buffer:
Передача операций как параметров функций
Можно не задавать функцию сравнения как часть типа Vector, а передавать ее как второй параметр функции sort(). Этот параметр является объектом класса, в котором определена реализация операции сравнения:
template<class T> void sort(Vector<T>& v, Comparator<T>& cmp) { unsigned n = v.size();
for (int i = 0; i<n-1; i++) for ( int j = n-1; i<j; j--) if (cmp.lessthan(v[j],v[j-1])) { // меняем местами v[j] и v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } }
Этот вариант можно рассматривать как обобщение традиционного приема, когда операция сравнения передается как указатель на функцию.
Воспользоваться этим можно так:
void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { Comparator<int> ci; Comparator<char*> cs; Comparator<String> cc;
sort(vi,ci); // sort(Vector<int>&); sort(vc,cc); // sort(Vector<String>&); sort(vi2,ci); // sort(Vector<int>&); sort(vs,cs); // sort(Vector<char*>&); }
Отметим, что включение в шаблон класса Comparator как параметра гарантирует, что функция lessthan будет реализовываться подстановкой. В частности, это полезно, если в шаблонной функции используется несколько функций, а не одна операция сравнения, и особенно это полезно, когда эти функции зависят от хранящихся в том же объекте данных.
Производные классы позволяют ввести новые операции
В предыдущем разделе функция сравнения была "встроенной" в теле sort() (просто использовалась операция <). Возможно другое решение, когда ее предоставляет сам шаблонный класс Vector. Однако, такое решение имеет смысл только при условии, что для типов элементов возможно осмысленное понятие сравнения. Обычно в такой ситуации функцию sort() определяют только для векторов, на которых определена операция < :
template<class T> void sort(SortableVector<T>& v) { unsigned n = v.size();
for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (v.lessthan(v[j],v[j-1])) { // меняем местами v[j] и v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } }
Класс SortableVector (сортируемый вектор) можно определить так:
template<class T> class SortableVector : public Vector<T>, public Comparator<T> { public: SortableVector(int s) : Vector<T>(s) { } };
Чтобы это определение имело смысл еще надо определить шаблонный класс Comparator (сравниватель):
template<class T> class Comparator { public: inline static lessthan(T& a, T& b) // функция "меньше" { return strcmp(a,b)<0; } // ... };
Чтобы устранить тот эффект, что в нашем случае операция < дает не тот результат для типа char*, мы определим специальный вариант класса сравнивателя:
class Comparator<char*> { public: inline static lessthan(const char* a, const char* b) // функция "меньше" { return strcmp(a,b)<0; } // ... };
Описание специального варианта шаблонного класса для char* полностью подобно тому, как в предыдущем разделе мы определили специальный вариант шаблонной функции для этой же цели. Чтобы описание специального варианта шаблонного класса сработало, транслятор должен обнаружить его до использования. Иначе будет использоваться создаваемый по шаблону класс. Поскольку класс должен иметь в точности одно определение в программе, использовать и специальный вариант класса, и вариант, создаваемый по шаблону, будет ошибкой.
Поскольку у нас уже специальный вариант класса Comparator для char*, специальный вариант класса SortableVector для char* не нужен, и можем, наконец, попробовать сортировку:
Простой шаблон типа
Шаблон типа для класса задает способ построения отдельных классов, подобно тому, как описание класса задает способ построения его отдельных объектов. Можно определить стек, содержащий элементы произвольного типа:
template<class T> class stack { T* v; T* p; int sz;
public: stack(int s) { v = p = new T[sz=s]; } ~stack() { delete[] v; }
void push(T a) { *p++ = a; } T pop() { return *--p; }
int size() const { return p-v; } };
Для простоты не учитывался контроль динамических ошибок. Не считая этого, пример полный и вполне правдоподобный.
Префикс template<class T> указывает, что описывается шаблон типа с параметром T, обозначающим тип, и что это обозначение будет использоваться в последующем описании. После того, как идентификатор T указан в префиксе, его можно использовать как любое другое имя типа. Область видимости T продолжается до конца описания, начавшегося префиксом template<class T>. Отметим, что в префиксе T объявляется типом, и оно не обязано быть именем класса. Так, ниже в описании объекта sc тип T оказывается просто char.
Имя шаблонного класса, за которым следует тип, заключенный в угловые скобки <>, является именем класса (определяемым шаблоном типа), и его можно использовать как все имена класса. Например, ниже определяется объект sc класса stack<char>:
stack<char> sc(100); // стек символов
Если не считать особую форму записи имени, класс stack<char> полностью эквивалентен классу определенному так:
class stack_char { char* v; char* p; int sz; public: stack_char(int s) { v = p = new char[sz=s]; } ~stack_char() { delete[] v; }
void push(char a) { *p++ = a; } char pop() { return *--p; }
int size() const { return p-v; } };
Можно подумать, что шаблон типа - это хитрое макроопределение, подчиняющееся правилам именования, типов и областей видимости, принятым в С++. Это, конечно, упрощение, но это такое упрощение, которое помогает избежать больших недоразумений. В частности, применение шаблона типа не предполагает каких-либо средств динамической поддержки помимо тех, которые используются для обычных "ручных" классов. Не следует так же думать, что оно приводит к сокращению программы.
Обычно имеет смысл вначале отладить конкретный класс, такой, например, как stack_char, прежде, чем строить на его основе шаблон типа stack<T>. С другой стороны, для понимания шаблона типа полезно представить себе его действие на конкретном типе, например int или shape*, прежде, чем пытаться представить его во всей общности.
Имея определение шаблонного класса stack, можно следующим образом определять и использовать различные стеки:
stack<shape*> ssp(200); // стек указателей на фигуры stack<Point> sp(400); // стек структур Point
void f(stack<complex>& sc) // параметр типа `ссылка на // complex' { sc.push(complex(1,2)); complex z = 2.5*sc.pop();
stack<int>*p = 0; // указатель на стек целых p = new stack<int>(800); // стек целых размещается // в свободной памяти for ( int i = 0; i<400; i++) { p->push(i); sp.push(Point(i,i+400)); }
// ... }
Поскольку все функции- члены класса stack являются подстановками, и в этом примере транслятор создает вызовы функций только для размещения в свободной памяти и освобождения.
Функции в шаблоне типа могут и не быть подстановками, шаблонный класс stack с полным правом можно определить и так:
template<class T> class stack { T* v; T* p; int sz; public: stack(int); ~stack();
void push(T); T pop();
int size() const; };
В этом случае определение функции-члена stack должно быть дано где-то в другом месте, как это и было для функций- членов обычных, нешаблонных классов. Подобные функции так же параметризируются типом, служащим параметром для их шаблонного класса, поэтому определяются они с помощью шаблона типа для функции. Если это происходит вне шаблонного класса, это надо делать явно:
template<class T> void stack<T>::push(T a) { *p++ = a; }
template<class T> stack<T>::stack(int s) { v = p = new T[sz=s]; }
Отметим, что в пределах области видимости имени stack<T> уточнение <T> является избыточным, и stack<T>::stack - имя конструктора.
Задача системы программирования, а вовсе не программиста, предоставлять версии шаблонных функций для каждого фактического параметра шаблона типа. Поэтому для приводившегося выше примера система программирования должна создать определения конструкторов для классов stack<shape*>, stack<Point> и stack<int>, деструкторов для stack<shape*> и stack<Point>, версии функций push() для stack<complex>, stack<int> и stack<Point> и версию функции pop() для stack<complex>. Такие создаваемые функции будут совершенно обычными функциями-членами, например:
Простой шаблон типа для глобальной функции
Начнем с простейшего шаблона для sort():
template<class T> void sort(Vector<T>&);
void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { sort(vi); // sort(Vector<int>& v); sort(vc); // sort(Vector<String>& v); sort(vi2); // sort(Vector<int>& v); sort(vs); // sort(Vector<char*>& v); }
Какая именно функция sort() будет вызываться определяется фактическим параметром. Программист дает определение шаблона типа для функции, а задача системы программирования обеспечить создание правильных вариантов функции по шаблону и вызов соответствующего варианта. Например, простой шаблон с алгоритмом пузырьковой сортировки можно определить так:
template<class T> void sort(Vector<T>& v) /* Сортировка элементов в порядке возрастания Используется сортировка по методу пузырька */ { unsigned n = v.size();
for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (v[j] < v[j-1]) { // меняем местами v[j] и v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } }
Советуем сравнить это определение с функцией сортировки с тем же алгоритмом из §4.6.9. Существенное отличие этого варианта в том, что вся необходимая информация передается в единственном параметре v. Поскольку тип сортируемых элементов известен (из типа фактического параметра, можно непосредственно сравнивать элементы, а не передавать указатель на производящую сравнение функцию. Кроме того, нет нужды возиться с операцией sizeof. Такое решение кажется более красивым и к тому же оно более эффективно, чем обычное. Все же оно сталкивается с трудностью. Для некоторых типов операция < не определена, а для других, например char*, ее определение противоречит тому, что требуется в приведенном определении шаблонной функции. (Действительно, нам нужно сравнивать не указатели на строки, а сами строки). В первом случае попытка создать вариант sort() для таких типов закончится неудачей (на что и следует надеяться) , а во втором появиться функция, производящая неожиданный результат.
Чтобы правильно сортировать вектор из элементов char* мы можем просто задать самостоятельно подходящее определение функции sort(Vector<char*>&):
void sort(Vector<char*>& v) { unsigned n = v.size();
for (int i=0; i<n-1; i++) for ( int j=n-1; i<j; j--) if (strcmp(v[j],v[j-1])<0) { // меняем местами v[j] и v[j-1] char* temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } }
Поскольку для векторов из указателей на строки пользователь дал свое особое определение функции sort(), оно и будет использоваться, а создавать для нее определение по шаблону с параметром типа Vector<char*>& не нужно. Возможность дать для особо важных или "необычных" типов свое определение шаблонной функции дает ценное качество гибкости в программировании и может быть важным средством доведения программы до оптимальных характеристик.
Разрешение перегрузки для шаблонной функции
К параметрам шаблонной функции нельзя применять никаких преобразований типа. Вместо этого при необходимости создаются новые варианты функции:
template<class T> T sqrt(t);
void f(int i, double d, complex z) { complex z1 = sqrt(i); // sqrt(int) complex z2 = sqrt(d); // sqrt(double) complex z3 = sqrt(z); // sqrt(complex) // ... }
Здесь для всех трех типов параметров будет создаваться по шаблону своя функция sqrt. Если пользователь захочет чего-нибудь иного, например вызвать sqrt(double), задавая параметр int, нужно использовать явное преобразование типа:
template<class T> T sqrt(T);
void f(int i, double d, complex z) { complex z1 = sqrt(double(i)); // sqrt(double) complex z2 = sqrt(d); // sqrt(double) complex z3 = sqrt(z); // sqrt(complex) // ... }
В этом примере по шаблону будут создаваться определения только для sqrt(double) и sqrt(complex).
Шаблонная функция может перегружаться как простой, так и шаблонной функцией того же имени. Разрешение перегрузки как шаблонных, так и обычных функций с одинаковыми именами происходит за три шага:
Эти правила слишком строгие, и, по всей видимости будут ослаблены, чтобы разрешить преобразования ссылок и указателей, а, возможно, и другие стандартные преобразования. Как обычно, при таких преобразованиях будет действовать контроль однозначности.
Найти функцию с точным сопоставлением параметров (§R.13.2); если такая есть, вызвать ее.Найти шаблон типа, по которому можно создать вызываемую функцию с точным сопоставлением параметров; если такая есть, вызвать ее.Попробовать правила разрешения для обычных функций (§R13.2); если функция найдена по этим правилам, вызвать ее, иначе вызов является ошибкой.
В любом случае, если на первом шаге найдено более одной функции, вызов считается неоднозначным и является ошибкой. Например:
template<class T> T max(T a, T b) { return a>b?a:b; };
void f(int a, int b, char c, char d) { int m1 = max(a,b); // max(int,int) char m2 = max(c,d); // max(char,char) int m3 = max(a,c); // ошибка: невозможно // создать max(int,char) }
Поскольку до генерации функции по шаблону не применяется никаких преобразований типа (правило [2]), последний вызов в этом примере нельзя разрешить как max(a,int(c)). Это может сделать сам пользователь, явно описав функцию max(int,int). Тогда вступает в силу правило [3]:
template<class T> T max(T a, T b) { return a>b?a:b; }
int max(int,int);
void f(int a, int b, char c, char d) { int m1 = max(a,b); // max(int,int) char m2 = max(c,d); // max(char,char) int m3 = max(a,c); // max(int,int) }
Программисту не нужно давать определение функции max(int,int), оно по умолчанию будет создано по шаблону.
Можно определить шаблон max так, чтобы сработал первоначальный вариант нашего примера:
template<class T1, class T2> T1 max(T1 a, T2 b) { return a>b?a:b; };
void f(int a, int b, char c, char d) { int m1 = max(a,b); // int max(int,int) char m2 = max(c,d); // char max(char,char) int m3 = max(a,c); // max(int,char) }
Однако, в С и С++ правила для встроенных типов и операций над ними таковы, что использовать подобный шаблон с двумя параметрами может быть совсем непросто. Так, может оказаться неверно задавать тип результата функции как первый параметр (T1), или, по крайней мере, это может привести к неожиданному результату, например для вызова
max(c,i); // char max(char,int)
Если в шаблоне для функции, которая может иметь множество параметров с различными арифметическими типами, используются два параметра, то в результате по шаблону будет порождаться слишком большое число определений разных функций. Более разумно добиваться преобразования типа, явно описав функцию с нужными типами.
Поскольку до генерации функции по шаблону не применяется никаких преобразований типа (правило [2]), последний вызов в этом примере нельзя разрешить как max(a,int(c)). Это может сделать сам пользователь, явно описав функцию max(int,int). Тогда вступает в силу правило [3]:
template<class T> T max(T a, T b) { return a>b?a:b; }
int max(int,int);
void f(int a, int b, char c, char d) { int m1 = max(a,b); // max(int,int) char m2 = max(c,d); // max(char,char) int m3 = max(a,c); // max(int,int) }
Программисту не нужно давать определение функции max(int,int), оно по умолчанию будет создано по шаблону.
Можно определить шаблон max так, чтобы сработал первоначальный вариант нашего примера:
template<class T1, class T2> T1 max(T1 a, T2 b) { return a>b?a:b; };
void f(int a, int b, char c, char d) { int m1 = max(a,b); // int max(int,int) char m2 = max(c,d); // char max(char,char) int m3 = max(a,c); // max(int,char) }
Однако, в С и С++ правила для встроенных типов и операций над ними таковы, что использовать подобный шаблон с двумя параметрами может быть совсем непросто. Так, может оказаться неверно задавать тип результата функции как первый параметр (T1), или, по крайней мере, это может привести к неожиданному результату, например для вызова
max(c,i); // char max(char,int)
Если в шаблоне для функции, которая может иметь множество параметров с различными арифметическими типами, используются два параметра, то в результате по шаблону будет порождаться слишком большое число определений разных функций. Более разумно добиваться преобразования типа, явно описав функцию с нужными типами.
Реализация списка
Реализация функций slist_base очевидна. Единственная трудность связана с обработкой ошибок. Например, что делать если пользователь с помощью функции get() пытается взять элемент из пустого списка. Подобные ситуации разбираются в функции обработки ошибок slist_handler(). Более развитый метод, рассчитанный на особые ситуации, будет обсуждаться в лекции 9.
Приведем полное описание класса slist_base:
class slist_base { slink* last; // last->next является началом списка public: void insert(slink* a); // добавить в начало списка void append(slink* a); // добавить в конец списка slink* get(); // удалить и возвратить // начало списка void clear() { last = 0; }
slist_base() { last = 0; } slist_base(slink* a) { last = a->next = a; }
friend class slist_base_iter; };
Чтобы упростить реализацию обеих функций insert и append, хранится указатель на последний элемент замкнутого списка:
void slist_base_insert(slink* a) // добавить в начало списка { if (last) a->next = last->next; else last = a; last->next = a; }
Заметьте, что last->next - первый элемент списка.
void slist_base::append(slink* a) // добавить в конец списка { if (last) { a->next = last->next; last = last->next = a; } else last = a->next = a; }
slist* slist_base::get() // удалить и возвратить начало списка { if (last == 0) slist_handler("нельзя взять из пустого списка"); slink* f = last->next; if (f== last) last = 0; else last->next = f->next; return f; }
Возможно более гибкое решение, когда slist_handler - указатель на функцию, а не сама функция. Тогда вызов
slist_handler("нельзя взять из пустого списка");
будет задаваться так
(*slist_handler)(" нельзя взять из пустого списка");
Как мы уже делали для функции new_handler (§3.2.6), полезно завести функцию, которая поможет пользователю создавать свои обработчики ошибок:
typedef void (*PFV)(const char*);
PFV set_slist_handler(PFV a) { PFV old = slist_handler; slist_handler = a; return old; }
PFV slist_handler = &default_slist_handler;
Особые ситуации, которые обсуждаются в лекции 9, не только дают альтернативный способ обработки ошибок, но и способ реализации slist_handler.
Шаблоны типа для функций
Использование шаблонных классов означает наличие шаблонных функций-членов. Помимо этого, можно определить глобальные шаблонные функции, т.е. шаблоны типа для функций, не являющихся членами класса. Шаблон типа для функций порождает семейство функций точно также, как шаблон типа для класса порождает семейство классов. Эту возможность мы обсудим на последовательности примеров, в которых приводятся варианты функции сортировки sort(). Каждый из вариантов в последующих разделах будет иллюстрировать общий метод.
Как обычно мы сосредоточимся на организации программы, а не на разработке ее алгоритма, поэтому использоваться будет тривиальный алгоритм. Все варианты шаблона типа для sort() нужны для того, чтобы показать возможности языка м полезные приемы программирования. Варианты не упорядочены в соответствии с тем, насколько они хороши. Кроме того, можно обсудить и традиционные варианты без шаблонов типа, в частности, передачу указателя на функцию, производящую сравнение.
Шаблоны типа для списка
На практике при разработке класса, служащего коллекцией объектов, часто приходится учитывать взаимоотношения использующихся в реализации классов, управление памятью и необходимость определить итератор по содержимому коллекции. Часто бывает так, что несколько родственных классов разрабатываются совместно (§12.2). В качестве примера мы предложим семейство классов, представляющих односвязные списки и шаблоны типа для них.
Шаблоны типа и производные классы
Мы уже видели, что сочетание производных классов (наследование) и шаблонов типа может быть мощным средством. Шаблон типа выражает общность между всеми типами, которые используются как его параметры, а базовый класс выражает общность между всеми представлениями (объектами) и называется интерфейсом. Здесь возможны некоторые простые недоразумения, которых надо избегать.
Два созданных по одному шаблону типа будут различны и между ними невозможно отношение наследования кроме единственного случая, когда у этих типов идентичны параметры шаблона. Например:
template<class T> class Vector { /* ... */ }
Vector<int> v1; Vector<short> v2; Vector<int> v3;
Здесь v1 и v3 одного типа, а v2 имеет совершенно другой тип. Из того факта, что short неявно преобразуется в int, не следует, что есть неявное преобразование Vector<short> в Vector<int>:
v2 = v3; // несоответствие типов
Но этого и следовало ожидать, поскольку нет встроенного преобразования int[] в short[].
Аналогичный пример:
class circle: public shape { /* ... */ };
Vector<circle*> v4; Vector<shape*> v5; Vector<circle*> v6;
Здесь v4 и v6 одного типа, а v5 имеет совершенно другой тип. Из того факта, что существует неявное преобразование circle в shape и circle* в shape*, не следует, что есть неявные преобразования Vector<circle*> в Vector<shape*> или Vector<circle*>* в Vector<shape*>* :
v5 = v6; // несоответствие типов
Дело в том, что в общем случае структура (представление) класса, созданного по шаблону типа, такова, что для нее не предполагаются отношения наследования. Так, созданный по шаблону класс может содержать объект типа, заданного в шаблоне как параметр, а не просто указатель на него. Кроме того, допущение подобных преобразований приводит к нарушению контроля типов:
void f(Vector<circle>* pc) { Vector<shape>* ps = pc; // ошибка: несоответствие типов (*ps)[2] = new square; // круглую ножку суем в квадратное // отверстие (память выделена для // square, а используется для circle }
На примерах шаблонов Islist, Tlink, Slist, Splist, Islist_iter, Slist_iter и SortableVector мы видели, что шаблоны типа дают удобное средство для создания целых семейств классов. Без шаблонов создание таких семейств только с помощью производных классов может быть утомительным занятием, а значит, ведущим к ошибкам. С другой стороны, если отказаться от производных классов и использовать только шаблоны, то появляется множество копий функций-членов шаблонных классов, множество копий описательной части шаблонных классов и во множестве повторяются функции, использующие шаблоны типа.
Список без принудительной связи
После "экскурса" в вопросы построения и использования списка с принудительной связью перейдем к построению списков без принудительной связи. Это значит, что элементы списка не обязаны содержать дополнительную информацию, помогающую в реализации списочного класса. Поскольку мы больше не можем рассчитывать, что объект в списке имеет поле связи, такую связь надо предусмотреть в реализации:
template<class T> struct Tlink : public slink { T info; Tlink(const T& a) : info(a) { } };
Класс Tlink<T> хранит копию объектов типа T помимо поля связи, которое идет от его базового класса slink. Отметим, что используется инициализатор в виде info(a), а не присваивание info=a. Это существенно для эффективности операции в случае типов, имеющих нетривиальные конструкторы копирования и операции присваивания (§7.11). Для таких типов (например, для String) определив конструктор как
Tlink(const T& a) { info = a; }
мы получим, что будет строиться стандартный объект String, а уже затем ему будет присваиваться значение.
Имея класс, определяющий связь, и класс Islist, получить определение списка без принудительной связи совсем просто:
template<class T> class Slist : private slist_base { public: void insert(const T& a) { slist_base::insert(new Tlink<T>(a)); } void append(const T& a) { slist_base::append(new Tlink<T>(a)); } T get(); // ... };
template<class T> T Slist<T>::get() { Tlink<T>* lnk = (Tlink<T>*) slist_base::get(); T i = lnk->info; delete lnk; return i; }
Работать со списком Slist так же просто, как и со списком Ilist. Различие в том, что можно включать в Slist объект, класс которого не является производным от slink, а также можно включать один объект в два списка:
void f(int i) { Slist<int> lst1; Slist<int> lst2;
lst1.insert(i); lst2.insert(i); // ...
int i1 = lst1.get(); int i2 = lst2.get(); // ... }
Однако, список с принудительной связью, например Islist, позволял создавать существенно более эффективную программу и давал более компактное представление. Действительно, при каждом включении объекта в список Slist нужно разместить объект Tlink, а при каждом удалении объекта из Slist нужно удалить объект Tlink, причем каждый раз копируется объект типа T. Когда возникает такая проблема дополнительных расходов, могут помочь два приема. Во-первых, Tlink является прямым кандидатом для размещения с помощью практически оптимальной функции размещения специального назначения (см. §5.5.6). Тогда дополнительные расходы при выполнении программы сократятся до обычно приемлемого уровня. Во-вторых, полезным оказывается такой прием, когда объекты хранятся в "первичном" списке, имеющим принудительную связь, а списки без принудительной связи используются только, когда требуется включение объекта в несколько списков:
void f(name* p) { Islist<name> lst1; Slist<name*> lst2;
lst1.insert(p); // связь через объект `*p' lst2.insert(p); // для хранения `p' используется // отдельный объект типа список // ... }
Конечно, подобные трюки можно делать только в отдельном компоненте программы, чтобы не допустить путаницы списочных типов в интерфейсах различных компонент. Но это именно тот случай, когда ради эффективности и компактности программы на них стоит идти.
Поскольку конструктор Slist копирует параметр для insert(), список Slist пригоден только для таких небольших объектов, как целые, комплексные числа или указатели. Если для объектов копирование слишком накладно или неприемлемо по смысловым причинам, обычно выход бывает в том, чтобы вместо объектов помещать в список указатели на них. Это сделано в приведенной выше функции f() для lst2.
Отметим, что раз параметр для Slist::insert() копируется, передача объекта производного класса функции insert(), ожидающей объект базового класса, не пройдет гладко, как можно было (по наивности) подумать:
class smiley : public circle { /* ... */ };
void g1(Slist<circle>& olist, const smiley& grin) { olist.insert(grin); // ловушка! }
В список будет включена только часть circle объекта типа smiley. Отметим, что эта неприятность будет обнаружена транслятором в том случае, который можно считать наиболее вероятным. Так, если бы рассматриваемый базовый класс был абстрактным, транслятор запретил бы "урезание" объекта производного класса:
void g2(Slist<shape>& olist, const circle& c) { olist.insert(c); // ошибка: попытка создать объект // абстрактного класса }
Чтобы избежать "урезания" объекта нужно использовать указатели:
void g3(Slist<shape*>& plist, const smiley& grin) { olist.insert(&grin); // прекрасно }
Не нужно использовать параметр-ссылку для шаблонного класса:
void g4(Slist<shape&>& rlist, const smiley& grin) { rlist.insert(grin); // ошибка: будет созданы команды, // содержащие ссылку на ссылку (shape&&) }
При генерации по шаблону типа ссылки, используемые подобным образом, приведут ошибкам в типах. Генерация по шаблону типа для функции
Slist::insert(T&);
приведет к появлению недопустимой функции
Slist::insert(shape&&);
Ссылка не является объектом, поэтому нельзя иметь ссылку на ссылку.
Поскольку список указателей является полезной конструкцией, имеет смысл дать ему специальное имя:
template<class T> class Splist : private Slist<void*> { public: void insert(T* p) { Slist<void*>::insert(p); } void append(T* p) { Slist<void*>::append(p); } T* get() { return (T*) Slist<void*>::get(); } };
class Isplist : private slist_base { public: void insert(T* p) { slist_base::insert(p); } void append(T* p) { slist_base::append(p); } T* get() { return (T*) slist_base::get(); } };
Эти определения к тому же улучшают контроль типов и еще больше сокращают необходимость дублировать функции.
Часто бывает полезно, чтобы тип элемента, указываемый в шаблоне типа, сам был шаблонным классом. Например, разреженную матрицу, содержащую даты, можно определить так:
typedef Slist< Slist<date> > dates;
Обратите внимание на наличие пробелов в этом определении. Если между первой и второй угловой скобкой > нет пробелов, возникнет синтаксическая ошибка, поскольку >> в определении
typedef Slist<Slist<date>> dates;
будет трактоваться как операция сдвига вправо. Как обычно, вводимое в typedef имя служит синонимом обозначаемого им типа, а не является новым типом. Конструкция typedef полезна для именования для длинных имен шаблонных классов также, как она полезна для любых других длинных имен типов.
Отметим, что параметр шаблона типа, который может по разному использоваться в его определении, должен все равно указываться среди списка параметров шаблона один раз. Поэтому шаблон типа, в котором используется объект T и список элементов T, надо определять так:
template<class T> class mytemplate { T ob; Slist<T> slst; // ... };
Список с принудительной связью
Вначале определим простой список, в котором предполагается, что в каждом заносимом в список объекте есть поле связи. Потом этот список будет использоваться как строительный материал для создания более общих списков, в которых объект не обязан иметь поле связи. Сперва в описаниях классов будет приведена только общая часть, а реализация будет дана в следующем разделе. Это делается за тем, чтобы вопросы проектирования классов не затемнялись деталями их реализации.
Начнем с типа slink, определяющего поле связи в односвязном списке:
struct slink { slink* next; slink() { next = 0; } slink(slink* p) { next = p; } };
Теперь можно определить класс, который может содержать объекты любого, производного от slink, класса:
class slist_base { // ... public: int insert(slink*); // добавить в начало списка int append(slink*); // добавить к концу списка slink* get(); // удалить и возвратить начало списка // ... };
Такой класс можно назвать списком с принудительной связью, поскольку его можно использовать только в том случае, когда все элементы имеют поле slink, которое используется как указатель на slist_base. Само имя slist_base (базовый односвязный список) говорит, что этот класс будет использоваться как базовый для односвязных списочных классов. Как обычно, при разработке семейства родственных классов возникает вопрос, как выбирать имена для различных членов семейства. Поскольку имена классов не могут перегружаться, как это делается для имен функций, для обуздания размножения имен перегрузка нам не поможет.
Класс slist_base можно использовать так:
void f() { slist_base slb; slb.insert(new slink); // ... slink* p = slb.get(); // ... delete p; }
Но поскольку структура slink не может содержать никакой информации помимо связи, этот пример не слишком интересен. Чтобы воспользоваться slist_base, надо определить полезный, производный от slink, класс. Например, в трансляторе используются узлы дерева программы name (имя), которые приходится связывать в список:
class name : public slink { // ... };
void f(const char* s) { slist_base slb; slb.insert(new name(s)); // ... name* p = (name*)slb.get(); // ... delete p; }
Здесь все нормально, но поскольку определение класса slist_base дано через структуру slink, приходится использовать явное приведение типа для преобразования значения типа slink*, возвращаемого функцией slist_base::get(), в name*. Это некрасиво. Для большой программы, в которой много списков и производных от slink классов, это к тому же чревато ошибками. Нам пригодилась бы надежная по типу версия класса slist_base:
template<class T> class Islist : private slist_base { public: void insert(T* a) { slist_base::insert(a); } T* get() { return (T*) slist_base::get(); } // ... };
Приведение в функции Islist::get() совершенно оправдано и надежно, поскольку в классе Islist гарантируется, что каждый объект в списке действительно имеет тип T или тип производного от T класса. Отметим, что slist_base является частным базовым классом Islist. Мы нет хотим, чтобы пользователь случайно натолкнулся на ненадежные детали реализации.
Имя Islist (intrusive singly linked list) обозначает односвязный список с принудительной связью. Этот шаблон типа можно использовать так:
void f(const char* s) { Islist<name> ilst; ilst.insert(new name(s)); // ... name* p = ilst.get(); // ... delete p }
Попытки некорректного использования будет выявлены на стадии трансляции:
class expr : public slink { // ... };
void g(expr* e) { Islist<name> ilst; ilst.insert(e); // ошибка: Islist<name>::insert(), // а нужно name* // ... }
Нужно отметить несколько важных моментов относительно нашего примера. Во-первых, решение надежно в смысле типов (преграда тривиальным ошибкам ставится в очень ограниченной части программы, а именно, в функциях доступа из Islist). Во-вторых, надежность типов достигается без увеличения затрат времени и памяти, поскольку функции доступа из Islist тривиальны и реализуются подстановкой. В-третьих, поскольку вся настоящая работа со списком делается в реализации класса slist_base (пока еще не представленной), никакого дублирования функций не происходит, а исходный текст реализации, т.е. функции slist_base, вообще не должен быть доступен пользователю. Это может быть существенно в коммерческом использовании служебных программ для списков. Кроме того, достигается разделение между интерфейсом и его реализацией, и становится возможной смена реализации без перетрансляции программ пользователя. Наконец, простой список с принудительной связью близок по использованию памяти и времени к оптимальному решению. Иными словами, такой подход близок к оптимальному по времени, памяти, упрятыванию данных и контролю типов и в тоже время он обеспечивает большую гибкость и компактность выражений.
К сожалению, объект может попасть в Islist только, если он является производным от slink. Значит нельзя иметь список Islist из значений типа int, нельзя составить список из значений какого-то ранее определенного типа, не являющегося производным от slink. Кроме того, придется постараться, чтобы включить объект в два списка Islist (§6.5.1).
с двойной связью, которые будут
(*2) Определите семейство списков с двойной связью, которые будут двойниками списков с одной связью, определенных в §8.3.(*3) Определите шаблон типа String, параметром которого является тип символа. Покажите как его можно использовать не только для обычных символов, но и для гипотетического класса lchar, который представляет символы не из английского алфавита или расширенный набор символов. Нужно постараться так определить String, чтобы пользователь не заметил ухудшения характеристик программы по памяти и времени или в удобстве по сравнению с обычным строковым классом.(*1.5) Определите класс Record (запись) с двумя членами-данными: count (количество) и price (цена). Упорядочите вектор из таких записей по каждому из членов. При этом нельзя изменять функцию сортировки и шаблон Vector.(*2) Завершите определения шаблонного класса Map, написав недостающие функции-члены.(*2) Задайте другую реализацию Map из §8.8, используя списочный класс с двойной связью.(*2.5) Задайте другую реализацию Map из §8.8, используя сбалансированное дерево. Такие деревья описаны в §6.2.3 книги Д. Кнут "Искусство программирования для ЭВМ" т.1, "Мир", 1978 [K]. (*2) Сравните качество двух реализаций Map. В первой используется класс Link со своей собственной функцией размещения, а во второй - без нее.(*3) Сравните производительность программы подсчета слов из §8.8 и такой же программы, не использующей класса Map. Операции ввода-вывода должны одинаково использоваться в обеих программах. Сравните несколько таких программ, использующих разные варианты класса Map, в том числе и класс из вашей библиотеки, если он там есть.(*2.5) С помощью класса Map реализуйте топологическую сортировку. Она описана в [K] т.1, стр. 323-332. (см. упражнение 6).(*2) Модифицируйте программу из §8.8 так, чтобы она работала правильно для длинных имен и для имен, содержащих пробелы (например, "thumb back").(*2) Определите шаблон типа для чтения различных видов строк, например, таких (предмет, количество, цена).(*2) Определите класс Sort из §8.4.5, использующий сортировку по методу Шелла. Покажите как можно задать метод сортировки с помощью параметра шаблона. Алгоритм сортировки описан в [K] т.3, §5.2.1 (см. упражнение 6).(*1) Измените определения Map и Mapiter так, чтобы постфиксные операции ++ и -- возвращали объект Mapiter.(*1.5) Используйте шаблоны типа в стиле модульного программирования, как это было показано в §8.4.5 и напишите функцию сортировки, рассчитанную сразу на Vector<T> и T[].
Одним из самых полезных видов
Вот ваша цитата
Бьерн Страуструп
Одним из самых полезных видов классов является контейнерный класс, т.е. такой класс, который хранит объекты каких-то других типов. Списки, массивы, ассоциативные массивы и множества - все это контейнерные классы. С помощью описанных в лекциях 5 и 7 средств можно определить класс, как контейнер объектов единственного, известного типа. Например, в §5.3.2 определяется множество целых. Но контейнерные классы обладают тем интересным свойством, что тип содержащихся в них объектов не имеет особого значения для создателя контейнера, но для пользователя конкретного контейнера этот тип является существенным. Следовательно, тип содержащихся объектов должен параметром контейнерного класса, и создатель такого класса будет определять его с помощью типа-параметра. Для каждого конкретного контейнера (т.е. объекта контейнерного класса) пользователь будет указывать каким должен быть тип содержащихся в нем объектов. Примером такого контейнерного класса был шаблон типа Vector из §1.4.3.
В этой лекции исследуется простой шаблон типа stack (стек) и в результате вводится понятие шаблонного класса. Затем рассматриваются более полные и правдоподобные примеры нескольких родственных шаблонов типа для списка. Вводятся шаблонные функции и формулируются правила, что может быть параметром таких функций. В конце приводится шаблон типа для ассоциативного массива.
Введение операций с помощью параметров шаблонного класса
Возможны ситуации, когда неявность связи между шаблонной функцией sort() и шаблонным классом Comparator создает трудности. Неявную связь легко упустить из виду и в то же время разобраться в ней может быть непросто. Кроме того, поскольку эта связь "встроена" в функцию sort(), невозможно использовать эту функцию для сортировки векторов одного типа, если операция сравнения рассчитана на другой тип (см. упражнение 3 в §8.9). Поместив функцию sort() в класс, мы можем явно задавать связь с классом Comparator:
template<class T, class Comp> class Sort { public: static void sort(Vector<T>&); };
Не хочется повторять тип элемента, и это можно не делать, если использовать typedef в шаблоне Comparator:
template<class T> class Comparator { public: typedef T T; // определение Comparator<T>::T static int lessthan(T& a, T& b) { return a < b; } // ... };
В специальном варианте для указателей на строки это определение выглядит так:
class Comparator<char*> { public: typedef char* T; static int lessthan(T a, T b) { return strcmp(a,b) < 0; } // ... };
После этих изменений можно убрать параметр, задающий тип элемента, из класса Sort:
template<class T, class Comp> class Sort { public: static void sort(Vector<T>&); };
Теперь можно использовать сортировку так:
void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { Sort< int,Comparator<int> >::sort(vi); Sort< String,Comparator<String> >:sort(vc); Sort< int,Comparator<int> >::sort(vi2); Sort< char*,Comparator<char*> >::sort(vs); }
и определить функцию sort() следующим образом:
template<class T, class Comp> void Sort<T,Comp>::sort(Vector<T>& v) { for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (Comp::lessthan(v[j],v[j-1])) { T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } }
Последний вариант ярко демонстрирует как можно соединять в одну программу отдельные ее части. Этот пример можно еще больше упростить, если использовать класс сравнителя (Comp) в качестве единственного параметра шаблона. В этом случае в определениях класса Sort и функции Sort::sort() тип элемента будет обозначаться как Comp::T.
Задание реализации с помощью параметров шаблона
В контейнерных классах часто приходится выделять память. Иногда бывает необходимо (или просто удобно) дать пользователю возможность выбирать из нескольких вариантов выделения памяти, а также позволить ему задавать свой вариант. Это можно сделать несколькими способами. Один из способов состоит в том, что определяется шаблон типа для создания нового класса, в интерфейс которого входит описание соответствующего контейнера и класса, производящего выделение памяти по способу, описанному в §6.7.2:
template<class T, class A> class Controlled_container : public Container<T>, private A { // ... void some_function() { // ... T* p = new(A::operator new(sizeof(T))) T; // ... } // ... };
Шаблон типа здесь необходим, поскольку мы создаем контейнерный класс. Наследование от Container<T> нужно, чтобы класс Controlled_container можно было использовать как контейнерный класс. Шаблон типа с параметром A позволит нам использовать различные функции размещения:
class Shared : public Arena { /* ... */ }; class Fast_allocator { /* ... */ };
Controlled_container<Process_descriptor,Shared> ptbl;
Controlled_container<Node,Fast_allocator> tree;
Controlled_container<Personell_record,Persistent> payroll;
Это универсальный способ предоставлять производным классам содержательную информацию о реализации. Его положительными качествами являются систематичность и возможность использовать функции-подстановки. Для этого способа характерны необычно длинные имена. Впрочем, как обычно, typedef позволяет задать синонимы для слишком длинных имен типов:
typedef Controlled_container<Personell_record,Persistent> pp_record;
pp_record payroll;
Обычно шаблон типа для создания такого класса как pp_record используют только в том случае, когда добавляемая информация по реализации достаточно существенна, чтобы не вносить ее в производный класс ручным программированием. Примером такого шаблона может быть общий (возможно, для некоторых библиотек стандартный) шаблонный класс Comparator (§8.4.2), а также нетривиальные (возможно, стандартные для некоторых библиотек) классы Allocator (классы для выделения памяти). Отметим, что построение производных классов в таких примерах идет по "основному проспекту", который определяет интерфейс с пользователем (в нашем примере это Container). Но есть и "боковые улицы", задающие детали реализации.
