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

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