![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-zBpMNOrd2lEMbYP0UdxGNJ85K9Pg0GO9gyfUIYx-h-Ak_rQcYdmEuFKCdMMuBS6c-pdnZzTI_V4NEIG61TZCIfzXi6mldEy1wYVBrx3wj-w4x6kzwUpggFyOFcXp7mOtitwfRSkDgVI/s320/boost.jpg)
Для того, чтобы выяснить эту разницу в скорости, можно создать следующую структуру, которая будет содержать несколько полей. Эти поля в дальнейшем будут использованы в индексации:
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.
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9iQJvmWGrL4pHGr589xCfnaDgsEvI0Yg9vU7GPrgqfa7tQSV5pWD7FQM-K9Iy05XVoft3FAM59kcwbrj6XZbZuafp1mdFlSB5VLY97F8vqvYf1leW9MJuTdM3CIGc8slhAH2EzR6I9JU/s320/hash_vs_order.png)
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9zuXFQfGyFL3H4gQM4kErOVfvWlaE1OwFkrUcDYagXm8fBt2rOraFlWemKeXHvjIEmdZVCkgJVhVlMIsxWPqBwyZ04bpaegMtCmJsGTRCyfssVeexU0xxN2FAVC0H2fNKGBVWI82Hxp4/s320/hash_vs_order_zoom.png)
На графиках видно, что поиск в ordered index происходит за логарифм, а в hashed index за константу. По X показан размер контейнера, по Y — нормированное количество тактов процессора (измерения проводились на Core2Duo E6420).
Так что, если какой-либо порядок элементов не требуется, то имеет смысл использовать hashed индекс, вместо ordered.
UPD: В первый раз не учитывались коллизии при вставке элементов и, поэтому, старый график был верен только до отметки в ~180 элементов из-за парадокса дней рождения.