Зачем кому-то использовать set вместо unordered_set?

Представляем C ++ 0x, unordered_setкоторый доступен во boostмногих других местах. Я понимаю, что unordered_setэто хеш-таблица со O(1)сложностью поиска. С другой стороны, setэто не что иное, как дерево со log(n)сложностью поиска. Зачем кому-то использовать setвместо unordered_set? т.е. есть ли необходимость в этом set?

Когда для кого-то, кто хочет перебирать элементы набора, порядок имеет значение.

Неупорядоченные наборы должны оплачивать свое среднее время доступа O (1) несколькими способами:

• setиспользует меньше памяти, чем unordered_setдля хранения того же количества элементов.
• Для небольшого количества элементов поиск в файле setможет быть быстрее, чем поиск в unordered_set.
• Несмотря на то, что многие операции выполняются быстрее в среднем для unordered_set, они часто гарантируют лучшую сложность наихудшего случая для set(например insert).
• Такая set сортировка элементов полезна, если вы хотите получить к ним доступ по порядку.
• Вы можете лексикографически сравнивать разные setс с <, <=, >и >=. unordered_sets не требуются для поддержки этих операций.

Всякий раз, когда вы предпочитаете дерево хеш-таблице.

Например, хеш-таблицы в худшем случае имеют значение «O (n)». O (1) - средний случай. В худшем случае деревья - "O ( log n)".

Используйте набор, когда:

1. Нам нужны упорядоченные данные (отдельные элементы).
2. Нам нужно будет распечатать / получить доступ к данным (в отсортированном порядке).
3. Нам нужен предшественник / преемник элементов.

Используйте unordered_set, когда:

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

Примеры:

задавать:

Ввод: 1, 8, 2, 5, 3, 9

Выход: 1, 2, 3, 5, 8, 9

Неупорядоченный_набор:

Ввод: 1, 8, 2, 5, 3, 9

Вывод: 9 3 1 8 2 5 (возможно, этот порядок зависит от хеш-функции)

Главное отличие:

Примечание: (в некоторых случаях setудобнее) например, используя в vectorкачестве ключа

set<vector<int>> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});

for(const auto& vec:s)
    cout<<vec<<endl;   // I have override << for vector
// 1 2
// 1 3 

Причина vector<int>может быть такой же ключевой, setпотому что vectorпереопределение operator<.

Но если вы используете, unordered_set<vector<int>>вам нужно создать хеш-функцию для vector<int>, потому что вектор не имеет хеш-функции, поэтому вы должны определить ее, например:

struct VectorHash {
    size_t operator()(const std::vector<int>& v) const {
        std::hash<int> hasher;
        size_t seed = 0;
        for (int i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
        return seed;
    }
};

vector<vector<int>> two(){
    //unordered_set<vector<int>> s; // error vector<int> doesn't  have hash function
    unordered_set<vector<int>, VectorHash> s;
    s.insert({1, 2});
    s.insert({1, 3});
    s.insert({1, 2});

    for(const auto& vec:s)
        cout<<vec<<endl;
    // 1 2
    // 1 3
}

вы можете видеть, что в некоторых случаях unordered_setвсе сложнее.

В основном цитируется по: https://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/ https://stackoverflow.com/a/29855973/6329006

Поскольку std :: set является частью Стандартного C ++, а unordered_set - нет. C ++ 0x НЕ является стандартом, как и Boost. Для многих из нас важна мобильность, а это значит, что нужно придерживаться стандарта.

Рассмотрим алгоритмы Sweepline. Эти алгоритмы совершенно не работают с хеш-таблицами, но прекрасно работают со сбалансированными деревьями. Чтобы дать вам конкретный пример алгоритма Sweepline, рассмотрим алгоритм фортуны. http://en.wikipedia.org/wiki/Fortune%27s_algorithm

Еще одна вещь в дополнение к тому, что уже упоминали другие люди. Хотя ожидаемая амортизированная сложность для вставки элемента в unordered_set составляет O (1), время от времени она будет принимать O (п) , поскольку потребности хэш-таблицы , чтобы быть перестроена (количество ковшей необходимо изменить) - даже с «хорошая» хеш-функция. Точно так же, как вставка элемента в вектор время от времени требует O (n), потому что базовый массив необходимо перераспределить.

Вставка в набор всегда занимает не более O (log n). В некоторых приложениях это может быть предпочтительнее.

g++ 6.4 stdlibc ++ упорядоченный и неупорядоченный набор тестов

Я протестировал эту доминирующую реализацию Linux C ++, чтобы увидеть разницу:

Полная информация о тестах и ​​их анализ приведены по адресу: Какова основная структура данных набора STL в C ++? и я не буду их здесь повторять.

«BST» означает «протестировано с помощью, std::setа« хэш-карта »означает« протестировано с помощью » std::unordered_set. «Куча» - это то, std::priority_queueчто я проанализировал в: Куча против двоичного дерева поиска (BST)

Вкратце:

• график ясно показывает, что в этих условиях вставка хэш-карты всегда была намного быстрее, когда элементов более 100 тыс., и разница растет по мере увеличения количества элементов

  Цена такого увеличения скорости состоит в том, что вы не можете эффективно перемещаться по порядку.

• кривые ясно показывают, что заказанный std::setоснован на BST и на std::unordered_setоснове хэш-карты. В справочном ответе я дополнительно подтвердил, что GDB пошагово отлаживал код.

Аналогичный вопрос для mapvs unordered_map: есть ли преимущество использования map над unordered_map в случае тривиальных ключей?

Простите меня, еще кое-что, что стоит отметить в отношении отсортированного свойства:

Если вам нужен диапазон данных в контейнере, например: вы сохранили время в наборе , и вам нужно время с 2013-01-01 по 2014-01-01.

Для unordered_set это невозможно.

Конечно, этот пример будет более убедительным для случаев использования между map и unordered_map .

Хотя этот ответ может быть запоздалым на 10 лет, стоит отметить, что он std::unordered_setтакже имеет недостатки в безопасности.

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

Это можно использовать для очень эффективных и элегантных атак типа «отказ в обслуживании».

Многие (большинство?) Реализации языков, которые используют хэш-карты внутри компании, столкнулись с этим:

• Javascript
• PHP
• Ява

Я бы сказал, что удобно иметь отношения, если вы хотите преобразовать их в другой формат.

Также возможно, что при более быстром доступе время для построения индекса или памяти, используемой при создании и / или доступе к нему, больше.

Если вы хотите, чтобы все было отсортировано, вы должны использовать set вместо unordered_set. unordered_set используется вместо набора, когда порядок хранения не имеет значения.