Boost :: Multiindex vs string indexed boost :: unordered_map

Question

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

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

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

Answer 1

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

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

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

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

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