10

我在stackOverflow std::map insert 或 std::map find中遇到了以下问题 ？

为什么使用 find() 被认为不如 lower_bound() + key_comp() ？

假设我有以下地图

map<int, int> myMap;
myMap[1]=1; 
myMap[2]=3;
myMap[3]=5;
int key = xxx; //some value of interest.
int value = yyy;

建议的答案是使用

map<int, int>::iterator itr = myMap.lower_bound(key);
if (itr != myMap.end() && !(myMap.key_comp()(key, itr->first)))
{
    //key found. 
    // do processing for itr->second
    // 
}else {
    //insert into the end position 
    myMap.insert (itr, map<int, int>::value_type(key, value));
}

为什么它比以下更好？

map<int, int>::iterator itr = myMap.find(key);
if (itr != myMap.end())
{
    //key found. 
    // do processing for itr->second
    // 
}else {
    //insert into the end position 
    myMap.insert (itr, map<int, int>::value_type(key, value));
}
4

1 回答 1

13

在第二种情况下，请注意，如果您需要插入值，迭代器总是myMap.end(). 这无助于提高插入操作的性能（当然，在最后插入新元素时除外）。容器需要找到插入新节点的正确位置，通常为 O(log N)。

使用，您已经找到lower_bound()了插入新元素的容器的最佳提示，这是第一种技术提供的优化机会。这可能导致接近 O(1) 的性能。您还有一个额外的关键比较，但这也是 O(1) （从容器的角度来看）。

由于初始find()和lower_bound都是 O(log N)，因此在第一种技术中最终得到 O(log N) 加上两个 O(1) 操作，在第二种情况下得到两个 O(log N) 操作。

于 2013-11-01T08:42:32.337 回答