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

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

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

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

<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"]

 

Программирование. Принципы и практика использования C++ Исправленное издание - _002.png
 Если строки "
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