Программирование

  C++ is a general purpose programming language designed to make

  programming more enjoyable for the serious programmer. Except

  for minor details, C++ is a superset of the C programming language.

  In addition to the facilities provided by C, C++ provides flexible and

  efficient facilities for defining new types.

Результат работы программы приведен ниже.

C: 1

C++: 3

C,: 1

Except: 1

In: 1

a: 2

addition: 1

and: 1

by: 1

defining: 1

designed: 1

details,: 1

efficient: 1

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 хранятся ключ, соответствующее ему число и указатели на два последующих узла.

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

Поскольку ключ хранится в члене класса Node с именем first, основное правило организации бинарного дерева поиска имеет следующий вид:

left–>firstfirst

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

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

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

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

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

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

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

left–>firstfirst

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

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

template > class map

{

  // ...

  typedef pair value_type; // контейнер map хранит

                                      // пары (Key,Value)

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