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 позволяет задать синонимы для слишком длинных имен типов:

typedef

Controlled 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, соответствующее K

и вернуть ссылку на него

...

Здесь ключ типа 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.firstO; p; p+ + ) cout << p.valueO << \t << p.keyO << \n; return 0;

Мы используем тип String для того, чтобы не беспокоиться о выделении памяти и переполнении ее, о чем приходится помнить, используя тип char*. Итератор Mapiter нужен для выбора по порядку всех значений массива. Итерация в Mapiter задается как имитация работы с указателями. Если входной поток имеет вид

It was new. It was singular. It was simple. It must succeed.

программа выдаст

4 It

1 must

1 new.

1 simple.

1 singular.

1 succeed.

3 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; } рекурсивное удаление всех

объектов в списке

Каждый объект 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);