Стоит ли хранить unordered_set в качестве ключа в unordered_map

Question

Я хочу сохранить unordered_set в качестве ключа в unordered_map, это хорошая идея, или я должен использовать std:: set для хранения некоторых данных, а затем использовать std:: map для хранения std:: set в качестве ключа. Что было бы лучше для производительности / поиска?

Любые предложения помогут

Answer 1

Как и во многих вопросах, связанных с производительностью структуры данных, точный ответ будет зависеть от вашего набора данных.
Учитывая, что вас интересует только производительность поиска, небольшие наборы данных обычно предпочитают использовать упорядоченные версии контейнеров, где "набор данных" означает среднее количество элементов в ваших ключах для типа ключа (набор против unordered_set), и количество элементов (set, value_type) для внешнего типа карты (map против unordered_map). Кстати, ничто не мешает вам смешивать упорядоченные и неупорядоченные контейнеры, такие как unordered_map, value_type>
Тем не менее, единственный способ быть на 100% уверенным в том, какой контейнер лучше, - это профилировать это с вашими фактическими данными.

Имея это в виду, вот еще несколько деталей:

• Для внешнего контейнера есть хороший шанс, что использование unordered_map обеспечит лучшую производительность поиска, основанную на обычных характеристиках хеш-контейнеров. Тем не менее, существует более тонкое влияние, которое зависит от сравнительной производительности оператора и функции хеша ключевого контейнера.
• Для ключевого контейнера на производительность поиска влияет относительная производительность контейнера "меньше чем оператор" (если ваш внешний контейнер является картой) или его хеш-функция (если ваш внешний контейнер - unordered_map).

Я постараюсь опубликовать некоторые реальные тесты, чтобы измерить это позже.