В чем разница между set и hashset в C ++ STL?

Question

Когда я должен выбрать один над другим? Есть ли какие-либо указатели, которые вы бы порекомендовали для использования правильных контейнеров STL?

Answer 1

hash_set - это расширение, которое не является частью стандарта C ++. Поиск должен быть O (1), а не O (log n) для set, поэтому в большинстве случаев он будет быстрее.

Другое отличие будет видно, когда вы будете перебирать контейнеры. set доставит содержимое в отсортированном порядке, в то время как hash_set будет в основном случайным (спасибо Лу Франко).

Редактировать: В C ++ 11 введено обновление стандарта C ++ unordered_set, которое следует отдавать предпочтение вместо hash_set. Производительность будет аналогичной и гарантируется стандартом. «Неупорядоченный» в имени подчеркивает, что повторение его приведет к результатам в произвольном порядке.

Answer 2

stl::set реализован в виде двоичного дерева поиска. hashset реализован в виде хеш-таблицы.

Основная проблема заключается в том, что многие люди используют stl::set, думая, что это хеш-таблица с поиском O (1), которой нет, и не имеет. Он действительно имеет O (log (n)) для поиска. Кроме того, читайте о бинарных деревьях и хеш-таблицах, чтобы получить лучшее представление о структурах данных.

Answer 3

Следует также помнить, что для hash_set необходимо предоставить хеш-функцию, тогда как для набора требуется только функция сравнения ('<'), которую легче определить (и предопределенная для собственных типов).

Answer 4

Не думаю, что кто-то еще ответил на другую часть вопроса.

Причиной использования hash_set или unordered_set является обычно время поиска O (1). Обычно я говорю, потому что очень часто, в зависимости от реализации, хеш может быть скопирован в более крупный хеш-массив, или хеш-корзина может содержать тысячи записей.

Причина использования набора в том, что вам часто требуется самый большой или самый маленький член набора. У хэша нет порядка, поэтому нет быстрого способа найти самый маленький элемент. У дерева есть порядок, поэтому самое большое или самое маленькое очень быстро. O (log n) для простого дерева, O (1), если оно содержит указатели на концах.

Answer 5

hash_set будет реализован с помощью хеш-таблицы, в которой в основном O (1) операций, тогда как набор реализуется с помощью дерева некоторого вида (AVL, красный черный и т. Д.), Которые имеют O (log n) операций , но в отсортированном порядке.

Редактировать: я написал, что деревья O (n). Это совершенно неправильно.