Какова временная сложность операции поиска элемента по ключу в std::map?

В стандартной библиотеке C++ контейнер std::map реализован как сбалансированное бинарное дерево (обычно красно-черное дерево). Поэтому операция поиска элемента по ключу имеет временную сложность O(log n), где n — количество элементов в контейнере.

Пример использования поиска:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Найден элемент: " << it->second << std::endl;
    } else {
        std::cout << "Элемент не найден" << std::endl;
    }
    return 0;
}