Como é determinada a complexidade temporal da busca de um elemento em std::map?

No std::map é utilizado uma árvore binária balanceada (geralmente uma árvore vermelho-preto), portanto a busca por um elemento tem uma complexidade de tempo de O(log n), onde n é o número de elementos no contêiner. Isso ocorre porque, para buscar, o elemento é comparado com os nós da árvore, indo para a subárvore esquerda ou direita, reduzindo a área de busca pela metade a cada passo.