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

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

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

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

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

По вышеуказанному критерию я должен пройти последний элементfoo.end()-1 вinsert не 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);

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

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() как подсказка вставки. Однако это, очевидно, только эмпирическое наблюдение. Стандарт, как уже говорилось, по-прежнему сбивает с толку в этом аспекте.