Язык программирования C++ для профессионалов
Ассоциативный массив - часть 2
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; }
