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 ()?

Suppose 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, note that if you need to insert a value, the iterator is always myMap.end() . This will not help improve the performance of the insert operation (unless a new item is inserted at the end, of course). The container needs to find the correct position where to insert a new node, which is usually equal to O (log N).

With lower_bound() you have already found the best hint for the container where you want to insert a new element, and this is the optimization opportunity offered by the first technique. This can lead to a performance close to O (1). You have an additional key comparison, but it is also O (1) (in terms of container).

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