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

Упражнение 11.38. Перепишите программы подсчета слов (см. раздел 11.1) и преобразования слов (см. раздел 11.3.6) так, чтобы использовать контейнер unordered_map.

Ассоциативные контейнеры обеспечивают эффективный поиск и возвращение элементов по ключу. Использование ключа отличает ассоциативные контейнеры от последовательных, в которых к элементам обращаются по позиции.

Существует восемь ассоциативных контейнеров со следующими свойствами.

• Карта хранит пары ключ-значение; набор хранит только ключи.

• Есть контейнеры с уникальными ключами и с не уникальными.

• Ключи могут храниться упорядоченными или нет.

Упорядоченные контейнеры используют функцию сравнения для упорядочивания элементов по ключу. По умолчанию для сравнения используется оператор <типа ключа. Неупорядоченные контейнеры используют для организации своих элементов оператор ==типа ключа и объект типа hash.

Имена контейнеров с не уникальными ключами включают слово multi; а имена контейнеров, использующих хеширование, начинаются словом unordered. Контейнер set— это упорядоченная коллекция, каждый ключ которой уникален; контейнер unordered_multiset— это неупорядоченная коллекция, ключи которой могут повторяться.

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

Итераторы упорядоченных контейнеров обеспечивают доступ к элементам по ключу. Элементы с тем же ключом хранятся рядом друг с другом и в упорядоченных, и в неупорядоченных контейнерах.

Ассоциативный контейнер(associative container). Тип, содержащий коллекцию объектов и обеспечивающий эффективный поиск по ключу.

Ассоциативный массив(associative array). Массив, элементы которого проиндексированы по ключу, а не по позиции. Таким образом, массив сопоставляет (ассоциирует) ключ со значением.

Контейнер map(карта). Ассоциативный контейнер, аналогичный ассоциативному массиву. Подобно типу vector, тип mapявляется шаблоном класса. Но при создании карты необходимо указать два типа: тип ключа и тип связанного с ним значения. В контейнере mapключи уникальны, они не повторяются. Каждый ключ связан с определенным значением. Обращение к значению итератора карты возвращает объект типа pair, который содержит константный ключ и связанное (ассоциированное) с ним значение.

Контейнер multimap. Ассоциативный контейнер, подобный контейнеру map, но способный содержать одинаковые ключи.

Контейнер multiset. Ассоциативный контейнер, который содержит только ключи. В отличие от набора, способен содержать одинаковые ключи.

Контейнер set(набор). Ассоциативный контейнер, который содержит только ключи. Ключи в контейнере setне могут совпадать.

Контейнер unordered_map. Контейнер, элементы которого являются парами ключ-значение. Допустим только один элемент на ключ.

Контейнер unordered_multimap. Контейнер, элементы которого являются парами ключ-значение. Допустимо несколько элементов на ключ.

Контейнер unordered_multiset. Контейнер, хранящий ключи. Допустимо несколько элементов на ключ.

Контейнер unordered_set. Контейнер, хранящий ключи. Допустим только один элемент на ключ.

Неупорядоченный контейнер(unordered container). Ассоциативные контейнеры, использующие хеширование, а не сравнение ключей для хранения и доступа к элементам. Эффективность этих контейнеров зависит от качества хеш-функции.

Оператор *. Оператор обращения к значению, примененный к итератору контейнера map, set, multimapили multiset, возвращает объект типа value_type. Обратите внимание на то, что типом value_typeконтейнера mapи multimapявляется пара (pair).

Оператор []. Оператор индексирования, примененный к контейнеру map, получает индекс, типом которого должен быть key_type(или тип, допускающий преобразование в него). Возвращает значение типа mapped_type.

Строгое сравнение(strict weak ordering). Отношения между ключами ассоциативного контейнера. При строгом сравнении можно сравнить два любых значения и выяснить, которое из них меньше. Если ни одно из значений не меньше другого, они считаются равными.