De acordo comesta págin, Posso obter uma inserção de tempo constante se eu usar

iterator std::set::insert ( iterator position, const value_type& x );

e aposition iterador que forneço diretamente "precede" o ponto de inserção adequado (em ordem

Agora, o que me preocupa é se eu sei que o valor que estou inserindo vai no final (já que é o maior), por exemplo

set<int> foo = {1, 2, 3};
foo.insert(4); // this is an inefficient insert

De acordo com o critério acima, devo passar o último elementofoo.end()-1 parainsert nã foo.end(). Meu entendimento está correto? O que acontece se eu passarfoo.end()? Será umO(log n) inserção ou umO(1) 1. Então, as opções são:

// Option A
foo.insert(foo.end()-1, 4);

// Option B
foo.insert(foo.end(), 4);

// Safer version of Option A
if(foo.empty())
    foo.insert(4);
else
    foo.insert(foo.end()-1, 4);

Eu pergunto porque estou escrevendo uma função que está modelada no contêiner. Eu quero inserir um elemento (que eu sei que é o maior) no final de qualquer contêiner que for passado. O uso da "Opção A" acima tem um comportamento diferente para um contêiner comovector:

foo.insert(foo.end()-1, 4);
// result is {1, 2, 3, 4} if foo is an std::set
// result is {1, 2, 4, 3} if foo is an std::vector

omo sugere @Bo_Persson, o problema aqui é que o C ++ 03 diz "logarítmico em geral, mas constante amortizada se t for inserido logo após p". enquanto C ++ 0x diz "logarítmico em geral, mas constante amortizada se t for inserido logo antes de p"

PS: Estou usando o GCC 4.5 no Ubuntu 11.04 com suporte a C ++ 0x ativad

Edit: Eu executei testes empíricos com o suporte C ++ 0x ativado e desativado e postou os resultados em uma resposta. Basicamente, a conclusão é que é tão bom (e obviamente mais seguro) fornecerend() como a dica de inserção. No entanto, isso é obviamente apenas uma observação empírica. O padrão, como afirmado, ainda é confuso neste aspect