Como é avaliada a complexidade temporal da operação de inserção de um elemento em std::map?

A inserção de um elemento em std::map geralmente tem uma complexidade de tempo de O(log n), onde n é o número de elementos no contêiner. Isso ocorre porque std::map é implementado como uma árvore binária balanceada (geralmente uma árvore vermelho-preto), e a operação de inserção requer a busca pela posição para o novo elemento, o que leva um tempo logarítmico.