C/C++ | Вопросы собесов on Telegram: “🤔 В чем разница map и unordered

🤔 В чем разница map и unordered_map?

std::map и std::unordered_map – оба являются ассоциативными контейнерами в C++, но они устроены по-разному и имеют разные скорости работы.

🚩Как устроены контейнеры?

🟠`std::map` – красно-чёрное дерево (сбалансированное BST)
Все ключи хранятся упорядоченно.
Операции insert, erase, find выполняются за O(log n).
Упорядоченность важна, если требуется поиск в диапазоне (lower_bound, upper_bound).

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m;
    m[2] = "B";
    m[1] = "A";
    m[3] = "C";

    for (const auto& [key, value] : m) {
        std::cout << key << " -> " << value << '\n'; 
    }
}

Вывод (отсортирован!)

1 -> A  
2 -> B  
3 -> C

🟠`std::unordered_map` – хеш-таблица
Нет сортировки, но поиск выполняется быстро – O(1) (в среднем).
Использует хеш-функцию, поэтому доступ к элементам зависит от хеширования.
Может быть медленным при коллизиях (O(n) в худшем случае).

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> um;
    um[2] = "B";
    um[1] = "A";
    um[3] = "C";

    for (const auto& [key, value] : um) {
        std::cout << key << " -> " << value << '\n';
    }
}

Вывод (порядок непредсказуем!)

2 -> B  
1 -> A  
3 -> C

🚩Когда использовать `map`, а когда `unordered_map`?

🟠Используйте `std::map`, если:
Нужно сортированное хранение ключей.
Требуется поиск по диапазону (lower_bound, upper_bound).
Хеш-функция для ключей сложна или недоступна (например, std::pair без кастомного хешера).

Ставь 👍 и забирай 📚 Базу знаний