А как ты представляешь себе поиск ключа в красно-черном дереве за O(1)? Это тоже самое, что найти всю ноду с ключом и значением. Нужно O(1) - юзай хэш-таблицы
Да. То что std::map по дефолту сортирует по ключам, и отдельно есть unordered, это странно. Сегодня вот на это напоролся и написал неэффективный алгоритм =\
Нет. Не странно. map/set - упорядоченное отображение/множество
Справедливости ради, в словах map и set нет ни намека на какое-либо упорядочение элементов, и множество (set) в математическом смысле тоже не подразумевает существование операции сравнения у элементов. Так что тут причины чисто исторические, так как в C++98 были только упорядоченные множества, а совместимость нарушать нельзя.
Справедливости ради, в словах map и set нет ни намека на какое-либо упорядочение элементов
Да. Но если смотреть на пару: множество / неупорядоченное множество - то уже закрадывается мысль, что если во втором случае неупорядоченное, то значит в первом упорядоченное.