Ассоциативные контейнеры

К ассоциативным контейнерам принадлежат: set, multiset, hash set, hash multiset, map, multimap, hash_map, hash_multimap. Они поддерживают эффективный поиск значений (values), связанных с ключом (key). Они позволяют вставить и удалить элемент, но в отличие от последовательностей не позволяют вставить элемент в заранее определенную и указанную позицию. Различают сортированные ассоциативные контейнеры (set, multiset, map, multimap) и хешированные (hashed) ассоциативные контейнеры (hash_set, hash_multiset, hash_map, hash_ / multimap).

Сортированные контейнеры соблюдают отношение порядка (ordering relation) для своих ключей, причем два ключа считаются эквивалентными, если ни один из них не меньше другого. Например, если отношение порядка не учитывает регистр, то ключ "strict rules" эквивалентен ключу "Strict Rules". Сортированные контейнеры хороши тем, что они гарантируют логарифмическую эффективность (complexity) большинства своих операций. Это гораздо более сильная гарантия, чем та, которую предоставляют хешированные ассоциативные контейнеры. Последние гарантируют постоянную эффективность только в среднем, а в худшем случае — линейную.

Хешированные ассоциативные контейнеры основаны на той или иной реализации хэш-таблиц (см. монографию Кнут Д. Искусство программирования, т. 3, Сортировка и поиск, 1999). Элементы в таком контейнере не упорядочены, хотя их можно добывать последовательно. Если вы вставите или удалите элемент, то последовательность оставшихся элементов может измениться, то есть она не гарантируется. Преимуществом рассматриваемого типа контейнеров является то, что в среднем они значительно быстрее сортированных ассоциативных контейнеров. Удачно подобранная функция хеширования позволяет выполнять вставки, удаления и поиск за постоянное, не зависящее от п, время. Кроме того, она обеспечивает равномерное распределение хешированных значений и минимизирует количество коллизий.

Поясним кратко суть хеширования. Она состоит в том, что каждому ключу (key) ставится в соответствие значение (value). Например, ключом могло бы быть имя абонента — строка символов, а значением — номер его телефона. Поиск значения по ключу осуществляется с помощью хеш-таблицы (hash table), которая ассоциирует ключевой объект с объектом типа значение. Эффективность работы зависит от алгоритма хеширования, который преобразует ключ в число из какого-то диапазона. Это число еще не value, а скорее индекс для выбора значения (value). При этом возможна ситуация коллизии (collision), когда два разных ключа будут преобразованы в одно и то же число. В таких случаях производится обработка коллизии по специальному алгоритму. Обычно используются списки для хранения ключей, случайно попавших в коллизию, или, как говорят, в одно ведро (bucket). Списки — это потеря эффективности поиска, но хорошие алгоритмы хеширования гарантируют очень низкую вероятность коллизий.

Если ключи не уникальны, то можно выбрать не hаsh_mар-контейнер, а контейнер типа hash_multimap. Если нужно просто хранить множество каких-то объектов, например строк текста, не ассоциируя их с другими объектами, то стоит подумать о контейнере типа hash_set. Ну а в случае, если среди этих объектов могут попасться одинаковые, то выбором может стать контейнер типа hash_multiset.

Хешируемые типы контейнеров все-таки упорядочивают контролируемую ими последовательность, вызывая встроенный в него объект hash Traits класса value_compare. Вы имеете доступ к этому объекту с помощью метода key_comp. В общем случае два элемента признаются либо одинаковыми, либо какой-либо из них признается меньшим. Но реальная упорядоченность элементов зависит от функции хеширования, функции, задающей отношение порядка и текущего размера хэш-таблицы, поэтому в общем случае невозможно предсказать порядок следования элементов. Важной характеристикой ассоциативных контейнеров является то, что вставка элементов не портит итераторы, а удаление делает недействительными только те итераторы, которые указывают на удаляемый элемент.

Содержание раздела