Контейнер multi_index библиотеки boost поддерживает несколько типов индексов. Среди них есть два очень похожих — ordered index и hashed index. Разница ясна из названия, hashed index не гарантирует какого-либо порядка сортировки, что, по идее, делает его несколько быстрее. Именно это и утверждается в документации: «they provide much faster lookup of elements, at the expense of losing sorting information». Что означает «much faster» далее не раскрывается.Для того, чтобы выяснить эту разницу в скорости, можно создать следующую структуру, которая будет содержать несколько полей. Эти поля в дальнейшем будут использованы в индексации:
struct container_t {
complex_elem_t hashed_index;
complex_elem_t ordered_index;
explicit container_t() : hashed_index(), ordered_index() {};
};Тип complex_elem_t введен для простой генерации уникальных элементов. Этот класс состоит из 5-ти полей типа short int, что позволило сгенерировать 10 млн. элементов без коллизий. В нем присутствуют операторы == и <. Также пришлось создать функцию hash_value, т.к. boost не умеет считать хэш для таких сложных структур.
Тип контейнера имеет следующий вид:
typedef multi_index_container<
container_t,
indexed_by<
hashed_unique< member<container_t, complex_elem_t, &container_t::hashed_index> >,
ordered_unique< member<container_t, complex_elem_t, &container_t::ordered_index> > >
> containers_t;В своих тестах я заполнял контейнеры элементами количеством от 1 до 10млн. штук. Для каждого производилось несколько поисков и результат усреднялся. Для замеров времени использовалась инструкция процессора rdtsc. Полностью тестовую программу можно скачать тут. Для построения графиков использовался OpenOffice.
На графиках видно, что поиск в ordered index происходит за логарифм, а в hashed index за константу. По X показан размер контейнера, по Y — нормированное количество тактов процессора (измерения проводились на Core2Duo E6420).
Так что, если какой-либо порядок элементов не требуется, то имеет смысл использовать hashed индекс, вместо ordered.
UPD: В первый раз не учитывались коллизии при вставке элементов и, поэтому, старый график был верен только до отметки в ~180 элементов из-за парадокса дней рождения.
