set и unordered_set

Иногда,хранение именно в виде упорядоченного массива очень важно с точки зрения алгоритма. Например, найдите значение (int), ближайшее к заданному, если значения хранятся в unodered_set.

Иногда, написание адекватной задаче хеш функции - невозможно, например, при хранении double.

Иногда, ожидаемый набор данных достаточно мал. О(1) не всегда быстрее O(Log(n)), можно гарантировать только, что существует такой размер набора данных, на котором O(1) будет быстрее. На практике, часто встречаются ситуации, когда ожидаемое число значений 3-5 штук.

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