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

Question

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

这是否意味着以下形式的代码片段的性能(在我正在研究和模仿Scott Meyer的"有效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第233期和N1780中的讨论.

回想一下,lower_bound使用key不小于指定键upper_bound的第一个元素返回一个迭代器,同时返回一个迭代器到第一个元素,键大于指定键.如果没有钥匙等同于容器中的指定键,然后lower_bound和upper_bound返回同样的事情-一个迭代器,这将是该元素之后的关键,如果它是在地图上.

因此,换句话说,您当前的代码已经在C++ 11规范下正常工作,实际上在C++ 98的缺陷规范下会出错.

Answer 2

是的，它将影响复杂性。提供正确的提示将使insert()摊销后的常数变得复杂，而给出和不正确的提示将迫使地图从头开始搜索位置，从而给出对数复杂度。基本上，无论地图有多大，一个好的提示都会使插入在恒定的时间内进行；如果提示不好，则在较大的地图上插入速度会变慢。

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