и std::unordered_map? Если они все равно по идее хранят пары ключ-значения в виде без строгой последовательности (так как хэшируют значения)?
std::map не хэширует никакие значения (а правильнее, конечно, ключи) Там они как раз строго упорядочены (в смысле отношения порядка <) Как следствие - логарифмический поиск, вставка, etc.
Разные реализации, map - красно-чёрное дерево, unordered_map - хэш-таблица.
А как же std::hash<>?
std::map хранит ключи в строго упорядоченной последовательности.
понятно, думал там хэш-таблица используется. спасибо
А где ты его в std::map увидел? Там как раз есть аргумент шаблона Compare = std::less<Key>
похоже перепутал. Но вроде смотрел в стандартной библиотеке и там в мапе был std::hash. может я путаю с чем-то другим
я так и понял, спасибо)
С std::unordered_map как раз: "std::unordered_map - cppreference.com" https://en.cppreference.com/w/cpp/container/unordered_map "std::map - cppreference.com" https://en.cppreference.com/w/cpp/container/map
К слову, стандарт не регламентирует метод реализации, а только асимптотику операций и интерфейс Но обычно (да и в принципе я иных реализаций не встречал), как Илья верно заметил, std::map - RB-дерево, std::unordered_map - хэш-таблица
Обсуждают сегодня