Язык программирования 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; }




Содержание  Назад  Вперед