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

  После класса vector вторым по частоте использования, вероятно, является стандартный контейнер map, представляющий собой упорядоченную последовательность пар (ключ,значение) и позволяющий находить значение по ключу; например, элемент my_phone_book["Nicholas"] может быть телефонным номером Николаса. Единственным достойным конкурентом класса map по популярности является класс unordered_map (см. раздел 21.6.4), оптимизированный для ключей, представляющих собой строки. Структуры данных, аналогичные контейнерам map и unordered_map, известны под разными названиями, например ассоциативные массивы (associative arrays), хеш-таблицы (hash tables) и красно-черные деревья (red-black trees). Популярные и полезные понятия всегда имеют много названий. Мы будем называть их всех ассоциативными контейнерами (associative containers).

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

Эти контейнеры определены в заголовках , , и .

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

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

int main()

{

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

  string s;

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

                             // строками

  typedef map::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 имеют тип pair. Первый член объекта класса pair называется first, второй — second. Цикл вывода выглядит следующим образом:

typedef map::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.