Страница:
};
Чтобы это определение имело смысл еще надо определить шаблонный
класс 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* не
нужен, и можем, наконец, попробовать сортировку:
void f(SortableVector<int>& vi,
SortableVector<String>& vc,
SortableVector<int>& vi2,
SortableVector<char*>& vs)
{
sort(vi);
sort(vc);
sort(vi2);
sort(vs);
}
Возможно иметь два вида векторов и не очень хорошо, но, по крайней
мере, SortableVector является производным от Vector. Значит если
в функции не нужна сортировка, то в ней и не надо знать о классе
SortableVector, а там, где нужно, сработает неявное преобразование
ссылки на производный класс в ссылку на общий базовый класс. Мы
ввели производный от Vector и Comparator класс SortableVector
(вместо того, чтобы добавить функции к классу, производному от одного
Vector) просто потому, что класс Comparator уже напрашивался в
предыдущим примере. Такой подход типичен при создании больших
библиотек. Класс Comparator естественный кандидат для библиотеки,
поскольку в нем можно указать различные требования к операциям
сравнения для разных типов.
Можно не задавать функцию сравнения как часть типа
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 будет реализовываться подстановкой.
В частности, это полезно, если в шаблонной функции используется
несколько функций, а не одна операция сравнения, и особенно это
полезно, когда эти функции зависят от хранящихся в том же объекте
данных.
В примере из предыдущего раздела объекты 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* тривиальна и может использоваться и в других ситуациях.
Возможны ситуации, когда неявность связи между шаблонной функцией
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.
К параметрам шаблонной функции нельзя применять никаких преобразований
типа. Вместо этого при необходимости создаются новые варианты
функции:
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).
Шаблонная функция может перегружаться как простой, так и шаблонной
функцией того же имени. Разрешение перегрузки как шаблонных, так и
обычных функций с одинаковыми именами происходит за три шагаЬ:
Ь Эти правила слишком строгие, и, по всей видимости будут ослаблены,
чтобы разрешить преобразования ссылок и указателей, а, возможно,
и другие стандартные преобразования. Как обычно, при таких
преобразованиях будет действовать контроль однозначности.
[1] Найти функцию с точным сопоставлением параметров ($$R.13.2);
если такая есть, вызвать ее.
[2] Найти шаблон типа, по которому можно создать вызываемую
функцию с точным сопоставлением параметров; если такая есть,
вызвать ее.
[3] Попробовать правила разрешения для обычных функций ($$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)
Если в шаблоне для функции, которая
может иметь множество параметров с различными арифметическими
типами, используются два параметра, то в результате по шаблону будет
порождаться слишком большое число определений разных функций.
Более разумно добиваться преобразования типа, явно описав функцию
с нужными типами.
Параметр шаблона типа не обязательно должен быть именем типа
(см. $$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:
template<class T, int sz>
class buffer {
T v[sz];
// ...
};
void f()
{
buffer<char,20> buf1;
buffer<complex,20> buf2;
buffer<char,20> buf3;
buffer<char,100> buf4;
buf1 = buf2; // ошибка: несоответствие типов
buf1 = buf3; // нормально
buf1 = buf4; // ошибка: несоответствие типов
// ...
}
Если в шаблоне типа для класса используются параметры, задающие
не типы, возможно появление конструкций, выглядящих двусмысленно:
template<int i>
class X { /* ... */ };
void f(int a, int b)
{
X < a > b>; // Как это понимать: X<a> b и потом
// недопустимая лексема, или X< (a>b) >; ?
}
Этот пример синтаксически ошибочен, поскольку первая угловая скобка
> завершает параметр шаблона. В маловероятном случае, когда вам
понадобится параметр шаблона, являющийся выражением "больше чем",
используйте скобки: X< (a>b)>.
Мы уже видели, что сочетание производных классов (наследование) и
шаблонов типа может быть мощным средством. Шаблон типа выражает
общность между всеми типами, которые используются как его параметры,
а базовый класс выражает общность между всеми представлениями
(объектами) и называется интерфейсом. Здесь возможны некоторые
простые недоразумения, которых надо избегать.
Два созданных по одному шаблону типа будут различны и между ними
невозможно отношение наследования кроме единственного случая, когда
у этих типов идентичны параметры шаблона. Например:
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 мы видели, что шаблоны типа дают
удобное средство для создания целых семейств классов. Без шаблонов
создание таких семейств только с помощью производных классов
может быть утомительным занятием, а значит, ведущим к ошибкам.
С другой стороны, если отказаться от производных классов и использовать
только шаблоны, то появляется множество копий функций-членов шаблонных
классов, множество копий описательной части шаблонных классов и во
множестве повторяются функции, использующие шаблоны типа.
В контейнерных классах часто приходится выделять память. Иногда
бывает необходимо (или просто удобно) дать пользователю возможность
выбирать из нескольких вариантов выделения памяти, а также позволить
ему задавать свой вариант. Это можно сделать несколькими способами.
Один из способов состоит в том, что определяется шаблон типа для
создания нового класса, в интерфейс которого входит описание
соответствующего контейнера и класса, производящего выделение памяти
по способу, описанному в $$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). Но есть и "боковые
улицы", задающие детали реализации.
Из всех универсальных невстроенных типов самым полезным, по всей
видимости, является ассоциативный массив. Его часто называют
таблицей (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
выдают ключ и значение того элемента, на который установлен
Чтобы это определение имело смысл еще надо определить шаблонный
класс 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* не
нужен, и можем, наконец, попробовать сортировку:
void f(SortableVector<int>& vi,
SortableVector<String>& vc,
SortableVector<int>& vi2,
SortableVector<char*>& vs)
{
sort(vi);
sort(vc);
sort(vi2);
sort(vs);
}
Возможно иметь два вида векторов и не очень хорошо, но, по крайней
мере, SortableVector является производным от Vector. Значит если
в функции не нужна сортировка, то в ней и не надо знать о классе
SortableVector, а там, где нужно, сработает неявное преобразование
ссылки на производный класс в ссылку на общий базовый класс. Мы
ввели производный от Vector и Comparator класс SortableVector
(вместо того, чтобы добавить функции к классу, производному от одного
Vector) просто потому, что класс Comparator уже напрашивался в
предыдущим примере. Такой подход типичен при создании больших
библиотек. Класс Comparator естественный кандидат для библиотеки,
поскольку в нем можно указать различные требования к операциям
сравнения для разных типов.
Можно не задавать функцию сравнения как часть типа
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 будет реализовываться подстановкой.
В частности, это полезно, если в шаблонной функции используется
несколько функций, а не одна операция сравнения, и особенно это
полезно, когда эти функции зависят от хранящихся в том же объекте
данных.
В примере из предыдущего раздела объекты 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* тривиальна и может использоваться и в других ситуациях.
Возможны ситуации, когда неявность связи между шаблонной функцией
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.
К параметрам шаблонной функции нельзя применять никаких преобразований
типа. Вместо этого при необходимости создаются новые варианты
функции:
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).
Шаблонная функция может перегружаться как простой, так и шаблонной
функцией того же имени. Разрешение перегрузки как шаблонных, так и
обычных функций с одинаковыми именами происходит за три шагаЬ:
Ь Эти правила слишком строгие, и, по всей видимости будут ослаблены,
чтобы разрешить преобразования ссылок и указателей, а, возможно,
и другие стандартные преобразования. Как обычно, при таких
преобразованиях будет действовать контроль однозначности.
[1] Найти функцию с точным сопоставлением параметров ($$R.13.2);
если такая есть, вызвать ее.
[2] Найти шаблон типа, по которому можно создать вызываемую
функцию с точным сопоставлением параметров; если такая есть,
вызвать ее.
[3] Попробовать правила разрешения для обычных функций ($$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)
Если в шаблоне для функции, которая
может иметь множество параметров с различными арифметическими
типами, используются два параметра, то в результате по шаблону будет
порождаться слишком большое число определений разных функций.
Более разумно добиваться преобразования типа, явно описав функцию
с нужными типами.
Параметр шаблона типа не обязательно должен быть именем типа
(см. $$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:
template<class T, int sz>
class buffer {
T v[sz];
// ...
};
void f()
{
buffer<char,20> buf1;
buffer<complex,20> buf2;
buffer<char,20> buf3;
buffer<char,100> buf4;
buf1 = buf2; // ошибка: несоответствие типов
buf1 = buf3; // нормально
buf1 = buf4; // ошибка: несоответствие типов
// ...
}
Если в шаблоне типа для класса используются параметры, задающие
не типы, возможно появление конструкций, выглядящих двусмысленно:
template<int i>
class X { /* ... */ };
void f(int a, int b)
{
X < a > b>; // Как это понимать: X<a> b и потом
// недопустимая лексема, или X< (a>b) >; ?
}
Этот пример синтаксически ошибочен, поскольку первая угловая скобка
> завершает параметр шаблона. В маловероятном случае, когда вам
понадобится параметр шаблона, являющийся выражением "больше чем",
используйте скобки: X< (a>b)>.
Мы уже видели, что сочетание производных классов (наследование) и
шаблонов типа может быть мощным средством. Шаблон типа выражает
общность между всеми типами, которые используются как его параметры,
а базовый класс выражает общность между всеми представлениями
(объектами) и называется интерфейсом. Здесь возможны некоторые
простые недоразумения, которых надо избегать.
Два созданных по одному шаблону типа будут различны и между ними
невозможно отношение наследования кроме единственного случая, когда
у этих типов идентичны параметры шаблона. Например:
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 мы видели, что шаблоны типа дают
удобное средство для создания целых семейств классов. Без шаблонов
создание таких семейств только с помощью производных классов
может быть утомительным занятием, а значит, ведущим к ошибкам.
С другой стороны, если отказаться от производных классов и использовать
только шаблоны, то появляется множество копий функций-членов шаблонных
классов, множество копий описательной части шаблонных классов и во
множестве повторяются функции, использующие шаблоны типа.
В контейнерных классах часто приходится выделять память. Иногда
бывает необходимо (или просто удобно) дать пользователю возможность
выбирать из нескольких вариантов выделения памяти, а также позволить
ему задавать свой вариант. Это можно сделать несколькими способами.
Один из способов состоит в том, что определяется шаблон типа для
создания нового класса, в интерфейс которого входит описание
соответствующего контейнера и класса, производящего выделение памяти
по способу, описанному в $$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). Но есть и "боковые
улицы", задающие детали реализации.
Из всех универсальных невстроенных типов самым полезным, по всей
видимости, является ассоциативный массив. Его часто называют
таблицей (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
выдают ключ и значение того элемента, на который установлен