Std::map insert()提示位置:c++98和c++11的区别

Question

在cplusplus的map::insert()上的条目中，我读到可以添加的位置作为函数的提示，对于c++98，"如果position指向将在插入元素之前的元素，则函数优化其插入时间"，而对于c++11，优化发生"如果position指向将在插入元素之后的元素(或到最后，如果它将是最后一个)"。

这是否意味着以下形式的代码片段(在我正在处理的遗留代码中大量存在，并以Scott Meyer的"Effective STL"为模型，第24项)的性能在切换到兼容c++ 11的编译器时受到影响?

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;

在c++ 11中改进这种模式的最好方法是什么?

Answer 1

c++ 98规范是标准中的一个缺陷。参见LWG issue 233和N1780中的讨论。

回想一下，lower_bound返回一个迭代器到key不小于指定键的第一个元素，而upper_bound返回一个迭代器到key大于指定键的第一个元素。如果容器中没有与指定键相等的键，则lower_bound和upper_bound返回相同的内容——指向映射中键后的元素的迭代器，如果键在映射中，则该元素为。

因此，换句话说，您当前的代码在c++ 11规范下已经可以正常工作，而实际上在c++ 98有缺陷的规范下是错误的。

Answer 2

是的，这会影响复杂度。给出正确的提示将使insert()具有平摊常数复杂度，而给出不正确的提示将迫使映射从一开始搜索位置，从而产生对数复杂度。基本上，无论你的地图有多大，一个好的提示都能让插入在固定时间内发生;如果提示不好，在较大的地图上插入会比较慢。

显然，解决方案是用upper_bound而不是lower_bound来搜索提示。

Answer 3

我认为正确的c++ 11风格提示插入可能如下:

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 4

工作lambda函数的快照供您参考。注意:m_map不应该为空。如果映射为空，在哪里添加元素是很容易知道的。

    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;
        }
    };