🤔 Какая сложность работы с map и unordered_map?

В std::map и std::unordered_map используются разные структуры данных, поэтому их операции (insert, find, erase) имеют разную сложность.

🚩Почему `std::map` медленнее?

std::map – это самобалансирующееся красно-чёрное дерево, где все операции (insert, find, erase) выполняются за O(log n).

std::map<int, std::string> m;
m[10] = "ten";  // O(log n)
m[5] = "five";  // O(log n)
m[20] = "twenty";  // O(log n)
m.find(5);  // O(log n)

Дерево std::map выглядит так

        10
       /  \
      5    20

🚩Почему `std::unordered_map` быстрее?

std::unordered_map – это хеш-таблица, где insert, find, erase работают за O(1) в среднем.

std::unordered_map<int, std::string> um;
um[10] = "ten";  // O(1)
um[5] = "five";  // O(1)
um[20] = "twenty";  // O(1)
um.find(5);  // O(1)

Внутри std::unordered_map выглядит так (разбито по бакетам)

Bucket 0:  ---
Bucket 1:  ---
Bucket 2:  (10, "ten")
Bucket 3:  (5, "five")
Bucket 4:  (20, "twenty")

🚩Когда `std::unordered_map` становится медленным (`O(n)`)?

В худшем случае все элементы попадают в один бакет (из-за плохой хеш-функции), тогда поиск превращается в O(n).

std::unordered_map<int, std::string> um;
um[1] = "one";
um[2] = "two";
um[3] = "three";

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