🗺 std::map или std::unordered_map: Битва за кэш

Когда нам нужно хранить пары «Ключ - Значение», рука сама тянется написать std::map. Это стандарт, это удобно, это сортировка из коробки.

Но с точки зрения производительности std::map это часто худший выбор. Почему?

🌲 1. std::map - Это Дерево (Red-Black Tree)
Каждый элемент в map - это отдельный узел (Node), выделенный в куче (new). Узлы разбросаны по памяти хаотично.

• Чтобы найти элемент, процессор прыгает по указателям: Root -> Left -> Right -> ...
• Каждый прыжок - это потенциальный Cache Miss (промах кэша). Процессор ждет сотни тактов, пока данные подтянутся из RAM.
• Сложность поиска: O(log N).

⚡ 2. std::unordered_map - Это Хеш-таблица
Здесь нет деревьев. Ключ превращается в число (хеш), и мы сразу прыгаем в нужную ячейку массива (Bucket).

• Массивы любят кэш процессора (Cache Locality).
• Сложность поиска: O(1) (в среднем). Это мгновенно.

🐢 Насколько велика разница?
На маленьких объемах (до 100 элементов) разницы почти нет.
Но на 1,000,000 элементов std::unordered_map может быть в 3-5 раз быстрее просто за счет отсутствия прыжков по памяти.

🤔 Когда использовать std::map?
Только в одном случае: Вам жизненно важен порядок ключей.
Например, если вы хотите вывести пользователей по алфавиту или найти диапазон дат (lower_bound / upper_bound).

🚀 Бонус: C++23 std::flat_map
В новом стандарте завезли std::flat_map. Это гибрид: интерфейс как у map (сортированный), но внутри - сплошной вектор.
Это самый быстрый вариант для поиска, но медленный для вставки. Если у вас C++23 - присмотритесь!

💡 Итог: если вам не нужна сортировка, всегда пишите std::unordered_map. Не заставляйте процессор бегать по дереву указателей без причины.

#cpp #stl #optimization #performance #map #hashing #coding #tips

➡️ @cpp_geek