Бьерн Страуструп. Язык программирования С Второе дополненное издание
 Скачать 2.87 Mb.
|
Реализация функций 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 Бьерн Страуструп. Язык программирования С++ 213 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. 8.3.4 Итерация В классе 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 Бьерн Страуструп. Язык программирования С++ 214 friend class Islist_iter // }; template // }; Обратите внимание, что имена итераторов появляются без определения их шаблонного класса. Это способ определения в условиях взаимной зависимости шаблонов типа. Теперь можно определить сами итераторы: template Islist_iter(Islist T* operator()() { return (T*) slist_base_iter::operator()(); } }; template Slist_iter(Slist T* operator()(); }; T* Slist_iter::operator()() { return ((Tlink } Заметьте, что мы опять использовали прием, когда из одного базового класса строится семейство производных классов (а именно, шаблонный класс). Мы используем наследование, чтобы выразить общность классов и избежать ненужного дублирования функций. Трудно переоценить стремление избежать дублирования функций при реализации таких простых и часто используемых классов как списки и итераторы. Пользоваться этими итераторами можно так: void f(name* p) { Islist Slist // Islist_iter (q=iter2()) { if (p == q) cout << " найден" << *p << '\n'; } } } Есть несколько способов задать итератор для контейнерного класса. Разработчик программы или библиотеки должен выбрать один из них и придерживаться его. Приведенный способ может показаться слишком хитрым. В более простом варианте можно было просто переименовать operator()() как next(). В обоих вариантах предполагается взаимосвязь между контейнерным классом и итератором для него, так Бьерн Страуструп. Язык программирования С++ 215 что можно при выполнении итератора обработать случаи, когда элементы добавляются или удаляются из контейнера. Этот и некоторые другие способы задания итераторов были бы невозможны, если бы итератор зависел от функции пользователя, в которой есть указатели на элементы из контейнера. Как правило, контейнер или его итераторы реализуют понятие "установить итерацию на начало" и понятие "текущего элемента". Если понятие текущего элемента предоставляет не итератор, а сам контейнер, итерация происходит в принудительном порядке по отношению к контейнеру аналогично тому, как поля связи принудительно хранятся в объектах из контейнера. Значит трудно одновременно вести две итерации для одного контейнера, но расходы на память и время при такой организации итерации близки к оптимальным. Приведем пример: 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(); }; Подобно тому, как в целях эффективности и компактности программы можно использовать для одного объекта как список с принудительной связью, так и список без нее, для одного контейнера можно использовать принудительную и непринудительную итерацию: void f(Islist // медленный поиск имен-дубликатов { list_iter (strcmp(p->string,q->string) == 0) cout << " дубликат" << p << '\n'; } } Еще один вид итераторов показан в $$8.8. 8.4 Шаблоны типа для функций Использование шаблонных классов означает наличие шаблонных функций-членов. Помимо этого, можно определить глобальные шаблонные функции, т.е. шаблоны типа для функций, не являющихся членами класса. Шаблон типа для функций порождает семейство функций точно также, как шаблон типа для класса порождает семейство классов. Эту возможность мы обсудим на последовательности примеров, в которых приводятся варианты функции сортировки sort(). Каждый из вариантов в последующих разделах будет иллюстрировать общий метод. Как обычно мы сосредоточимся на организации программы, а не на разработке ее алгоритма, поэтому использоваться будет тривиальный алгоритм. Все варианты шаблона типа для sort() нужны для того, чтобы показать возможности языка м полезные приемы программирования. Варианты не упорядочены в соответствии с тем, насколько они хороши. Кроме того, можно обсудить и традиционные варианты без шаблонов типа, в частности, передачу указателя на функцию, производящую сравнение. Бьерн Страуструп. Язык программирования С++ 216 8.4.1 Простой шаблон типа для глобальной функции Начнем с простейшего шаблона для sort(): template Vector Vector Vector { sort(vi); // sort(Vector // sort(Vector // sort(Vector // sort(Vector } Какая именно функция sort() будет вызываться определяется фактическим параметром. Программист дает определение шаблона типа для функции, а задача системы программирования обеспечить создание правильных вариантов функции по шаблону и вызов соответствующего варианта. Например, простой шаблон с алгоритмом пузырьковой сортировки можно определить так: template /* Сортировка элементов в порядке возрастания Используется сортировка по методу пузырька */ { unsigned n = v.size(); for (int i=0; i T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } Советуем сравнить это определение с функцией сортировки с тем же алгоритмом из $$4.6.9. Существенное отличие этого варианта в том, что вся необходимая информация передается в единственном параметре v. Поскольку тип сортируемых элементов известен (из типа фактического параметра, можно непосредственно сравнивать элементы, а не передавать указатель на производящую сравнение функцию. Кроме того, нет нужды возиться с операцией sizeof. Такое решение кажется более красивым и к тому же оно более эффективно, чем обычное. Все же оно сталкивается с трудностью. Для некоторых типов операция < не определена, а для других, например char*, ее определение противоречит тому, что требуется в приведенном определении шаблонной функции. (Действительно, нам нужно сравнивать не указатели на строки, а сами строки). В первом случае попытка создать вариант sort() для таких типов закончится неудачей (на что и следует надеяться) , а во втором появиться функция, производящая неожиданный результат. Чтобы правильно сортировать вектор из элементов char* мы можем просто задать самостоятельно подходящее определение функции sort(Vector { unsigned n = v.size(); for (int i=0; i { // меняем местами v[j] и v[j-1] char* temp = v[j]; v[j] = v[j-1]; Бьерн Страуструп. Язык программирования С++ 217 v[j-1] = temp; } } Поскольку для векторов из указателей на строки пользователь дал свое особое определение функции sort(), оно и будет использоваться, а создавать для нее определение по шаблону с параметром типа Vector 8.4.2 Производные классы позволяют ввести новые операции В предыдущем разделе функция сравнения была "встроенной" в теле sort() (просто использовалась операция <). Возможно другое решение, когда ее предоставляет сам шаблонный класс Vector. Однако, такое решение имеет смысл только при условии, что для типов элементов возможно осмысленное понятие сравнения. Обычно в такой ситуации функцию sort() определяют только для векторов, на которых определена операция < : template { unsigned n = v.size(); for (int i=0; i { // меняем местами v[j] и v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } Класс SortableVector (сортируемый вектор) можно определить так: template : public Vector SortableVector(int s) : Vector }; Чтобы это определение имело смысл еще надо определить шаблонный класс Comparator (сравниватель): template { return strcmp(a,b)<0; } // }; Чтобы устранить тот эффект, что в нашем случае операция < дает не тот результат для типа char*, мы определим специальный вариант класса сравнивателя: class Comparator // функция "меньше" { return strcmp(a,b)<0; } // }; Описание специального варианта шаблонного класса для char* полностью подобно тому, как в предыдущем разделе мы определили специальный вариант шаблонной функции для этой же цели. Чтобы описание специального варианта шаблонного класса сработало, транслятор должен обнаружить Бьерн Страуструп. Язык программирования С++ 218 его до использования. Иначе будет использоваться создаваемый по шаблону класс. Поскольку класс должен иметь в точности одно определение в программе, использовать и специальный вариант класса, и вариант, создаваемый по шаблону, будет ошибкой. Поскольку у нас уже специальный вариант класса Comparator для char*, специальный вариант класса SortableVector для char* не нужен, и можем, наконец, попробовать сортировку: void f(SortableVector SortableVector SortableVector SortableVector { sort(vi); sort(vc); sort(vi2); sort(vs); } Возможно иметь два вида векторов и не очень хорошо, но, по крайней мере, SortableVector является производным от Vector. Значит если в функции не нужна сортировка, то в ней и не надо знать о классе SortableVector, а там, где нужно, сработает неявное преобразование ссылки на производный класс в ссылку на общий базовый класс. Мы ввели производный от Vector и Comparator класс SortableVector (вместо того, чтобы добавить функции к классу, производному от одного Vector) просто потому, что класс Comparator уже напрашивался в предыдущим примере. Такой подход типичен при создании больших библиотек. Класс Comparator естественный кандидат для библиотеки, поскольку в нем можно указать различные требования к операциям сравнения для разных типов. 8.4.3 Передача операций как параметров функций Можно не задавать функцию сравнения как часть типа Vector, а передавать ее как второй параметр функции sort(). Этот параметр является объектом класса, в котором определена реализация операции сравнения: template { unsigned n = v.size(); for (int i = 0; i { // меняем местами v[j] и v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } Этот вариант можно рассматривать как обобщение традиционного приема, когда операция сравнения передается как указатель на функцию. Воспользоваться этим можно так: void f(Vector Vector Vector Vector { Comparator Comparator Comparator Бьерн Страуструп. Язык программирования С++ 219 } Отметим, что включение в шаблон класса Comparator как параметра гарантирует, что функция lessthan будет реализовываться подстановкой. В частности, это полезно, если в шаблонной функции используется несколько функций, а не одна операция сравнения, и особенно это полезно, когда эти функции зависят от хранящихся в том же объекте данных. 8.4.4 Неявная передача операций В примере из предыдущего раздела объекты Comparator на самом деле никак не использовались в вычислениях. Это просто "искусственные" параметры, нужные для правильного контроля типов. Введение таких параметров достаточно общий и полезный прием, хотя и не слишком красивый. Однако, если объект используется только для передачи операции (как и было в нашем случае), т.е. в вызываемой функции не используется ни значение, ни адрес объекта, то можно вместо этого передавать операцию неявно: template { unsigned n = v.size(); for (int i=0; i { // меняем местами v[j] и v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } В результате мы приходим к первоначальному варианту использования sort(): void f(Vector Vector Vector Vector { sort(vi); // sort(Vector } Основное преимущество этого варианта, как и двух предыдущих, по сравнению с исходным вариантом в том, что часть программы, занятая собственно сортировкой, отделена от частей, в которых находятся такие операции, работающие с элементами, как, например lessthan. Необходимость подобного разделения растет с ростом программы, и особенный интерес это разделение представляет при проектировании библиотек. Здесь создатель библиотеки не может знать типы параметров шаблона, а пользователи не знают (или не хотят знать) специфику используемых в шаблоне алгоритмов. В частности, если бы в функции sort() использовался более сложный, оптимизированный и рассчитанный на коммерческое применение алгоритм, пользователь не очень бы стремился написать свою особую версию для типа char*, как это было сделано в $$8.4.1. Хотя реализация класса Comparator для специального случая char* тривиальна и может использоваться и в других ситуациях. 8.4.5 Введение операций с помощью параметров шаблонного класса Возможны ситуации, когда неявность связи между шаблонной функцией sort() и шаблонным классом Comparator создает трудности. Неявную связь легко упустить из виду и в то же время разобраться в ней может быть непросто. Кроме того, поскольку эта связь "встроена" в функцию sort(), невозможно использовать эту функцию для сортировки векторов одного типа, если операция сравнения рассчитана на другой тип (см. упражнение 3 в $$8.9). Поместив функцию sort() в класс, мы можем явно задавать связь с классом Comparator: Бьерн Страуструп. Язык программирования С++ 220 template }; Не хочется повторять тип элемента, и это можно не делать, если использовать typedef в шаблоне Comparator: template < b; } // }; В специальном варианте для указателей на строки это определение выглядит так: class Comparator } // }; После этих изменений можно убрать параметр, задающий тип элемента, из класса Sort: template }; Теперь можно использовать сортировку так: void f(Vector Vector Vector Vector { Sort< int,Comparator Sort< String,Comparator Sort< int,Comparator Sort< char*,Comparator } и определить функцию sort() следующим образом: template { for (int i=0; i { T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } Последний вариант ярко демонстрирует как можно соединять в одну программу отдельные ее части. Этот пример можно еще больше упростить, если использовать класс сравнителя (Comp) в качестве Бьерн Страуструп. Язык программирования С++ 221 единственного параметра шаблона. В этом случае в определениях класса Sort и функции Sort::sort() тип элемента будет обозначаться как Comp::T. 8.5 Разрешение перегрузки для шаблонной функции К параметрам шаблонной функции нельзя применять никаких преобразований типа. Вместо этого при необходимости создаются новые варианты функции: template { complex z1 = sqrt(i); // sqrt(int) complex z2 = sqrt(d); // sqrt(double) complex z3 = sqrt(z); // sqrt(complex) // } Здесь для всех трех типов параметров будет создаваться по шаблону своя функция sqrt. Если пользователь захочет чего-нибудь иного, например вызвать sqrt(double), задавая параметр int, нужно использовать явное преобразование типа: template { 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 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) } Поскольку до генерации функции по шаблону не применяется никаких преобразований типа (правило Бьерн Страуструп. Язык программирования С++ 222 [2]), последний вызов в этом примере нельзя разрешить как max(a,int(c)). Это может сделать сам пользователь, явно описав функцию max(int,int). Тогда вступает в силу правило [3]: template 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 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) Если в шаблоне для функции, которая может иметь множество параметров с различными арифметическими типами, используются два параметра, то в результате по шаблону будет порождаться слишком большое число определений разных функций. Более разумно добиваться преобразования типа, явно описав функцию с нужными типами. 8.6 Параметры шаблона типа Параметр шаблона типа не обязательно должен быть именем типа (см. $$R.14.2). Помимо имен типов можно задавать строки, имена функций и выражения-константы. Иногда бывает нужно задать как параметр целое: template T v[sz]; // буфер объектов произвольного типа // }; void f() { buffer // } Мы сделали sz параметром шаблона buffer, а не его объектов, и это означает, что размер буфера должен быть известен на стадии трансляции, чтобы его объекты было можно размещать, не используя свободную память. Благодаря этому свойству такие шаблоны как buffer полезны для реализации Бьерн Страуструп. Язык программирования С++ 223 контейнерных классов, поскольку для последних первостепенным фактором, определяющим их эффективность, является возможность размещать их вне свободной памяти. Например, если в реализации класса string короткие строки размещаются в стеке, это дает существенный выигрыш для программы, поскольку в большинстве задач практически все строки очень короткие. Для реализации таких типов как раз и может пригодиться шаблон buffer. Каждый параметр шаблона типа для функции должен влиять на тип функции, и это влияние выражается в том, что он участвует по крайней мере в одном из типов формальных параметров функций, создаваемых по шаблону. Это нужно для того, чтобы функции можно было выбирать и создавать, основываясь только на их параметрах: template // нормально template // нормально template // ошибка template // ошибка template // ошибка template // ошибка template // нормально template // нормально Здесь все ошибки вызваны тем, что параметр-тип шаблона никак не влияет на формальные параметры функций. Подобного ограничения нет в шаблонах типа для классов. Дело в том, что параметр для такого шаблона нужно указывать всякий раз, когда описывается объект шаблонного класса. С другой стороны, для шаблонных классов возникает вопрос: когда два созданных по шаблону типа можно считать одинаковыми? Два имени шаблонного класса обозначают один и тот же класс, если совпадают имена их шаблонов, а используемые в этих именах параметры имеют одинаковые значения (с учетом возможных определений typedef, вычисления выражений-констант и т.д.). Вернемся к шаблону buffer: template T v[sz]; // }; void f() { buffer // } Если в шаблоне типа для класса используются параметры, задающие не типы, возможно появление конструкций, выглядящих двусмысленно: template { X < a > b>; // Как это понимать: X b и потом // недопустимая лексема, или X< (a>b) >; ? } Этот пример синтаксически ошибочен, поскольку первая угловая скобка > завершает параметр шаблона. В маловероятном случае, когда вам понадобится параметр шаблона, являющийся Бьерн Страуструп. Язык программирования С++ 224 выражением "больше чем", используйте скобки: X< (a>b)>. 8.7 Шаблоны типа и производные классы Мы уже видели, что сочетание производных классов (наследование) и шаблонов типа может быть мощным средством. Шаблон типа выражает общность между всеми типами, которые используются как его параметры, а базовый класс выражает общность между всеми представлениями (объектами) и называется интерфейсом. Здесь возможны некоторые простые недоразумения, которых надо избегать. Два созданных по одному шаблону типа будут различны и между ними невозможно отношение наследования кроме единственного случая, когда у этих типов идентичны параметры шаблона. Например: template /* ... */ } Vector Vector Vector Здесь v1 и v3 одного типа, а v2 имеет совершенно другой тип. Из того факта, что short неявно преобразуется в int, не следует, что есть неявное преобразование Vector // несоответствие типов Но этого и следовало ожидать, поскольку нет встроенного преобразования int[] в short[]. Аналогичный пример: class circle: public shape { /* ... */ }; Vector Vector Vector Здесь v4 и v6 одного типа, а v5 имеет совершенно другой тип. Из того факта, что существует неявное преобразование circle в shape и circle* в shape*, не следует, что есть неявные преобразования Vector // несоответствие типов Дело в том, что в общем случае структура (представление) класса, созданного по шаблону типа, такова, что для нее не предполагаются отношения наследования. Так, созданный по шаблону класс может содержать объект типа, заданного в шаблоне как параметр, а не просто указатель на него. Кроме того, допущение подобных преобразований приводит к нарушению контроля типов: void f(Vector { Vector // ошибка: несоответствие типов (*ps)[2] = new square; // круглую ножку суем в квадратное // отверстие (память выделена для // square, а используется для circle } На примерах шаблонов Islist, Tlink, Slist, Splist, Islist_iter, Slist_iter и SortableVector мы видели, что шаблоны типа дают удобное средство для создания целых семейств классов. Без шаблонов создание таких семейств только с помощью производных классов может быть утомительным занятием, а значит, ведущим к ошибкам. С другой стороны, если отказаться от производных классов и использовать только шаблоны, то появляется множество копий функций-членов шаблонных классов, множество копий описательной части шаблонных классов и во множестве повторяются функции, использующие шаблоны типа. Бьерн Страуструп. Язык программирования С++ 225 8.7.1 Задание реализации с помощью параметров шаблона В контейнерных классах часто приходится выделять память. Иногда бывает необходимо (или просто удобно) дать пользователю возможность выбирать из нескольких вариантов выделения памяти, а также позволить ему задавать свой вариант. Это можно сделать несколькими способами. Один из способов состоит в том, что определяется шаблон типа для создания нового класса, в интерфейс которого входит описание соответствующего контейнера и класса, производящего выделение памяти по способу, описанному в $$6.7.2: template : public Container // void some_function() { // T* p = new(A::operator new(sizeof(T))) T; // } // }; Шаблон типа здесь необходим, поскольку мы создаем контейнерный класс. Наследование от Container Controlled_container ptbl; Controlled_container Controlled_container payroll; Это универсальный способ предоставлять производным классам содержательную информацию о реализации. Его положительными качествами являются систематичность и возможность использовать функции-подстановки. Для этого способа характерны необычно длинные имена. Впрочем, как обычно, typedef позволяет задать синонимы для слишком длинных имен типов: typedef Controlled_container pp_record; pp_record payroll; Обычно шаблон типа для создания такого класса как pp_record используют только в том случае, когда добавляемая информация по реализации достаточно существенна, чтобы не вносить ее в производный класс ручным программированием. Примером такого шаблона может быть общий (возможно, для некоторых библиотек стандартный) шаблонный класс Comparator ($$8.4.2), а также нетривиальные (возможно, стандартные для некоторых библиотек) классы Allocator (классы для выделения памяти). Отметим, что построение производных классов в таких примерах идет по "основному проспекту", который определяет интерфейс с пользователем (в нашем примере это Container). Но есть и "боковые улицы", задающие детали реализации. 8.8 Ассоциативный массив Из всех универсальных невстроенных типов самым полезным, по всей видимости, является ассоциативный массив. Его часто называют таблицей (map), а иногда словарем, и он хранит пары значений. Имея одно из значений, называемое ключом, можно получить доступ к другому, называемому просто значением. Ассоциативный массив можно представлять как массив, в котором индекс не обязан быть целым: template // public: V& operator[](const K&); // найти V, соответствующее K Бьерн Страуструп. Язык программирования С++ 226 // и вернуть ссылку на него // }; Здесь ключ типа K обозначает значение типа V. Предполагается, что ключи можно сравнивать с помощью операций == и <, так что массив можно хранить в упорядоченном виде. Отметим, что класс Map отличается от типа assoc из $$7.8 тем, что для него нужна операция "меньше чем", а не функция хэширования. Приведем простую программу подсчета слов, в которой используются шаблон Map и тип String: #include #include #include "Map.h" int main() { Map String word; while (cin >> word) count[word]++; for (Mapiter 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 K key; V value; Link* pre; Link* suc; Link(const K& k, const V& v) : key(k), value(v) { } Link() { delete suc; } // рекурсивное удаление всех Бьерн Страуструп. Язык программирования С++ 227 // объектов в списке }; Каждый объект Link содержит пару (ключ, значение). Классы описаны в Link как друзья, и это гарантирует, что объекты Link можно создавать, работать с ними и уничтожать только с помощью соответствующих классов итератора и Map. Обратите внимание на предварительные описания шаблонных классов Map и Mapiter. Шаблон Map можно определить так: template Link Link 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 { (void) operator[](k); // сделать k текущим элементом return Mapiter } Mapiter Mapiter }; Элементы хранятся в упорядоченном списке с дойной связью. Для простоты ничего не делается для ускорения поиска (см. упражнение 4 из $$8.9). Ключевой здесь является функция operator[](): template V& Map { if (head == 0) { current = head = new Link } Link = p; return current->value; } if (k < p- >key) { // вставить перед p (в начало) current = new Link Бьерн Страуструп. Язык программирования С++ 228 current->pre = p->pre; current->suc = p; if (p == head) // текущий элемент становится начальным head = current; else p->pre->suc = current; p->pre = current; return current->value; } Link = new Link = p; current->suc = 0; p->suc = current; return current->value; } p = s; } } Операция индексации возвращает ссылку на значение, которое соответствует заданному как параметр ключу. Если такое значение не найдено, возвращается новый элемент со стандартным значением. Это позволяет использовать операцию индексации в левой части присваивания. Стандартные значения для ключей и значений устанавливаются конструкторами Map. В операции индексации определяется значение current, используемое итераторами. Реализация остальных функций-членов оставлена в качестве упражнения: template { // см. упражнение 2 из $$8.10 } template Map { // копирование таблицы Map и всех ее элементов } template Map& Map { // копирование таблицы Map и всех ее элементов } Теперь нам осталось только определить итерацию. В классе Map есть функции-члены first(), last() и element(const K&), которые возвращают итератор, установленный соответственно на первый, последний или задаваемый ключом-параметром элемент. Сделать это можно, поскольку элементы хранятся в упорядоченном по ключам виде. Итератор Mapiter для Map определяется так: template Map Link Mapiter(Map { m = mm; p = pp; } public: Mapiter() { m = 0; p = 0; } Mapiter(Map Бьерн Страуструп. Язык программирования С++ 229 operator void*() { return p; } const K& key(); V& value(); Mapiter& operator--(); // префиксная void operator--(int); // постфиксная Mapiter& operator++(); // префиксная void operator++(int); // постфиксная }; После позиционирования итератора функции key() и value() из Mapiter выдают ключ и значение того элемента, на который установлен итератор. template { if (p) return p->key; else return m->def_key; } template { if (p) return p->value; else return m->def_val; } По аналогии с указателями определены операции ++ и -- для продвижения по элементам Map вперед и назад: Mapiter префиксный декремент { if (p) p = p->pre; return *this; } void Mapiter { if (p) p = p->pre; } Mapiter { if (p) p = p->suc; return *this; } void Mapiter { if (p) p = p->suc; } Постфиксные операции определены так, что они не возвращают никакого значения. Дело в том, что затраты на создание и передачу нового объекта Mapiter на каждом шаге итерации значительны, а польза от него будет не велика. Объект Mapiter можно инициализировать так, чтобы он был установлен на начало Map: template { m == &mm; p = m->head; } Операция преобразования operator void*() возвращает нуль, если итератор не установлен на элемент Map, и ненулевое значение иначе. Значит можно проверять итератор iter, например, так: void f(Mapiter { Бьерн Страуструп. Язык программирования С++ 230 // 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 { K word; while (cin >> word) { V val = 0; if (cin >> val) key[word] +=val; else return; } } Теперь можно написать простую программу, вызывающую функцию readlines() и печатающую получившуюся таблицу: main() { Map Бьерн Страуструп. Язык программирования С++ 231 cout << p.key() << '\t' << val << '\n'; } cout << "--------------------\n"; cout << "total\t" << total << '\n'; } 8.9 Упражнения 1. (*2) Определите семейство списков с двойной связью, которые будут двойниками списков с одной связью, определенных в $$8.3. 2. (*3) Определите шаблон типа String, параметром которого является тип символа. Покажите как его можно использовать не только для обычных символов, но и для гипотетического класса lchar, который представляет символы не из английского алфавита или расширенный набор символов. Нужно постараться так определить String, чтобы пользователь не заметил ухудшения характеристик программы по памяти и времени или в удобстве по сравнению с обычным строковым классом. 3. (*1.5) Определите класс Record (запись) с двумя членами-данными: count (количество) и price (цена). Упорядочите вектор из таких записей по каждому из членов. При этом нельзя изменять функцию сортировки и шаблон Vector. 4. (*2) Завершите определения шаблонного класса Map, написав недостающие функции-члены. 5. (*2) Задайте другую реализацию Map из $$8.8, используя списочный класс с двойной связью. 6. (*2.5) Задайте другую реализацию Map из $$8.8, используя сбалансированное дерево. Такие деревья описаны в $$6.2.3 книги Д. Кнут "Искусство программирования для ЭВМ" т.1, "Мир", 1978 [K]. 7. (*2) Сравните качество двух реализаций Map. В первой используется класс Link со своей собственной функцией размещения, а во второй - без нее. 8. (*3) Сравните производительность программы подсчета слов из $$8.8 и такой же программы, не использующей класса Map. Операции ввода-вывода должны одинаково использоваться в обеих программах. Сравните несколько таких программ, использующих разные варианты класса Map, в том числе и класс из вашей библиотеки, если он там есть. 9. (*2.5) С помощью класса Map реализуйте топологическую сортировку. Она описана в [K] т.1, стр. 323-332. (см. упражнение 6). 10. (*2) Модифицируйте программу из $$8.8 так, чтобы она работала правильно для длинных имен и для имен, содержащих пробелы (например, "thumb back"). 11. (*2) Определите шаблон типа для чтения различных видов строк, например, таких (предмет, количество, цена). 12. (*2) Определите класс Sort из $$8.4.5, использующий сортировку по методу Шелла. Покажите как можно задать метод сортировки с помощью параметра шаблона. Алгоритм сортировки описан в [K] т.3, $$5.2.1 (см. упражнение 6). 13. (*1) Измените определения Map и Mapiter так, чтобы постфиксные операции ++ и -- возвращали объект Mapiter. 14. (*1.5) Используйте шаблоны типа в стиле модульного программирования, как это было показано в $$8.4.5 и напишите функцию сортировки, рассчитанную сразу на Vector |