current->pre = p->pre; current->suc = p;

if (p == head) текущий элемент становится начальн1м

head = current; else

p->pre->suc = current; p->pre = current; return current->value;

Link<K,V>* s = p->suc;

if (s == 0) { вставить после p (в конец) current = new Link<K,V>(k,def val); current->pre = p; current->suc = 0; p->suc = current; return current->value;

p = s;

Операция индексации возвращает ссылку на значение, которое соответствует заданному как параметр ключу. Если такое значение не найдено, возвращается новый элемент со стандартным значением. Это позволяет использовать операцию индексации в левой части присваивания. Стандартные значения для ключей и значений устанавливаются конструкторами Map. В операции индексации определяется значение current, используемое итераторами.

Реализация остальных функций-членов оставлена в качестве упражнения:

template<class K, class V> void Map<K,V>::remove(const K& k)

см. упражнение 2 из $$8.10

template<class K, class V> Map<K,V>::Map(const Map<K,V>& m)

копирование таблицы Map и всех ее элементов

template<class K, class V>

Map& Map<K,V>::operator=(const Map<K,V>& m)

копирование таблицы Map и всех ее элементов

Теперь нам осталось только определить итерацию. В классе Map есть функции-члены first(), last() и element(const K&), которые возвращают итератор, установленный соответственно на первый, последний или задаваемый ключом-параметром элемент. Сделать это можно, поскольку элементы хранятся в упорядоченном по ключам виде. Итератор Mapiter для Map определяется так:

template<class K, class V> class Mapiter { friend class Map<K,V>; Map<K,V>* m; Link<K,V>* p;

Mapiter(Map<K,V>* mm, Link<K,V>* pp)

{ m = mm; p = pp; } public:

Mapiter() { m = 0; p = 0; }

Mapiter(Map<K,V>& mm);

operator void*() { return p; } const K& key(); V& value();

Mapiter& operator--(); префиксная

void operator--(int); постфиксная

Mapiter& operator++(); префиксная

void operator++(int); постфиксная

После позиционирования итератора функции key() и value() из Mapiter выдают ключ и значение того элемента, на который установлен итератор.

template<class K, class V> const K& Mapiter<K,V>::key()

if (p) return p->key; else return m->def key;

template<class K, class V> V& Mapiter<K,V>::value()

if (p) return p->value; else return m->def val;

По аналогии с указателями определены операции ++ и -- для продвижения по элементам Map вперед и назад:

Mapiter<K,V>& Mapiter<K,V>::operator--() префиксный декремент

if (p) p = p->pre; return *this;

void Mapiter<K,V>::operator--(int) постфиксный декремент

if (p) p = p->pre;

Mapiter<K,V>& Mapiter<K,V>::operator++() префиксный инкремент

if (p) p = p->suc; return *this;

void Mapiter<K,V>::operator++(int) постфиксный инкремент

if (p) p = p->suc;

Постфиксные операции определены так, что они не возвращают никакого значения. Дело в том, что затраты на создание и передачу нового объекта Mapiter на каждом шаге итерации значительны, а польза от него будет не велика.

Объект Mapiter можно инициализировать так, чтобы он был установлен на начало Map:

template<class K, class V> Mapiter<K,V>::Mapiter(Map<K,V>& mm)

m == &mm; p = m->head;

Операция преобразования operator void*() возвращает нуль, если итератор не установлен на элемент Map, и ненулевое значение иначе. Значит можно проверять итератор iter, например, так:

void f(Mapiter<const char*, Shape*>& iter)

Нужно отсортировать список так, чтобы значения, соответствующие одному предмету, складывались, и напечатать получившийся список вместе с итоговым значением:

hammer 9

nail 1350

saw 7

total 1366

Вначале напишем функцию, которая читает входные строки и заносит предметы с их количеством в таблицу. Ключом в этой таблице является первое слово строки:

template<class K, class V> void readlines(Map<K,V>&key)

K word;

while (cin >> word) {

V val = 0;

if (cin >> val)

key[word] +=val; else

return;

Теперь можно написать простую программу, вызывающую функцию readlines() и печатающую получившуюся таблицу:

main()

Map<String,int> tbl( nil ,0); readlines(tbl); int total = 0;

for (Mapiter<String,int> p(tbl); p; ++p) { int val = p.valueO; total +=val;

...

if (iter) {

установлен на элемент таблицы

else {

не установлен на элемент таблицы

...

Аналогичный прием используется для контроля потоковых операций ввода-вывода в $$1 0.3.2.

Если итератор не установлен на элемент таблицы, его функции key() и value() возвращают ссылки на стандартные объекты.

Если после всех этих определений вы забыли их назначение, можно привести еще одну небольшую программу, использующую таблицу Map. Пусть входной поток является списком пар значений следующего вида: