Menu
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));
}
734
lower_bound in c++ stl returns an iterator even when the element is not present.
map lower_bound() function in C++ STL Parameters: This function accepts a single mandatory parameter key which specifies the element whose lower_bound is to be returned. Return Value: The function returns an iterator pointing to the key in the map container which is equivalent to k passed in the parameter.
The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val. This means that the function returns an iterator pointing to the next smallest number just greater than or equal to that number.
C++ map find() function is used to find an element with the given key value k. If it finds the element then it returns an iterator pointing to the element. Otherwise, it returns an iterator pointing to the end of the map, i.e., map::end().
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.
132
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
