roblema @ C ++ 0x: inserción de tiempo constante en std :: set

De acuerdo aesta págin, Puedo lograr una inserción de tiempo constante si uso

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

y elposition iterador que proporciono directamente "precede" al punto de inserción adecuado (en orden).

Ahora el caso que me preocupa es si sé que el valor que estoy insertando va al final (ya que es el más grande), por ejemplo

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

De acuerdo con el criterio anterior, debería pasar el último elementofoo.end()-1 ainsert n foo.end(). ¿Es correcto mi entendimiento? ¿Qué pasa si pasofoo.end()? ¿Será unaO(log n) inserción o unaO(1) uno. Entonces, las opciones son:

// 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);

Pregunto porque estoy escribiendo una función que está en plantilla en el contenedor. Quiero insertar un elemento (que sé que es el más grande) al final de cualquier contenedor que se pase. El uso de la "Opción A" anterior tiene un comportamiento diferente para un contenedor 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 sugiere @Bo_Persson, el problema aquí es que C ++ 03 dice "logarítmico en general, pero constante amortizado si t se inserta justo después de p". mientras que C ++ 0x dice "logarítmico en general, pero constante amortizado si t se inserta justo antes de p".

PS: estoy usando GCC 4.5 en Ubuntu 11.04 con soporte C ++ 0x habilitado.

Edit: Ejecuté pruebas empíricas con soporte C ++ 0x habilitado y deshabilitado yposicionó los resultados en una respuesta. Básicamente, la conclusión es que es igual de bueno (y obviamente es más seguro) proporcionarend() como pista de inserción. Sin embargo, eso obviamente es solo una observación empírica. El estándar, como se dijo, sigue siendo confuso en este aspecto.