Kaip nustatoma elementų paieškos laiko sudėtingumas std::map?

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