Thread: map: lower_bound, upper_bound, and insert

I'm trying to figure out the most efficient way to use map.insert with the iterator parameter. I'm not certain if the iterator should be immediately before the new element or immediately after the new element.

insert - C++ Reference suggests "if [the iterator is] set to the element that precedes the actual location where the element is inserted, [it] makes for a very efficient insertion operation."
map<Key, Data, Compare, Alloc> simply says that the iterator is provided as a hint with no indication of which way would be better.
The first answer provided at std::map insert or std::map find? - Stack Overflow seems to suggest that lower_bound is returning the correct iterator to be used as the parameter to insert. However, lower_bound never returns an iterator to a location that would be before the new element; it's always the same location or after.

[tangentially-related rant]
IMO, lower_bound is a terrible name for what it does. upper_bound makes sense; the returned iterator is the first element with a key > the provided key. lower_bound returns almost exactly the same thing, except the keys could be equivalent. Suppose you've got a set of numbers { 1, 4, 8, 12 } and you ask for the lower_bound of 7. Isn't 4 the answer that most of us would expect? I mean, the upper_bound of 7 is 8. Who would expect that the lower_bound == upper_bound for an element that doesn't exist in the collection?! Blah.
[/rant]

Is there a standard correct position for the iterator, or is this implementation-dependent?

I am still not sure of the real answer to this, but I recall doing some empirical testing on specific implementations as mentioned in this CodeGuru thread: efficient map(/set) insertion.

Thanks laserlight. That answered my question.

Originally Posted by pianorain

[tangentially-related rant]
IMO, lower_bound is a terrible name for what it does. upper_bound makes sense; the returned iterator is the first element with a key > the provided key. lower_bound returns almost exactly the same thing, except the keys could be equivalent. Suppose you've got a set of numbers { 1, 4, 8, 12 } and you ask for the lower_bound of 7. Isn't 4 the answer that most of us would expect? I mean, the upper_bound of 7 is 8. Who would expect that the lower_bound == upper_bound for an element that doesn't exist in the collection?! Blah.
[/rant]

I agree that they are not the best names in the world, but all you need to remember is that if you insert an element at the position indicated by lower or upper bound, you don't break the ordering.

lower_bound is the lower bound of equal_range, upper_bound is the upper bound. Therefore, when the element is not present, lower_bound must equal upper_bound so that the equal_range is empty.
By the way, C++0x clarifies the insertion hint. For a value t and an iterator p, c.insert(p, t) has the following complexity:
(N3092 Table 99)
"logarithmic in general, but amortized constant if t is inserted right before p."