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

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

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

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

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

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

Примечание: 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 вернет значения в " случайный порядок.

Ответ 2

Еще одно отличие (хотя и не связанное с производительностью) заключается в том, что set вставка не делает недействительными итераторы, а unordered_set может вставляться, если она вызывает переименование. На практике это довольно незначительная проблема, поскольку ссылки на фактические элементы остаются в силе.