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

Нашел этот хороший вопрос, который аналогичен, но не совсем так, поскольку он говорит о Java, который имеет различную реализацию хеш-таблиц, благодаря наличию синхронизированных аксессуаров/мутаторов Различия между HashMap и Hashtable?

Так в чем же разница в реализации С++ для set и unordered_set? Конечно, этот вопрос можно распространить на карту vs unordered_map и т.д. Для других контейнеров С++.

Вот моя первоначальная оценка

set. Хотя стандарт явно не требует, чтобы он был реализован как деревья, ограничение временной сложности, запрашиваемое для его операций для find/insert, означает, что он всегда будет реализован как дерево. Обычно это дерево RB (как видно из GCC 4.8), которое сбалансировано по высоте. Поскольку они сбалансированы по высоте, у них есть предсказуемая сложность времени для find()

Плюсы: Компактный (по сравнению с другими DS в сравнении)

Con: Сложность времени доступа - O (lg n)

unordered_set. Хотя стандарт явно не требует, чтобы он реализовывался как деревья, ограничение временной сложности, запрашиваемое для его операций для find/insert, означает, что он всегда будет реализован как хеш-таблица.

Плюсы:

Быстрее (promises амортизируется O (1) для поиска)
Легко конвертировать базовые примитивы в потокобезопасные, по сравнению с tree-DS

Минусы:

Поиск не гарантируется O (1) Тройной худший случай - O (n)
Не такой компактный, как дерево. (для практических целей коэффициенты нагрузки никогда не 1)

Примечание: O (1), для хэш-таблицы исходит из предположения, что нет столкновения. Даже с коэффициентом нагрузки 0,5 каждая вставка второй переменной приводит к столкновению. Можно заметить, что коэффициент нагрузки хэш-таблицы обратно пропорционален количеству операций, необходимых для доступа к элементу в нем. Больше мы уменьшаем # operations, более редкую хеш-таблицу. Когда сохраненный элемент имеет размер, сопоставимый с указателем, тогда накладные расходы довольно значительны.

Изменить: поскольку большинство из них говорит, что вопрос содержит в себе достаточный ответ, я меняю вопрос на "Я пропустил какую-либо разницу между картой/набором для анализа производительности, которую нужно знать?"

Ответ 1

Я думаю, вы вообще ответили на свой вопрос, однако, это:

Не такой компактный, как дерево. (для практических целей коэффициенты нагрузки никогда не 1)

не обязательно верно. Каждый node дерева (мы будем считать его красно-черным деревом) для типа T использует пространство, равное по крайней мере 2 * pointer_size + sizeof(T) + sizeof(bool). Это может быть 3 * pointer size в зависимости от того, содержит ли дерево указатель parent для каждого дерева node.

Сравните это с хэш-картой: будет пустое пространство массива для каждой хэш-карты из-за того, что load factor < 1, как вы сказали. Однако, предполагая, что хэш-карта использует односвязные списки для цепочки (и, действительно, нет никакой реальной причины), каждый вставленный элемент принимает только sizeof(T) + pointer size.

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

Для любого элемента T, который имеет небольшой размер (так, любой базовый тип), преобладает размер указателей и других служебных данных. При коэффициенте нагрузки > 0.5 (например) std::unordered_set может действительно использовать меньше памяти, чем эквивалент std::set.

Другой большой недостающей точкой является тот факт, что итерация через std::set гарантированно приведет к упорядочению от наименьшего к наибольшему на основе данной функции сравнения, в то время как итерация через std::unordered_set вернет значения в " случайный порядок.

Ответ 1

Ответ 2