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?
