Implementation of lower_bound on vector pairs

Question

I know we need to include some compare function in order to achieve this.

But not able to write for this one.

For example:

Elements of vector={(2,4),(4,2),(5,1),(5,3)}

to find=5

lower_bound() should return 2

code->

#define pp pair<int,int>

bool cmp(const pp &l,const pp &r) {
    return l.first < r.first;
}

int main() {
   vector<pp> v;
   sort(v.begin(), v.end(), cmp);
   int id=(int)(lower_bound(v.begin(), v.end(), ??) - v.begin());
}

Answer 1

Pairs (just like tuples) compare lexicographically anyway. You don't need to define any special comparators for this.

And since you're using lower_bound you'll be searching for the first element that does not compare less than the val you're searching, so you should use a min value as the second pair element. To sum up, all can be done in "two" lines of code :

sort(v.begin(),v.end());
auto id = distance(v.begin(), lower_bound(v.begin(),v.end(), 
       make_pair(5, numeric_limits<int>::min())) );

---

Some Notes :

1. Use std::distance to calculate the number of elements between two iterators
2. The return type of std::distance is an unsigned type. Unless you need negative indexing (Python like syntax for "count from the end" indexes) it's a good practice to keep your indexes unsigned.