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

With reference to Daniel's answer, observe that the comment `//insert into the end position` is incorrect in the `lower_bound` version of the code. It's kind of incorrect even in the `find` version of the code, since the new element is always inserted to its correct position according to the sort order of the `map`. The iterator you pass in is just a hint that will improve performance if it's correct. — Steve Jessop, Nov 01 '13 at 10:55
Why is there a negation for "`key found`" condition in the first case? — Кое Кто, May 30 '23 at 16:16

Daniel Frey · Accepted Answer · 2013-11-01T08:48:46.193

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.

find() vs lower_bound+key_comp

1 Answers1