SexyBeast SexyBeast - 11 days ago 5
C++ Question

STL sorted vector find first element less than or equal to given value

I have a vector of

pairs
. Suppose it is like this:

vector<pair<int,int>> vec = { {1,12}, {1,5}, {1,6}, {1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} };


The
pairs
are sorted by first element.

Given a
pair
, I need to find the index of the last
pair
in the vector whose first element is less than or equal to first element of the given pair. If for that last
pair
, other pairs lie to its left with the same value of the first element, I need the first of all those pairs:

<4,10> => 4 (vec[4] is <3,9>, the elements with the largest first value less than or equal to 4 are those with first element as 3, and there are 4 pairs with a 3 in the first element, at indices 4-7, so return the first of those pairs)

<0,10> => -1, since no element exists to its right.

<1,6> => 0 (vec[0] is <1,12>. There is no pair whose first element is less than 1, and there are 4 pairs, including <1,6> whose first element is 1. So we need the first of these 4 pairs.)

<23,81> => 12 (vec[12] is <20,8>)


Condition: I need to use only standard algorithms like
upper_bound
,
binary_search
and
lower_bound
. I tried this, but it is failing badly:

vector<pair<int,int>> vec = { {1,12}, {1,5}, {1,6},{1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} };

auto i = std::lower_bound(vec.begin(), vec.end(), make_pair<int,int>(4,10),
[](const pair<int,int>& f1, const pair<int,int>& f2) { return f1.first < f2.first; });

cout << i-vec.begin();

Answer

Since you want the first pair, you maybe want to combine lower and upper bound?

#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>

using namespace std;

int main()
{
    vector<pair <int,int> > vec = { {1,12}, {1,5}, {1,6}, {1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} };

    auto u_it = std::upper_bound(vec.begin(), vec.end(), make_pair<int,int>(4, 10),
        [](const pair<int,int>& f1, const pair<int,int>& f2) { return f1.first < f2.first; });

    if(u_it == vec.begin())
        cout << "-1\n";

    auto l_it = std::lower_bound(vec.begin(), u_it, make_pair(prev(u_it)->first, 10),
        [](const pair<int,int>& f1, const pair<int,int>& f2) { return f1.first < f2.first; });

    cout << l_it - vec.begin() << "\n";
    return 0;

}

Output:

Georgioss-MacBook-Pro:~ gsamaras$ g++ -Wall -std=c++0x main.cpp 
Georgioss-MacBook-Pro:~ gsamaras$ ./a.out 
4

PS - answer updated after WhozCraig's comment:

you want to use it = std::upper_bound(beg,end) to find the first strictly-greater element, and if that answers non-begin, then use std::lower_bound(beg,it) to find the lowest-matching ordinal of the element whose value is pulled from (it-1).

The answer now satisfies all the test cases you have provided (I am not showing it here). Hope that helps! :)


Appendix:

Ref for std::lower_bound, std::upper_bound and std::prev. Please notice how the std::lower_bound call uses std::make_pair without an initializing list, so that it lets the compiler come into play and resolve deduce the type.

Comments