find() vs lower_bound+key_comp

Question

I came across the following question in stackOverflow std::map insert or std::map find?

why is using find() considered inferior to lower_bound() + key_comp() ?

assume I have the following map

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

the suggested answer is to use

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

why is it better than the following?

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

In the second case, notice that if you need to insert the value, the iterator is always myMap.end(). This can not help to improve the performance of the insert operation (except when the new element is inserted at the end, of course). The container needs to find the correct position where to insert the new node, which is usually O(log N).

With lower_bound(), you already found the best hint for the container where to insert the new element and this is the optimization opportunity that the first technique offers. This might lead to a performance close to O(1). You have an additional key comparison, but that is O(1) as well (from the container's perspective).

Since both the initial find() and lower_bound are O(log N), you end up with a O(log N) plus two O(1) operation in the first technique and with two O(log N) operations in the second case.