Язык программирования C++ для профессионалов




Ассоциативный массив


Из всех универсальных невстроенных типов самым полезным, по всей видимости, является ассоциативный массив. Его часто называют таблицей (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.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.

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

4 It 1 must 1 new. 1 simple. 1 singular. 1 succeed. 3 was.

Конечно, определить ассоциативный массив можно многими способами, а, имея определение Map и связанного с ним класса итератора, мы можем предложить много способов для их реализации. Здесь выбран тривиальный способ реализации. Используется линейный поиск, который не подходит для больших массивов. Естественно, рассчитанная на коммерческое применение реализация будет создаваться, исходя из требований быстрого поиска и компактности представления (см. упражнение 4 из §8.9).

Мы используем список с двойной связью Link:




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