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

Question

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

Answer 1

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

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

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

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

Как краткое резюме:

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

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

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

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