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

деревья (red-black trees). Популярные и полезные понятия всегда имеют много названий. Мы будем называть их всех ассоциативными контейнерами (associative containers).

В стандартной библиотеке предусмотрены восемь ассоциативных контейнеров.

Эти контейнеры определены в заголовках <map>, <set>, <unordered_map> и <unordered_set>.

21.6.1. Ассоциативные массивы

Рассмотрим более простую задачу: создадим список номеров вхождений слов в текст. Для этого вполне естественно записать список слов вместе с количеством их вхождений в текст. Считывая новое слово, мы проверяем, не появлялось ли оно ранее; если нет, вставляем его в список и связываем с ним число 1. Для этого можно было бы использовать объект типа list или vector, но тогда мы должны были бы искать каждое считанное слово. Такое решение было бы слишком медленным. Класс map хранит свои ключи так, чтобы их было легко увидеть, если они там есть. В этом случае поиск становится тривиальной задачей.

int main()

{

  map<string,int> words;     // хранит пары (слово, частота)

  string s;

  while (cin>>s) ++words[s]; // контейнер words индексируется

                             // строками

  typedef map<string,int>::const_iterator Iter;

  for (Iter p = words.begin(); p!=words.end(); ++p)

  cout << p–>first << ": " << p–>second << 'n';

}

Самой интересной частью этой программы является выражение ++words[s]. Как видно уже в первой строке функции main(), переменная words — это объект класса map, состоящий из пар (string, int); т.е. контейнер words отображает строки string в целые числа int. Иначе говоря, имея объект класса string, контейнер words дает нам доступ к соответствующему числу типа int. Итак, когда мы индексируем контейнер words объектом класса string (содержащим слово, считанное из потока ввода), элемент words[s] является ссылкой на число типа int, соответствующее строке s. Рассмотрим конкретный пример.

words["sultan"]

 

 Если строки "sultan" еще не было, то она вставляется в контейнер words вместе со значением, заданным по умолчанию для типа int, т.е. 0. Теперь контейнер words содержит элемент ("sultan", 0). Следовательно, если строка "sultan" ранее не вводилась, то выражение ++words["sultan"] свяжет со строкой "sultan" значение 1. Точнее говоря, объект класса map выяснит, что строки "sultan" в нем нет, вставит пару ("sultan",0), а затем оператор ++ увеличит это значение на единицу, в итоге оно станет равным 1.

Проанализируем программу еще раз: выражение ++words[s] получает слово из потока ввода и увеличивает его значение на единицу. При первом вводе каждое слово получает значение 1. Теперь смысл цикла становится понятен.

while (cin>>s) ++words[s];

Он считывает каждое слово (отделенное пробелом) из потока ввода и вычисляет количество его вхождений в контейнер. Теперь нам достаточно просто вывести результат. По контейнеру map можно перемещаться так же, как по любому другому контейнеру из библиотеки STL. Элементы контейнера map<string,int> имеют тип pair<string,int>. Первый член объекта класса pair называется first, второй — second. Цикл вывода выглядит следующим образом:

typedef map<string,int>::const_iterator Iter;

for (Iter p = words.begin(); p!=words.end(); ++p)

  cout << p–>first << ": " << p–>second << 'n';

Оператор typedef (см. разделы 20.5 и A.16) предназначен для обеспечения удобства работы и удобочитаемости программ. В качестве текста мы ввели в программу вступительный текст из первого издания книги The C++ Programming Language.

  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<Fruit,int> в памяти компьютера, если мы вставили в него пары (Kiwi,100), (Quince,0), (Plum,8), (Apple,7), (Grape,2345) и (Orange,99).

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

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

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

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

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

 

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