std::lower_bound() vs std::map::lower_bound()

Question

The lower_bound function of algorithms library takes a forward iterator and returns the lower bound. It works fine for vectors but when i used it for a map, I got compiler error. My doubt is that std::map supports bidirectional iterators which can obviously act as forward iterators, so why std::lower_bound(map.begin(),map.end(),int value) doesn't work but the member function of map class, map.lower_bound(int value) works for a map? Here is some example code for reference

    #include<bits/stdc++.h>
    using namespace std;
    int main(){
    
    vector<int>v = {1,1,1,2,3,4,2,3,2,5,6,12,12,9};
    map<int,int>mp;
    for(auto x:v)mp[x]++;
    
    for(int i=0;i<15;i++){
    
    auto it = mp.lower_bound(i); // this works
 //   auto it = lower_bound(mp.begin(),mp.end(),i) //this doesn't work
    if(it!=mp.end())
    cout<<i<<" lower bound is "<<it->first<<" and its frequency in vector is "<<it->second<<endl;
    
    
    }
    
    
    return 0;
    }

Answer 1

Everything you need can be found in the documentation

• std::lower_bound
• std::map::lower_bound.

std::lower_bound expects a sorted range of N values of type T given by the iterators and T value to search for.

• If the iterators are random access, it is the slightly modified binary search to get the lower bound as specified. Therefore the complexity is logarithmic in N.
• If the iterators are just bidirectional, the complexity is linear in N.

std::map<Key,Value>::lower_bound expects Key key to search for and the complexity is logarithmic in N because it performs binary search on the red-black tree, although that is technically an implementation detail.

So, std::lower_bound does not work for you because the map contains pair<const Key,Value>, not just Key, the following will work

auto it = lower_bound(mp.begin(),mp.end(),std::pair<const int,int>{9,1});

but the complexity is linear and of course it is not very useful if you only want to search using keys. std::map::lower_bound solves both problems. Although the latter could have been solved by custom Compare function.

This pattern is common to all containers and algorithms, there is e.g. generic std::find and specialized container::find for each container that is better.

Please, do not use #include<bits/stdc++.h>.

Answer 2

The member function exists because the algorithm's function doesn't work. The element type of map is pair<const K, T>. The algorithm's function isn't aware of how to compare only key parts of values.