Стоит ли хранить unordered_set в качестве ключа в unordered_map
Я хочу сохранить unordered_set в качестве ключа в unordered_map, это хорошая идея, или я должен использовать std :: set для хранения некоторых данных, а затем использовать std :: map для хранения std :: set в качестве ключа. Что было бы лучше для производительности / поиска?
Любые предложения помогут
Решение
Как и во многих вопросах, связанных с производительностью структуры данных, точный ответ будет зависеть от вашего набора данных.
Учитывая, что вас интересует только производительность поиска, небольшие наборы данных обычно предпочитают использовать упорядоченные версии контейнеров, где «набор данных» означает среднее количество элементов в ваших ключах для типа ключа (набор против unordered_set), и количество элементов (set, value_type) для внешнего типа карты (map против unordered_map). Кстати, ничто не мешает вам смешивать упорядоченные и неупорядоченные контейнеры, такие как unordered_map, value_type>
Еще, единственный способ быть на 100% уверенным, какой контейнер лучше, — это профилировать его с вашими фактическими данными.
Имея это в виду, вот еще несколько деталей:
- Для внешнего контейнера есть хороший шанс, что использование unordered_map обеспечит лучшую производительность поиска, основанную на обычных характеристиках хеш-контейнеров. Тем не менее, существует более тонкое влияние, которое зависит от сравнительной производительности оператора и функции хеша ключевого контейнера.
- Для ключевого контейнера производительность поиска зависит от относительной производительности оператора меньше контейнера (если ваш внешний контейнер является картой) или его хеш-функции (если ваш внешний контейнер — unordered_map).
Я постараюсь опубликовать некоторые реальные тесты, чтобы измерить это позже.
Другие решения
Других решений пока нет …