Edit Question - KnowledgeHub

Title Body

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 <a href="ht

Tags (comma-separated) Cancel