std :: map insert（）提示位置：C++ 98和C++之间的区别11

On cplusplus' entry on map::insert()我读了关于可以添加的位置，作为函数的提示，“函数优化插入时间position指向之前的元素插入的元素“for C++ 98，而对于C++ 11则优化发生”if if position指向的元素将跟在插入的元素（或结尾，if这将是最后一次）“。std :: map insert（）提示位置：C++ 98和C++之间的区别11

这是否意味着以下形式的代码片段的性能（这些代码片段在我正在处理的遗留代码中丰富并在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一起使用的最佳方法是什么？

来源

2015-09-24 mr_T

这是一个梦幻般的非兼容性。伟大的工作，C++。 –

请参见[LWG问题233]（http://wg21.link/lwg233）和[N1780]（http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html ）。我不确定是否存在实际实现C++ 98规范的实现。 –

@LightnessRacesinOrbit：那么你喜欢bug与C++ 98的兼容性问题，就像Wine承诺Windows API一样？曾经有一次在Windows中存在另一个严重的安全漏洞，在Wine中发现了同样的漏洞，这当然是完全不同的相同API规范的实现。这有点令人印象深刻，但我宁愿ISO修复C++ 98中的缺陷，而不是将它们传播到永恒。 –

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

回想lower_bound返回一个迭代器与主要不小于指定的键少的第一个元素，同时upper_bound返回一个迭代器与主要大于指定键时，第一元件。如果在容器中没有与指定键相同的键，则lower_bound和upper_bound返回相同的内容 - 如果元素位于映射中，则返回之后的元素的迭代器。因此，换句话说，当前的代码已经在C++ 11规范下正常工作，事实上在C++ 98的有缺陷的规范下会出错。

来源

2015-09-24 10:32:32

很好的答案！我只想补充一点，旧规范不允许在新的密钥小于任何现有密钥（即插入在前面）时提供提示，而end（）对任何内容都没有用处。通过修复，提示迭代器与传递给序列容器的insert（）的迭代器的工作方式相同，这可以解决这个问题。 –

@ArneVogel是的，这是在N1780开头提到的。 –

是的，它会影响复杂性。给出正确的提示将使insert()具有分期不变的复杂性，而给出和不正确的提示将迫使地图从头开始搜索位置，从而给出对数复杂度。基本上，不管你的地图有多大，一个好的提示都会使插入时间不变，不好的提示在较大的地图上插入会变慢。

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

来源

2015-09-24 10:12:07 SingerOfTheFall

我想正确的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; 
}

来源

2017-08-17 19:17:53

std :: map insert（）提示位置：C++ 98和C++之间的区别11

回答

相关问题