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;
}
Everything you need can be found in the documentation
std::lower_bound expects a sorted range of N values of type T given by the iterators and T value to search for.
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>.