Для операции count(). Что быстрее std :: set <void*> или std :: unordered_set <void*>?

Question

Предположим, что sizeof(void*) == sizeof(size_t) и что хэширование указателя просто отливает его в size_t. Поэтому я хочу знать, содержит ли мой набор элемент, который будет быстрее std::set<void*> или std::unordered_set<void*>?

Я знаю, как работает std::set, но я не знаком с std::unordered_set. Ну, я знаю, что неупорядоченный набор использует хеширование и ведра и что, если пересечение не происходит (это мой случай), сложность O (1). Но я не знаю, насколько это постоянная сложность.

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

¹ Количество элементов настолько мало, что даже std::vector будет выполнять штраф.

Answer 1

Я думаю, что важно немного в маленьком примечании:

Количество элементов настолько мало, что даже std::vector будет выполнять хорошо.

std::vector больше кэша дружественный чем std::set и std::unordered_set, поскольку она выделяет его элементы в непрерывной области памяти (это предусмотрено в стандарте).

И хотя поиск и сложность вставки хуже для std::vector чем для std::set или std::unordered_set (линейный по сравнению с O (журнал N) и амортизируется O (1), соответственно), расположение данных и более высокая скорость хит кэш вероятно, будут доминировать над вычислительной сложностью и повысить производительность.

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

Как всегда, измеряет различные альтернативы до того, как вы совершите сделку, и всегда предпочитаете более простой дизайн, если у вас нет доказательств того, что оно представляет собой узкое место, препятствующее выполнению вашим заявлением требований к производительности.

Answer 2

unordered_set имеет большую локальность кэша, чем set во многих реализациях. Но так как количество элементов настолько мало в вашем случае, то vector, вероятно, полностью впишется в кеш, что делает его лучшим выбором, несмотря на сложность поиска элементов (O).