Контейнер map (ассоциативный массив, словарь)

Обычные массивы представляют собой набор пронумерованных элементов, то есть для обращения к какому-либо элементу списка необходимо указать его номер. Номер элемента в списке однозначно идентифицирует сам элемент. Но идентифицировать данные по числовым номерам не всегда оказывается удобно. Например, маршруты поездов в России идентифицируются численно-буквенным кодом (число и одна цифра), также численно-буквенным кодом идентифицируются авиарейсы, то есть для хранения информации о рейсах поездов или самолетов в качестве идентификатора удобно было бы использовать не число, а текстовую строку.

Структура данных, позволяющая идентифицировать ее элементы не по числовому индексу, а по произвольному, называется словарем или ассоциативным массивом. Соответствующая структура данных в библиотеке STL называется map (отображение), поскольку словарь является сопоставлением элементам одного множества (ключам, то есть индексам) значения из другого множества. Для использования этой структуры необходимо подключить заголовочный файл map.

Рассмотрим простой пример использования словаря. Заведем словарь Capitals, где индексом является название страны, а значением — название столицы этой страны. Это позволит легко определять по строке с названием страны ее столицу.

// Создадим словарь
map <string, string> Capitals;

// Заполним его несколькими значениями
Capitals["Russia"] = "Moscow";
Capitals["Armenia"] = "Yerevan";
Capitals["Turkey"] = "Ankara";

cout << "В какой стране вы живете? ";
cin >> country;

// Проверим, есть ли такая страна в словаре Capitals
if (Capitals.count(country))
{
    // Если есть - выведем ее столицу
    cout << "Столица вашей страны " << Capitals[country] << endl;
}
else
{
    // Запросим название столицы и добавив его в словарь
    cout << "Как называется столица вашей страны? ";
    cin >> city;
    Capitals[country] = city;
}

Итак, каждый элемент словаря состоит из двух объектов: ключа и значения. В нашем примере ключом является название страны, значением является название столицы. Ключ идентифицирует элемент словаря, значение является данными, которые соответствуют данному ключу. Значения ключей — уникальны, двух одинаковых ключей в словаре быть не может.

При объявлении структуры данных из шаблона map необходимо указать типы данных ключа и значения. В нашем примере оба этих типа string.

В жизни широко распространены словари, например, привычные бумажные словари (толковые, орфографические, лингвистические). В них ключом является слово-заголовок статьи, а значением — сама статья. Для того, чтобы получить доступ к статье, необходимо указать слово-ключ.

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

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

Когда нужно использовать словари

Словари нужно использовать в следующих случаях:

• Подсчет числа каких-то объектов. В этом случае нужно завести словарь, в котором ключами являются объекты, а значениями — их количество.
• Хранение каких-либо данных, связанных с объектом. Ключи — объекты, значения — связанные с ними данные. Например, если нужно по названию месяца определить его порядковый номер, то это можно сделать при помощи словаря Num["January"] = 1; Num["February"] = 2; ....
• Установка соответствия между объектами (например, “родитель—потомок”). Ключ — объект, значение — соответствующий ему объект.
• Если нужен обычный массив, но при этом максимальное значение индекса элемента очень велико, но при этом будут использоваться не все возможные индексы (так называемый “разреженный массив”), то можно использовать ассоциативный массив для экономии памяти.

Работа с элементами словаря

Основная операция со словарем: получение значения элемента по ключу, записывается так же, как и для массивов: A[key]. Если элемента с заданным ключом не существует в словаре, то возвращается 0, если значения словаря  числовые, пустая строка для строковых значений и значение, возвращаемое конструктором по умолчанию для более сложных объектов.

Также для доступа к элементам словаря можно использовать метод at(key). Как и в случае с вектором, этот метод производит проверку наличия в словаре элемента с ключом key, а при его отсутствии генерирует исключение (ошибка исполнения).

Проверить принадлежность ключа key словарю можно методами count(key) (возвращает количество вхождений ключа в словать, то есть 0 или 1) или find(key) (возвращает итератор на найденный элемент или значение end(), если элемент отcутствует в словаре).

Для добавления нового элемента в словарь нужно просто присвоить ему какое-то значение: A[key] = value.

Операции доступа к элементу по его ключу и добавления элемента в словарь производятся за \(O(\log n)\) (\(n\) — число элементов в словаре).

Для удаления элемента из словаря используется метод erase(). В качестве параметра ему нужно передать либо значение ключа удаляемого элемента (тогда удаление производится за \(O(\log n)\)), либо итератор на удаляемый элемент (тогда удаление будет проводиться за \(O(1)\)).

Перебор элементов словаря

Как и для множеств, для словарей определены итераторы. Методы find, upper_bound, lower_bound, begin, end, rbegin, rend возвращают итератор на элемент словаря. Назначение этих элементов такое же, как для контейнера set. Методы поиска в качестве параметра получают ключ элемента.

Разыменование итератора возвращает объект типа pair, у которого поле first — это ключ элемента, а поле second — его значение.

Используя итераторы можно организовать перебор всех элементов словаря:

Вместо громоздкой записи (*it).first и (*it).second можно использовать более компактный оператор доступа к полю через указатель “->”: it->first, it->second.

Также элементы словаря можно перебирать и при помощи range-based циклов. В этом случае значение элемента словаря - это пара из двух полей: ключ и значение. Аналогичный пример вывода элементов словаря, разыменовывать auto-переменную не нужно: