straustrup2 (852740), страница 59
Текст из файла (страница 59)
Примером такого шаблона может быть общий (возможно, длянекоторых библиотек стандартный) шаблонный класс 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;}}Операция индексации возвращает ссылку на значение, которое соответствует заданному как параметрключу.
Если такое значение не найдено, возвращается новый элемент со стандартным значением. Этопозволяет использовать операцию индексации в левой части присваивания. Стандартные значения дляключей и значений устанавливаются конструкторами 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);228Бьерн Страуструп.operator void*() { return p; }const K& key();V& value();Mapiter& operator--();void operator--(int);Mapiter& operator++();void operator++(int);Язык программирования С++////////префикснаяпостфикснаяпрефикснаяпостфиксная};После позиционирования итератора функции key() и value() из Mapiter выдают ключ и значение тогоэлемента, на который установлен итератор.template<class K, class V> const K& Mapiter<K,V>::key(){if (p) return p->key; else return m->def_key;}template<class K, class V> V& Mapiter<K,V>::value(){if (p) return p->value; else return m->def_val;}По аналогии с указателями определены операции ++ и -- для продвижения по элементам Map вперед иназад:Mapiter<K,V>& Mapiter<K,V>::operator--() //префиксный декремент{if (p) p = p->pre;return *this;}void Mapiter<K,V>::operator--(int){if (p) p = p->pre;}// постфиксный декрементMapiter<K,V>& Mapiter<K,V>::operator++() // префиксный инкремент{if (p) p = p->suc;return *this;}void Mapiter<K,V>::operator++(int){if (p) p = p->suc;}// постфиксный инкрементПостфиксные операции определены так, что они не возвращают никакого значения.
Дело в том, чтозатраты на создание и передачу нового объекта Mapiter на каждом шаге итерации значительны, апольза от него будет не велика.Объект Mapiter можно инициализировать так, чтобы он был установлен на начало Map:template<class K, class V> Mapiter<K,V>::Mapiter(Map<K,V>& mm){m == &mm; p = m->head;}Операция преобразования operator void*() возвращает нуль, если итератор не установлен на элементMap, и ненулевое значение иначе. Значит можно проверять итератор iter, например, так:void f(Mapiter<const char*, Shape*>& iter){229Бьерн Страуструп.Язык программирования С++// ...if (iter) {// установлен на элемент таблицы}else {// не установлен на элемент таблицы}// ...}Аналогичный прием используется для контроля потоковых операций ввода-вывода в $$10.3.2.Если итератор не установлен на элемент таблицы, его функции key() и value() возвращают ссылки настандартные объекты.Если после всех этих определений вы забыли их назначение, можно привести еще одну небольшуюпрограмму, использующую таблицу Map.
Пусть входной поток является списком пар значенийследующего вида:hammernailsawsawhammernailnail21003471000250Нужно отсортировать список так, чтобы значения, соответствующие одному предмету, складывались, инапечатать получившийся список вместе с итоговым значением:hammer9nail1350saw7------------------total1366Вначале напишем функцию, которая читает входные строки и заносит предметы с их количеством втаблицу. Ключом в этой таблице является первое слово строки:template<class K, class V>void readlines(Map<K,V>&key){K word;while (cin >> word) {V val = 0;if (cin >> val)key[word] +=val;elsereturn;}}Теперь можно написать простую программу, вызывающую функцию readlines() и печатающуюполучившуюся таблицу:main(){Map<String,int> tbl("nil",0);readlines(tbl);int total = 0;for (Mapiter<String,int> p(tbl); p; ++p) {int val = p.value();total +=val;230Бьерн Страуструп.Язык программирования С++cout << p.key() << '\t' << val << '\n';}cout << "--------------------\n";cout << "total\t" << total << '\n';}8.9 Упражнения1.(*2) Определите семейство списков с двойной связью, которые будут двойниками списков с однойсвязью, определенных в $$8.3.2.(*3) Определите шаблон типа String, параметром которого является тип символа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
