According to this page, I can achieve constant time insertion if I use
iterator std::set::insert ( iterator position, const value_type& x );
and the position iterator I provide directly "precedes" the proper (in-order) insertion point.
Now the case I'm concerned with is if I know that the value I'm inserting goes at the end (since it's the largest), e.g.:
set<int> foo = {1, 2, 3};
foo.insert(4); // this is an inefficient insert
According to the above criterion I should pass the last element foo.end()-1 to insert not foo.end(). Is my understanding correct? What happens if I pass foo.end()? Will it be a O(log n) insertion or a O(1) one. So, the options are:
// 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);
I ask because I'm writing a function that's templated on the container. I want to insert an element (that I know is the largest) to the end of whatever container is passed in. Using "Option A" above has a different behavior for a container like 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
As @Bo_Persson suggests, the problem here is that C++03 says "logarithmic in general, but amortized constant if t is inserted right after p." while C++0x says "logarithmic in general, but amortized constant if t is inserted right before p."
PS: I'm using GCC 4.5 on Ubuntu 11.04 with C++0x support enabled.
Edit: I ran empirical tests with C++0x support enabled and disabled and c++ stl insert set complexity-theory