CODEWITHSUNDEEP
arraysc++11std-pairupperbound
Michelle
Michelle

Reputation: 107

How to use upper_bound on array of pair<int,int> in C++?

I want to use upper_bound on array of pair and that too using a comparator function that compares the second parameter of pair. Please help.

Code:

bool cmp(const pair<int,int> &p1, const pair<int,int> &p2)
{
    return p1.second<p2.second;
}

int subsets(pair<int,int> time[], int p)
{
    if(p == 0)  return 1;
    int j = upper_bound(time, time+p, time[p], cmp) - time;
}


EDIT: I have corrected the return type but I don't seem to get what I wanted as an output.
I have an array of pair<int,int> named time which contains the start and end time as the first and second parameter respectively and sorted according to end time in increasing fashion.

Presently I am at index p. I want to find the maximum index of the array( = j), such that time[j].second <= time[p].first.
Eg.
time = { (1,5), (4,7) , (6, 12) } and if p = 2(0 based indexing) then j should be = 0 (as 5 <= 6 but 7 > 6) but upper_bound gives me j = 2.

How can I achieve this?

Upvotes: 0

Views: 775

Answers (2)

Michelle
Michelle

Reputation: 107

The following code does the job :)

bool compareit(int n, pair<int,int> &p)
{
    return p.second > n;
}

int subsets(pair<int,int> time[], int p)
{
    if(p == 0)  return 1;
    int j = upper_bound(time, time+p, time[p].first, compareit) - time;
}

Upvotes: 0

Zecong Hu
Zecong Hu

Reputation: 3214

There's nothing wrong with your cmp function, the error was raised when you try to store the return value of std::upper_bound into int j.

According to the reference, std::upper_bound:

Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found.

So to obtain the position of the found element in your time array, you need to modify your code as follows:

int j = upper_bound(time, time + p, time[p], cmp) - time;

or equivalently, use the std::distance function.

Also, don't forget to check whether such element exists (i.e. whether std::upper_bound returned time + p in this case).

Upvotes: 1

Related Questions