c++ - C++0x issue: Constant time insertion into std::set -

according this page, can achieve constant time insertion if use

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

and position iterator provide directly "precedes" proper (in-order) insertion point.

now case i'm concerned if know value i'm inserting goes @ end (since it's largest), e.g.:

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

according above criterion should pass last element foo.end()-1 insert not foo.end(). understanding correct? happens if pass foo.end()? o(log n) insertion or o(1) one. so, options are:

// option foo.insert(foo.end()-1, 4);  // option b foo.insert(foo.end(), 4);  // safer version of option if(foo.empty())     foo.insert(4); else     foo.insert(foo.end()-1, 4); 

i ask because i'm writing function that's templated on container. want insert element (that know largest) end of whatever container passed in. using "option a" above has different behavior container vector:

foo.insert(foo.end()-1, 4); // result {1, 2, 3, 4} if foo std::set // result {1, 2, 4, 3} if foo std::vector 

as @bo_persson suggests, problem here c++03 says "logarithmic in general, amortized constant if t inserted right after p." while c++0x says "logarithmic in general, amortized constant if t inserted right before p."

ps: i'm using gcc 4.5 on ubuntu 11.04 c++0x support enabled.

edit: ran empirical tests c++0x support enabled , disabled , posted results in answer. basically, conclusion it's (and safer) provide end() insertion hint. however, that's empirical observation. standard, stated, still confusing on aspect.

is cheating run test instead of reading through library specifications?

for g++-4.4 -o2 integers 0 <= < 5000000 running times standard insertion are

real    0m14.952s user    0m14.665s sys 0m0.268s 

and running times insertion using end() hint are

real    0m4.373s user    0m4.148s sys 0m0.224s 

insertion @ end() - 1 fast far can tell, more cumbersome use because end() - 1 illegal operation (you have use operator--()) , crashes if set happens empty.

#include <set>  typedef std::set<int> set;  void insert_standard(set& xs, int x) {     xs.insert(x); }  void insert_hint_end(set& xs, int x) {     xs.insert(xs.end(), x); }  int main() {     const int cnt = 5000000;     set xs;     (int = 0; < cnt; i++) {         // insert_hint_end(xs, i);         insert_standard(xs, i);     } }