Согласно этой странице, я могу добиться вставки с постоянным временем, если использую
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);
Я спрашиваю, потому что пишу функцию, созданную по шаблону контейнера. Я хочу вставить элемент (который, как я знаю, является самым большим) в конец любого переданного контейнера. Использование «Варианта A» выше имеет другое поведение для контейнера, такого как 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, проблема здесь в том, что С++ 03 говорит «логарифмический в целом, но амортизированная константа, если t вставляется сразу после p». в то время как C ++ 0x говорит «логарифмический в целом, но амортизированная константа, если t вставляется прямо перед p».
PS: я использую GCC 4.5 на Ubuntu 11.04 с включенной поддержкой C++0x.
Изменить: я провел эмпирические тесты с включенной и отключенной поддержкой С++ 0x и ">опубликовал результаты в ответе. По сути, вывод состоит в том, что так же хорошо (и, очевидно, безопаснее) предоставить end()
в качестве подсказки для вставки. Однако, очевидно, это всего лишь эмпирическое наблюдение. Стандарт, как уже говорилось, все еще сбивает с толку в этом аспекте.