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

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

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

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

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

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

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

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

Плюсы:

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

Минусы:

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

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

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

3 Solutions collect form web for “в чем разница между set и unordered_set в C ++?”

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

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

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

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

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

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

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

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

Юуши уже давно проецирует пространственную эффективность и другие точки; просто несколько других вопросов, о которых я прокомментирую …

O (1), для hash-таблицы исходит из предположения, что нет столкновения.

Это не правда. То, что означает O (1), заключается не в том, что первая попытка поиска всегда будет успешной, а в том, что в среднем требуется постоянное количество попыток, а не что-то, что растет с ростом числа значений. Например, с unordered_set или … _map , max_load_factor умолчанию имеет значение 1.0 при построении, и если коэффициент загрузки приближается к тому, что при хорошей хеш-функции среднее число элементов, хеш которых равно одному ведру, будет около 2 независимо от того, как многие значения указаны в таблице.

Даже с коэффициентом нагрузки 0,5 каждая вставка второй переменной приводит к столкновению.

Правда, но это не так страшно, как вы могли бы интуитивно ожидать: средняя длина цепи 2 при коэффициенте загрузки 1.0 неплохая.

Можно заметить, что коэффициент нагрузки hash-таблицы обратно пропорционален количеству операций, необходимых для доступа к элементу в нем. Больше мы уменьшаем # operations, более редкую хеш-таблицу.

Там определенно корреляция (она не обратная).

  • Как создать trie в c #
  • Как отменить односвязный список, используя только два указателя?
  • вставить, удалить, max в O (1)
  • Эффективная реализация неизменяемого (двойного) LinkedList
  • Как бы вы реализовали кеш LRU в Java?
  • Как вы проверяете двоичное дерево поиска?
  • Удаление среднего узла из одного связанного списка, когда указатель на предыдущий узел недоступен
  • Interesting Posts

    Как сделать блок submitP () метода ThreadPoolExecutor, если он насыщен?

    Каков ваш любимый подход к совместному использованию cookie для перекрестных доменов?

    Как вы видите нижнюю часть действительно высоких ячеек в Excel?

    Есть ли больше для интерфейса, чем правильные методы

    Как удалить все COM-порты из командной строки в Windows 7?

    Создание нескольких файлов журналов различного содержания с помощью log4j

    Могу ли я переместить свою домашнюю папку в Mac OS X?

    Сериализация объекта в XML

    Как перебирать папки и переименовывать расширения в пакетном файле?

    LINQ: использование INNER JOIN, Group и SUM

    Зачем начинать с диска C в современных вычислениях?

    Установить диапазон для элементов в GridLayoutManager с помощью SpanSizeLookup

    отображение AM и PM в маленькой букве после форматирования даты

    Усечение длинных строк с помощью CSS: возможно?

    CSS-преобразование текста используется на всех шапках

    Давайте будем гением компьютера.