c++ - STL 排序 vector 查找小于或等于给定值的第一个元素

Question

我有一个对的 vector 。假设是这样的:

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

对按第一个元素排序。

给定一个对，我需要在第一个元素小于或等于给定对的第一个元素的 vector 中找到最后一个对 的索引。如果对于最后一个 对，其他对位于其左侧且具有与第一个元素相同的值，我需要所有这些对中的第一个:

<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 发表评论后更新了答案:

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

现在的答案满足所有您提供的测试用例(我不在这里展示)。希望有帮助! :)

---

附录:

引用 std::lower_bound , std::upper_bound和 std::prev .请注意 std::lower_bound 调用如何使用 std::make_pair 没有 初始化列表，这样它就可以让编译器发挥作用并解决deduce the type .