Стенли Липпман - Язык программирования C++. Пятое издание

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

Классическим примером применения ассоциативного массива является программа подсчета слов:

// подсчитать, сколько раз каждое слово встречается во вводе

map word_count; // пустая карта строк и чисел

string word;

while (cin >> word)

++word_count[word]; // получить и прирастить счетчик слов

for (const auto &w : word_count) // для каждого элемента карты

// отобразить результаты

cout << w.first << " occurs " << w.second

<< ((w.second >1) ? " times" : " time") << endl;

Эта программа читает ввод и сообщает, сколько раз встречается каждое слово.

Подобно последовательным контейнерам, ассоциативные контейнеры являются шаблонами (см. раздел 3.3). Чтобы определить карту, следует указать типы ключа и значения. В этой программе карта хранит элементы, ключи которых имеют тип string, а значения — тип size_t(см. раздел 3.5.2). При индексации карты word_countстрока используется как индекс, а возвращаемый счетчик типа size_tсвязан с этой строкой.

Цикл whileчитает слова со стандартного устройства ввода по одному за раз. Он использует каждое слово для индексирования карты word_count. Если слова еще нет в карте, оператор индексирования создает новый элемент, ключом которого будет слово, а значением 0. Независимо от того, должен ли быть создан элемент, его значение увеличивается.

Как только весь ввод прочитан, серийный оператор for(см. раздел 3.2.3) перебирает карту выводя каждое слово и соответствующий счетчик.

При получении элемента из карты возвращается объект типа pair(пара), рассматриваемого в разделе 11.2.3 (стр. 545). Если не вдаваться в подробности, то pair— это шаблон типа, который содержит две открытые переменные-члена по имени first(первый) и second(второй). У используемых картой пар член firstявляется ключом, a second— соответствующим значением. Таким образом, оператор вывода должен отобразить каждое слово и связанный с ним счетчик.

Если бы эта программа была запущена для текста первого параграфа данного раздела, то вывод был бы таким:

Although occurs 1 time

Before occurs 1 time

an occurs 1 time

and occurs 1 time

...

Логичным усовершенствованием создаваемой программы будет игнорирование таких распространенных слов, как "the", "and", "or" и т.д. Для хранения игнорируемых слов будет использован набор, а подсчитываться будут только те слова, которые отсутствуют в этом наборе:

// подсчитать, сколько раз каждое слово встречается во вводе

map word_count; // пустая карта строк и чисел

set exclude = {"The", "But", "And", "Or", "An", "A",

"the", "but", "and", "or", "an", "a"};

string word;

while (cin >> word)

// подсчитать только не исключенные слова

if (exclude.find(word) == exclude.end())

++word_count[word]; // получить и прирастить счетчик слов

Подобно другим контейнерам, set является шаблоном. Чтобы определить набор, следует указать тип его элементов, которым в данном случае будет string. Подобно последовательным контейнерам, для элементов ассоциативного контейнера применима списочная инициализация (см. раздел 3.3.6). Набор excludeбудет содержать 12 слов, которые следует игнорировать.

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

// подсчитать только не исключенные слова

if (exclude.find(word) == exclude.end())

Вызов функции find()возвращает итератор. Если заданный ключ находится в наборе, итератор указывает на него. Если элемент не найден, функция find()возвращает итератор на элемент после конца. В этой версии счетчик слов изменяется, только если слово не находится в наборе exclude.

Если запустить эту версию для того же ввода, что и прежде, вывод будет таким:

Although occurs 1 time

Before occurs 1 time

are occurs 1 time

as occurs 1 time

...

Упражнение 11.1. Опишите различия между картой и вектором.

Упражнение 11.2. Приведите пример того, когда наиболее полезен контейнер list, vector, deque, mapи set.

Упражнение 11.3. Напишите собственную версию программы подсчета слов.

Упражнение 11.4. Усовершенствуйте свою программу так, чтобы игнорировать регистр и пунктуацию. Т.е. слова "example" и "Example", например, должны увеличить тот же счетчик.

Ассоциативные контейнеры (и упорядоченные, и неупорядоченные) поддерживают общие функции контейнеров, описанные в разделе 9.2 и перечисленные в табл. 9.2. Ассоциативные контейнеры не поддерживают функции, специфические для последовательных контейнеров, такие как push_front()или back(). Поскольку элементы хранятся на основании их ключа, эти операции были бы бессмысленны для ассоциативных контейнеров. Кроме того, ассоциативные контейнеры не поддерживают конструкторы и функции вставки, получающие значение элемента и его позицию.

Кроме функций, общих для всех контейнеров, ассоциативные контейнеры предоставляют некоторые функции (табл. 11.7) и псевдонимы типов (табл. 11.3), которых нет у последовательных контейнеров. Помимо этого, неупорядоченные контейнеры предоставляют функции настройки производительности их хеша, которые рассматриваются в разделе 11.4.

Итераторы ассоциативных контейнеров двунаправлены (см. раздел 10.5.1).

Как только что упоминалось, при определении карты следует указать типы ключа и значения; при определении набора задают только тип ключа, поскольку значения у него нет. Каждый из ассоциативных контейнеров имеет стандартный конструктор, который создает пустой контейнер заданного типа. Ассоциативный контейнер можно также инициализировать копией другого контейнера того же типа или диапазоном значений, тип которых может быть приведен к типу контейнера. По новому стандарту возможна также списочная инициализация элементов: