Иллюстрированный самоучитель по Visual Studio.Net
Ассоциативные контейнеры
К ассоциативным контейнерам принадлежат: 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).
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий