Boost::Multiindex против индексированного строки boost::unordered_map

Мне нужен контейнер уникальных элементов, доступ к которому осуществляется с помощью триплета int, и каждый int может быть более 1 000 000 000.

(Только некоторые из этих элементов будут фактически заполнены, и на самом деле эти элементы сами по себе являются boost::unordered_map).

Быстрее ли иметь многоиндексный массив, такой как boost::multiindex (или, может быть, что-то еще, чего я не знаю) или просто boost::unordered_map с составленной строкой в ​​качестве ключа?


c++ boost multidimensional-array boost-multi-index
person ElementalStorm    schedule 04.09.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Мультииндекс - это не то, что вам нужно, вам, кажется, нужен один индекс, тип которого - тройной. (Если вам действительно не нужны три независимых индекса; если я неправильно понял, оставьте комментарий.)

Не используйте струны, боже мой, нет. Просто используйте тройку в качестве ключа:

typedef std::tuple<int, int, int> key_type;

Если вы используете std::map<key_type, T>, вы получаете логарифмический поиск, которого может быть достаточно, и я думаю, что вам даже не нужно выполнять дополнительную работу (не уверен, что лексикографическое сравнение определено по умолчанию для кортежей).

Если вы хотите использовать std::unordered_map<key_type, T> (или ускоренную версию), вам нужно определить хеш-функцию. Я думаю, что в Boost уже есть один для кортежей, но в С++ 11 его нет; но очень легко реализовать себя на основе hash_combine(), который вы можете просто вырезать из кода Boost.

person Kerrek SB    schedule 04.09.2011
comment
Я действительно думаю, что std::tuple имеет встроенный лексикографический operator<... если все типы, которые вы передаете, конечно. - person Matthieu M.; 04.09.2011
comment
@Matthieu: Привет, приятно знать. St0rM: Если у вас нет кортежей (отметьте также <tr1/tuple> или <boost/tuple>, если у вас нет <tuple>), вы можете составить их самостоятельно или использовать pair<pair<int,int>,int>... - person Kerrek SB; 04.09.2011
comment
На самом деле кажется, что boost::tuple лучше, даже если теперь мне придется немного ударить головой, чтобы понять, как это работает. Спасибо - person ElementalStorm; 04.09.2011
comment
Он работает как пара, только с большим количеством элементов, а для доступа к элементам используется некоторый синтаксис шаблона. Преимущество кортежа boost в том, что вы сможете использовать его в неупорядоченной карте прямо из коробки. - person Kerrek SB; 04.09.2011
comment
На самом деле, для вашего кортежа нужно определить хеш-функцию, и это немного сложно, потому что вы должны помнить, что кортеж находится под boost::tuples, а не под boost. Это что-то вроде: namespace boost { namespace tuples { std::size_t hash_value(key_type const& e) { std::size_t seed = 0; boost::hash_combine( seed, e.get<0>() ); boost::hash_combine( seed, e.get<1>() ); boost::hash_combine( seed, e.get<2>() ); return seed; } } } ...но в любом случае это довольно просто :-) - person ElementalStorm; 04.09.2011
comment
@St0rM: О, хорошо, что ж, рад, что ты это понял. Я думал, что Boost определяет хэши для всех видов вещей, но кортежи, похоже, не входят в их число. С вариативными шаблонами вы можете написать общую реализацию, но если вам нужна только тройка, это подойдет. - person Kerrek SB; 04.09.2011
comment
@Kerrek: Может быть, вы хотите обновить свой ответ ... На ваше усмотрение. И еще раз спасибо, вы избавили меня от многих головных болей :-) - person ElementalStorm; 04.09.2011