查找（）VS LOWER_BOUND + key_comp

我碰到以下问题排在计算器 std::map insert or std::map find?查找（）VS LOWER_BOUND + key_comp

为什么使用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)); 
}

来源

2013-11-01 Angel Koh

参照Daniel的回答，请注意''lower_bound'版本的代码中注释'//插入结束位置'不正确。即使在代码的“find”版本中，它也是不正确的，因为新元素总是按照map的排序顺序插入到正确的位置。你传入的迭代器只是一个提示，如果它是正确的，将提高性能。 –

在第二种情况下，请注意，如果你需要插入值，迭代器总是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-01 08:42:32

查找（）VS LOWER_BOUND + key_comp

回答

相关问题