C++ std::map

hash_map был уже в SGI STL в 96м.

А как ты представляешь себе поиск ключа в красно-черном дереве за O(1)? Это тоже самое, что найти всю ноду с ключом и значением. Нужно O(1) - юзай хэш-таблицы

оу, я думал std::map это и есть HashMap...

А справочник не осилил? до 20 не было метода вообще. У мэпа сложность логарифмическая, там не может быть О1.

PS: А в unordered_map::find() всегда О1 было.

Нет, это std::unordered_map

наименования от бога, как остальное в этом поделии

наименования от бога

+1.

Да. То что std::map по дефолту сортирует по ключам, и отдельно есть unordered, это странно. Сегодня вот на это напоролся и написал неэффективный алгоритм =\

ps: плюсы видел разок в дверной глазок

А какие проблемы с наименованием?

• map - отображение
• set - множество
• если приставка unordered - значит неупорядоченный контейнер

То, что там под капотом, бинарное дерево или хэш таблица - стандарт не определяет.

Один разок можно и в шоколадный глазок! (И нужно!) А как этот метод должен работать, что за магия такая?

То что std::map по дефолту сортирует по ключам, и отдельно есть unordered, это странно

Нет. Не странно.

map/set - упорядоченное отображение/множество. Раз упорядоченное - значит бинарное дерево под капотом.

unordered_map/unordered_set - неупорядоченное отображение/множество. Раз неупорядоченное - значит под капотом хэш таблица.

По-моему все логично.

Нет. Не странно. map/set - упорядоченное отображение/множество

Справедливости ради, в словах map и set нет ни намека на какое-либо упорядочение элементов, и множество (set) в математическом смысле тоже не подразумевает существование операции сравнения у элементов. Так что тут причины чисто исторические, так как в C++98 были только упорядоченные множества, а совместимость нарушать нельзя.

map - отображение

map - карта https://fivethirtyeight.com/wp-content/uploads/2015/10/kappa.png

Справедливости ради, в словах map и set нет ни намека на какое-либо упорядочение элементов

Да. Но если смотреть на пару: множество / неупорядоченное множество - то уже закрадывается мысль, что если во втором случае неупорядоченное, то значит в первом упорядоченное.

а должно было быть: множество и упорядоченное множество

Где же ты был, когда C++98 принимали!

Справедливости ради, в словах map и set нет ни намека на какое-либо упорядочение элементов

На хеширование тоже нет.

Да, поэтому ОП не должен был его подразумевать

Ну это если перевести в лоб - то это карта. Но также есть такое слово:

mapping - отображение

А те не думаешь, что это те же яйца?

У неё с рождения был метод count, который работал точно так же, но названием отпугивал квадратно-гнездовых жавистов.

а с чего ты взял что O(1) будет всегда быстрее иных сложностей? — она вполне может быть намного дольше чем O(n).