Проблема C ++ 0x: Вставка постоянного времени в std :: set

Согласно эта страница , я могу добиться вставки с постоянным временем, если я использую итератор

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

и position , который я предоставляю напрямую "предшествует" правильной (по порядку) точке вставки.

Теперь меня беспокоит случай, когда я знаю, что значение, которое я вставляю, идет в конце (поскольку оно самое большое), например:

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

В соответствии с указанным выше критерием я должен передать последний элемент foo.end () - 1 в insert not foo.end () . Я правильно понимаю ? Что произойдет, если я передам foo.end () ? Будет ли это вставка O (log n) или O (1) ]. Итак, варианты:

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

Я спрашиваю, потому что я пишу функцию, созданную по шаблону для контейнера. Я хочу вставить элемент (который, как я знаю, является самым большим) в конец любого переданного контейнера. Использование «Вариант A "выше, имеет другое поведение для контейнера, такого как vector [1 198930]:

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

Как предлагает @Bo_Persson, проблема здесь в том, что C ++ 03 говорит «логарифмический в целом, но амортизированная константа, если t вставляется сразу после p». В то время как C ++ 0x говорит «логарифмический в целом, но амортизированная константа, если t вставляется прямо перед p. "

PS: Я использую GCC 4.5 на Ubuntu 11.04 с включенной поддержкой C ++ 0x.

Редактировать: Я провел эмпирические тесты с включенной поддержкой C ++ 0x и отключен и опубликовал результаты в ответе . По сути, можно сделать вывод, что так же хорошо (и, очевидно, безопаснее) предоставить end () в качестве подсказки для вставки. Однако это, очевидно, всего лишь эмпирическое наблюдение. Стандарт, как указано, по-прежнему сбивает с толку в этом аспекте.