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

Таблица 11.1. Типы ассоциативных контейнеров

Элементы упорядочиваются по ключу map Ассоциативный массив, хранящий пары ключ-значение set Контейнер, в котором ключ является значением multimap Карта, допускающая совпадение ключей multiset Набор, допускающий совпадение ключей Неупорядоченные коллекции unordered_map Карта, организованная по хеш-функции unordered_set Набор, организованный по хеш-функции unordered_multimap Хешированная карта; ключи могут повторяться unordered multiset Хешированный набор; ключи могут повторяться

Типы map и multimap определены в заголовке map; классы set и multiset — в заголовке set; неупорядоченные версии контейнеров определены в заголовках unordered_map и unordered_set соответственно.

11.1. Использование ассоциативных контейнеров

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

Карта (тип map) — это коллекция пар ключ-значение. Например, каждая пара может содержать имя человека как ключ и номер его телефона как значение. О такой структуре данных говорят, что она "сопоставляет имена с номерами телефонов". Тип map зачастую называют ассоциативным массивом (associative array). Ассоциативный массив похож на обычный массив, но его индексы не обязаны быть целыми числами. Значения в карте находят по ключу, а не по их позиции. В карте имен и номеров телефонов имя человека использовалось бы как индекс для поиска номера телефона этого человека.

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

Использование контейнера map

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

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

map<string, size_t> 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

...

Использование контейнера set

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

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

map<string, size_t> word_count; // пустая карта строк и чисел

set<string> 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.1. Опишите различия между картой и вектором.

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

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

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

11.2. Обзор ассоциативных контейнеров

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

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

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

11.2.1. Определение ассоциативного контейнера