Самый быстрый тип для std :: map key?

Question

Я хотел бы использовать разделы графа в качестве ключа к std :: map

Я мог бы представить это как вектор std узлов.Или я мог бы преобразовать его в более компактный «пользовательский» двоичный формат (битовый набор?) Или строковое представление.

Для упрощения можно сказать, что нет никакого внутреннего порядка для секций графа.

Который будет самым быстрым с точки зрения вставки и поиска (обратите внимание, что размер этой карты будет порядка миллиарда узлов)

Answer 1

Сохраняйте свой тип ключа, но используйте unordered_map boost и напишите свою собственную функцию hash() для вашего графического раздела.

Например, если порядок не имеет значения, вы можете хэшировать каждый узел способом, который не зависит от порядка. Если вы опубликуете, как вы его кодируете сейчас, мы можем помочь с этим подробнее.

Answer 2

Если у вас будет столько записей и производительность критична, я бы посоветовал использовать unordered_map.

Если вы используете C ++ 1x, он находится в стандартной библиотеке; в противном случае вы можете получить его из boost .

Если производительность действительно критическая, вы можете пойти еще дальше и использовать boost :: intrusive . Он содержит «навязчивые» версии контейнеров стандартной библиотеки: они копируют указатели значений, которые вы вставляете, вместо самих значений. Если значения велики, вы получите большой выигрыш в производительности.

Answer 3

Единственный способ надежно ответить на этот вопрос - это единственный способ ответить на ЛЮБОЙ вопрос оптимизации: попробуйте и посмотрите.

Тем не менее, я сомневаюсь, что между ними будет большая разница, если есть эффективный оператор сравнения, который вы можете использовать.