//
//
unordered_set
Упражнение 11.37. Каковы преимущества неупорядоченного контейнера по сравнению с упорядоченной версией этого контейнера? Каковы преимущества упорядоченной версии?
Упражнение 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.
