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

Ответ 1

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

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

Примеры:

задавать:

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

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

Unordered_set:

Ввод: 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 потому что operator< переопределения 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/ fooobar.com/questions/453052/...

Ответ 7

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

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

Ответ 8

Извините, еще одна вещь, заслуживающая внимания в сортировке:

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

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

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

Ответ 9

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

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

Ответ 10

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

Ответ 11

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 основан на hashmap. В справочном ответе я также подтвердил, что с помощью GDB пошагово отлаживаем код.

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

Ответ 12

Если кто-то слишком ленив, чтобы писать unordered_