Каково различие между набором и hashset в C++ STL?
Когда я должен выбрать один по другому? Есть ли какие-либо указатели, которые Вы рекомендовали бы для использования правильных контейнеров STL?
5 ответов
hash_set - это расширение, не являющееся частью стандарта C ++. Поиск должен быть O (1), а не O (log n) для набора , поэтому в большинстве случаев это будет быстрее.
Еще одно отличие будет видно при итерации по контейнерам. set доставит содержимое в отсортированном порядке, а hash_set будет по существу случайным (спасибо Лу Франко).
Редактировать: В обновлении C ++ 11 до стандарта C ++ был введен unordered_set , который следует использовать вместо hash_set . Производительность будет аналогичной и гарантирована стандартом. «Неупорядоченный» в названии подчеркивает, что его повторение не приведет к результатам в произвольном порядке.
Еще одна вещь, о которой следует помнить, - это то, что с hash_set вы должны предоставить хеш-функцию, тогда как set требует только функцию сравнения ('<'), которую легче определить (и предопределено для собственных типов).
stl :: set реализовано как двоичное дерево поиска.
hashset реализовано как хэш стол.
Основная проблема здесь в том, что многие люди используют stl :: set , думая, что это хеш-таблица с поиском O (1), чего нет и нет. У него действительно есть O (log (n)) для поиска. Помимо этого, прочтите о двоичных деревьях и хэш-таблицах, чтобы лучше понять структуры данных.
Я не думаю, что кто-то ответил на другую часть вопроса.
Причиной использования hash_set или unordered_set является обычно O(1) время поиска. Я говорю "обычно", потому что время от времени, в зависимости от реализации, хэш может быть скопирован в более крупный хэш-массив, или хэш-ведро может содержать тысячи записей.
Причина использовать набор - если вам часто нужен самый большой или самый маленький член набора. Хэш-массив не имеет порядка, поэтому нет быстрого способа найти наименьший элемент. Дерево имеет порядок, поэтому найти наибольший или наименьший элемент можно очень быстро. O(log n) для простого дерева, O(1), если оно содержит указатели на концы.
Набор hash_set может быть реализован с помощью хеш-таблицы, которая содержит в основном O (1) операций, тогда как набор реализуется каким-либо деревом (AVL, красно-черный и т. Д.) С O (log n) операций. , но находятся в отсортированном порядке.
Edit: Я написал, что деревья O (n). Это совершенно неверно.