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());
}

I would suggest `typedef std::pair pp;` instead of macro definition. — timrau, Jun 01 '14 at 15:22
@user2826957 Yes, but it's not the appropriate way to do it. This is precisely what `typedef`s are for. — Joseph Mansfield, Jun 01 '14 at 15:33
@user2826957 “Macro definition works too!” – No it does not, outside of your trivial example. This has been explained to death on here and elsewhere. — Konrad Rudolph, Jun 01 '14 at 15:39

score 15 · Answer 1 · edited May 23 '17 at 12:17

15

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 :

Use std::distance to calculate the number of elements between two iterators
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.

edited May 23 '17 at 12:17

Community

1
1

answered Jun 01 '14 at 17:25

Nikos Athanasiou

29,616
15
87
153

Can you explain how `numeric_limits::min()` works? – asn Feb 01 '19 at 16:21
@KPMG ```numeric_limits``` provides information on numerical types. ```min()``` is a static function returning the smallest number representable by ```T``` (here: ```T``` = ```int```). Likewise, ```numeric_limits::max()``` provides the largest number representable by the type ```T```. These are, for example, very useful when writing functions looking for minima or maxima. I would guess that ```numeric_limits::max()``` simply sets all the bits of an int to 1. – RL-S Jun 12 '20 at 09:33

score 7 · Answer 2 · answered Jun 01 '14 at 15:22

7

Since you don't care about the second value of pp, just construct a temporary pp object with any value as the second element.

int id = std::lower_bound(v.begin(), v.end(), pp(5, 0), cmp) - v.begin();

answered Jun 01 '14 at 15:22

timrau

22,578
4
51
64

1

Better to use `std::numeric_limits::min()` instead of `0`. – Jarod42 Jun 01 '14 at 15:42

P0W · Answer 3 · 2014-06-01T15:47:46.460

I think you should compare the pairs as per definition of lower_bound So,

   typedef pair<int,int> pp;
   //...

   int id=(int)(lower_bound(v.begin(),v.end(), 
                pp(5,std::numeric_limits<int>::min())), //Value to compare
                [](const pp& lhs, const pp& rhs)       // Lambda
                {
                    return lhs < rhs ;                //  first argument < second
                }
                 ) - v.begin()
               );

score 1 · Answer 4 · answered Feb 11 '21 at 18:52

You can use lower_bound on vector of pairs with custom compare operator .

You need to pass four arguments in that case like this :-

it1 = iterator position from where to search
it2 = iterator position till where to search

lower_bound (it1 ,it2 , finding_element, your_comparator )

auto myComp = [&](pair<int,string> e1, pair<int,string> e2) {
if(e1.second!=e2.second)
    return e1.second<e2.second;
else
    return e1.first<e2.first;
};
 
void Show_sample_code()
{
    vector<pair<int,string>> data={{1, "sahil"}, {2, "amin"}};
    sort(data.begin(), data.end(), myComp);
    pair<int, string> p={1,"sahil"};
    auto it=lower_bound( data.begin(), data.end(), p, myComp ) ;
    if(it!=data.end())
         cout<<"found at index="<<distance(data.begin(), it)<<endl;
    else
    cout<<"notfound"<<endl;
return;
}

Implementation of lower_bound on vector pairs

4 Answers4