find() vs lower_bound+key_comp

Question

>我在堆栈溢出中遇到了以下问题std：：map insert or 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));
}

Answer 1

在第二种情况下，请注意，如果需要插入值，迭代器始终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） 操作。