В стандартной библиотеке предусмотрены восемь ассоциативных контейнеров.
Эти контейнеры определены в заголовках
<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
