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

Ответ 1

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

Еще одна разница будет наблюдаться, когда вы будете проходить через контейнеры. set будет доставлять содержимое в отсортированном порядке, а hash_set будет по существу случайным (спасибо Lou Franco).

Изменить: обновление С++ 11 до стандарта С++ ввело unordered_set, которое должно быть предпочтительным вместо hash_set. Производительность будет аналогичной и гарантируется стандартом. "Неупорядоченный" в названии подчеркивает, что итерация его приведет к результатам без особого порядка.

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

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