find()vs lower_bound + key_comp

Question

我在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));
}

Answer 1

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

有了lower_bound(),你已经找到了容器最好的提示,其中插入新的元素,这是优化的机会,第一个技术提供.这可能会导致性能接近O(1).你有一个额外的密钥比较,但也是O(1)(从容器的角度来看).

由于初始值find()和lower_boundO都是O(log N),因此在第一种技术中最终得到O(log N)加上两次O(1)运算,在第二种情况下得到两次O(log N)运算.