STL排序向量找到小于或等于给定值的第一个元素

Question

我有一个向量pairs。假设是这样的：

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

在pairs由第一个元素进行排序。

给定a pair，我需要找到pair向量中最后一个元素的索引，该向量的第一个元素小于或等于给定对的第一个元素。如果对于最后一个pair，其他对以第一个元素的相同值位于其左侧，那么我需要所有这些对中的第一个：

<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>)

条件：我只需要使用标准的算法，如upper_bound，binary_search和lower_bound。我试过了，但是失败很严重：

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 1

由于您需要第一对，因此您可能想结合上下限？

#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, *prev(u_it),
        [](const pair<int,int>& f1, const pair<int,int>& f2) { return f1.first < f2.first; });

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

}

输出：

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

PS-在WhozCraig发表评论后更新了答案：

您想使用it = std::upper_bound(beg,end)查找第一个严格大于的元素，如果答案是非开始，则使用std::lower_bound(beg,it)查找值从中拉出的元素的最低匹配序号(it-1)。

现在的答案满足所有的测试用例，您所提供（我不显示在这里）。希望有帮助！:)

附录：

引用std :: lower_bound，std :: upper_bound和std :: prev。请注意，在没有初始化列表的情况下std::lower_bound调用是如何使用的，以便让编译器起作用并解析推断类型。std::make_pair