Иллюстрированный самоучитель по Visual Studio.Net



              

Ассоциативные контейнеры - часть 2


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

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

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




Содержание  Назад  Вперед