Efficiency using insert with a map in c++

Question

There's an example on cplusplus.com reference that I'm not understanding.

In the following example, when C is inserted, why is that less efficient than inserting B? What's different about them?

  // second insert function version (with hint position):
  std::map<char,int>::iterator it = mymap.begin();
  mymap.insert (it, std::pair<char,int>('b',300));  // max efficiency inserting
  mymap.insert (it, std::pair<char,int>('c',400));  // no max efficiency inserting

Answer 1

That example is using the overload of insert that accepts a "hint" iteration to say in what part of the backing binary tree the new element should be inserted. The example implies it - which was initialised to begin() - is as good a hint as possible when inserting into an empty table, but less useful (perhaps not useful at all) when inserting a second element.

I'm not sure why that website (which historically hasn't been very good - I trust cppreference.com far more), makes the efficiency assertion about the insertion of 'b'. The Standard's requirements are (with p being the hint iterator):

The element is inserted as close as possible to the position just prior to p.

A position prior to begin() doesn't exist. If anything, it's likely to be more efficient not to provide a hint for the first insert.

During the second insert, 'b' is at begin() and we don't want to insert 'c' "just prior to" 'b', so the Standard's "as close as possible" kicks in and the insert can be expected to grope around for the correct place despite the hint.

More generally, hints get useful when the tree has many more elements, so the insert implementation can just check a couple elements near the hint to ensure order without working its way down from the root of the binary tree.