Программирование. Принципы и практика использования C++ Исправленное издание, стр. 294

enjoyable: 1

facilities: 2

flexible: 1

for: 3

general: 1

is: 2

language: 1

language.: 1

make: 1

minor: 1

more: 1

new: 1

of: 1

programmer.: 1

programming: 3

provided: 1

provides: 1

purpose: 1

serious: 1

superset: 1

the: 3

to: 2

types.: 1

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

21.6.2. Обзор ассоциативных массивов

Так что же такое контейнер map? Существует много способов реализации ассоциативных массивов, но в библиотеке STL они реализованы на основе сбалансированных бинарных деревьев; точнее говоря, они представляют собой красно-черные деревья. Мы не будем вдаваться в детали, но поскольку вам известны эти технические термины, вы можете найти их объяснение в литературе или в веб.

Дерево состоит из узлов (так же как список состоит из узлов; см. раздел 20.4). В объекте класса

Node

хранятся ключ, соответствующее ему число и указатели на два последующих узла.

Программирование. Принципы и практика использования C++ Исправленное издание - _242.png

Вот как может выглядеть объект класса

map<Fruit,int>

в памяти компьютера, если мы вставили в него пары (Kiwi,100), (Quince,0), (Plum,8), (Apple,7), (Grape,2345) и (Orange,99).

Программирование. Принципы и практика использования C++ Исправленное издание - _243.png

Поскольку ключ хранится в члене класса

Node

с именем

first

, основное правило организации бинарного дерева поиска имеет следующий вид:

left–>first<first && first<right–>first

Иначе говоря, для каждого узла выполняются два условия.

• Ключ его левого подузла меньше ключа узла.

• Ключ узла меньше, чем ключ правого подузла.

Можете убедиться, что эти условия выполняются для каждого узла дерева. Это позволяет нам выполнять поиск вниз по дереву, начиная с корня. Забавно, что в литературе по компьютерным наукам деревья растут вниз. Корневым узлом является узел, содержащий пару (Orange, 99). Мы просто перемещаемся по дереву вниз, пока не найдем подходящее место. Дерево называется сбалансированным (balanced), если (как в приведенном выше примере) каждое его поддерево содержит примерно такое же количество узлов, как и одинаково удаленные от корня поддеревья. В сбалансированном дереве среднее количество узлов, которые мы должны пройти, пока не достигнем заданного узла, минимально.

В узле могут храниться дополнительные данные, которые контейнер может использовать для поддержки баланса. Дерево считается сбалансированным, если каждый узел имеет примерно одинаковое количество наследников как слева, так и справа. Если дерево, состоящее из N узлов, сбалансировано, то для обнаружения узла необходимо просмотреть не больше log₂N узлов. Это намного лучше, чем N/2 узлов в среднем, которые мы должны были бы просмотреть, если бы ключи хранились в списке, а поиск выполнялся с начала (в худшем случае линейного поиска нам пришлось бы просмотреть N узлов). (См. также раздел 21.6.4.)

Для примера покажем, как выглядит несбалансированное дерево.

Программирование. Принципы и практика использования C++ Исправленное издание - _244.png

Это дерево по-прежнему удовлетворяет критерию, требующему, чтобы ключ каждого узла был больше ключа левого подузла и меньше ключа правого.

left–>first<first && first<right–>first

И все же это дерево является несбалансированным, поэтому нам придется совершить три перехода, чтобы найти узлы Apple и Kiwi, вместо двух, как в сбалансированном дереве. Для деревьев, содержащих много узлов, эта разница может оказаться существенной, поэтому для реализации контейнеров

map

используются сбалансированные деревья.

Разбираться в принципах организации деревьев, используемых для реализации контейнера

map

, необязательно. Достаточно предположить, что профессионалы знают хотя бы принципы их работы. Все, что нам нужно, — это интерфейс класса

map

из стандартной библиотеки. Ниже приведена его несколько упрощенная версия.

template<class Key, class Value, class Cmp = less<Key> > class map

{

// ...

typedef pair<Key,Value> value_type; // контейнер map хранит

// пары (Key,Value)

typedef sometype1 iterator; // указатель на узел дерева

typedef sometype2 const_iterator;

iterator begin(); // указывает на первый элемент

iterator end(); // указывает на следующий за последним

// элемент

Value& operator[](const Key& k); // индексирование

// по переменной k

iterator find(const Key& k); // поиск по ключу k

void erase(iterator p); // удаление элемента, на который

// указывает итератор p

pair<iterator, bool> insert(const value_type&);

// вставляет пару (key,value)

// ...

};

Настоящий вариант контейнера определен в заголовке

<map>

. Можно представить себе итератор в виде указателя

Node*

, но при реализации итератора нельзя полагаться на какой-то конкретный тип.