Б. Страуструп - Язык программирования С++ (1119446), страница 61
Текст из файла (страница 61)
*/ };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 мы видели, чтошаблоны типа дают удобное средство для создания целых семейств классов.
Без шаблонов созданиетаких семейств только с помощью производных классов может быть утомительным занятием, а значит,ведущим к ошибкам. С другой стороны, если отказаться от производных классов и использовать толькошаблоны, то появляется множество копий функций-членов шаблонных классов, множество копийописательной части шаблонных классов и во множестве повторяются функции, использующие шаблонытипа.224Бьерн Страуструп.Язык программирования С++8.7.1 Задание реализации с помощью параметров шаблонаВ контейнерных классах часто приходится выделять память.
Иногда бывает необходимо (или простоудобно) дать пользователю возможность выбирать из нескольких вариантов выделения памяти, а такжепозволить ему задавать свой вариант. Это можно сделать несколькими способами. Один из способовсостоит в том, что определяется шаблон типа для создания нового класса, в интерфейс которого входитописание соответствующего контейнера и класса, производящего выделение памяти по способу,описанному в $$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 позволяет задать синонимы для слишком длинных имен типов:typedefControlled_container<Personell_record,Persistent> pp_record;pp_record payroll;Обычно шаблон типа для создания такого класса как pp_record используют только в том случае, когдадобавляемая информация по реализации достаточно существенна, чтобы не вносить ее в производныйкласс ручным программированием.
Примером такого шаблона может быть общий (возможно, длянекоторых библиотек стандартный) шаблонный класс Comparator ($$8.4.2), а также нетривиальные(возможно, стандартные для некоторых библиотек) классы Allocator (классы для выделения памяти).Отметим, что построение производных классов в таких примерах идет по "основному проспекту",который определяет интерфейс с пользователем (в нашем примере это Container). Но есть и "боковыеулицы", задающие детали реализации.8.8 Ассоциативный массивИз всех универсальных невстроенных типов самым полезным, по всей видимости, являетсяассоциативный массив. Его часто называют таблицей (map), а иногда словарем, и он хранит парызначений.
Имея одно из значений, называемое ключом, можно получить доступ к другому, называемомупросто значением. Ассоциативный массив можно представлять как массив, в котором индекс не обязанбыть целым:template<class K, class V> class Map {// ...public:V& operator[](const K&);// найти V, соответствующее K225Бьерн Страуструп.Язык программирования С++// и вернуть ссылку на него// ...};Здесь ключ типа 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.программа выдаст4111113Itmustnew.simple.singular.succeed.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; }// рекурсивное удаление всех226Бьерн Страуструп.Язык программирования С++// объектов в списке};Каждый объект 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);227Бьерн Страуструп.Язык программирования С++current->pre = p->pre;current->suc = p;if (p == head) // текущий элемент становится начальнымhead = current;elsep->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;}}Операция индексации возвращает ссылку на значение, которое соответствует заданному как параметрключу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
