std::map insert() hint location: difference betwee

Question

On cplusplus' entry on map::insert() I read about the location one could add as a hint for the function that the "function optimizes its insertion time if position points to the element that will precede the inserted element" for c++98, while for c++11 the optimization occurs "if position points to the element that will follow the inserted element (or to the end, if it would be the last)".

Does this mean that the performance of code snippets of the following form (which are abundant in the legacy code I'm working on and modeled after Scott Meyer's "Effective STL", item 24) were affected in switching to a C++11-compliant compiler?

auto pLoc = someMap.lower_bound(someKey);
if(pLoc != someMap.end() && !(someMap.key_comp()(someKey, pLoc->first)))
    return pLoc->second;
else
    auto newValue = expensiveCalculation();
    someMap.insert(pLoc, make_pair(someKey, newValue));  // using the lower bound as hint
    return newValue;

What would be the best way to improve this pattern for use with C++11?

Answer 1

a snapshot of working lambda function for your reference.

    auto create_or_get_iter = [this] (const K& key) {

        auto it_upper = m_map.upper_bound(key);
        auto it_effective = it_upper == m_map.begin() ? it_upper : std::prev(it_upper);
        auto init_val = it_effective->second;

        if (it_effective == m_map.begin() || it_effective->first < key) {
            return m_map.insert(it_effective, std::make_pair(key, init_val));
        } else {
            it_effective->second = init_val;
            return it_effective;
        }

    };

Answer 2

I am thinking the correct C++11-style hint insertion might be as follows:

iterator it = table.upper_bound(key);   //upper_bound returns an iterator pointing to the first element that is greater than key
if (it == table.begin() || (--it)->first < key) {
    // key not found path
    table.insert(it, make_pair(key, value));
}
else {
    // key found path
    it->second = value;
}

Answer 3

Yes, it will affect the complexity. Giving the correct hint will make insert() have amortized constant complexity, while giving and incorrect hint will force the map to search for the position from the beginning, giving logarithmic complexity. Basically, a good hint makes the insertion happen in constant time, no matter how big your map is; with a bad hint the insertion will be slower on larger maps.

The solution is, apparently, to search for the hint with upper_bound instead of lower_bound.

Answer 4

The C++98 specification is a defect in the standard. See the discussion in LWG issue 233 and N1780.

Recall that lower_bound returns an iterator to the first element with key not less than the specified key, while upper_bound returns an iterator to the first element with key greater than the specified key. If there is no key equivalent to the specified key in the container, then lower_bound and upper_bound return the same thing - an iterator to the element that would be after the key if it were in the map.

So, in other words, your current code already works correctly under the C++11 spec, and in fact would be wrong under C++98's defective specification.