如何在 C++ 中对 <int,int> 数组使用 upper_bound？

Question

我想在 pair 数组上使用 upper_bound 并且也使用比较器函数来比较 pair 的第二个参数。请帮忙

代码:

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

编辑：我已经更正了 return 类型，但我似乎没有得到我想要的输出。
我有一个名为 time 的 pair<int,int> 数组，其中分别包含开始时间和结束时间作为第一个和第二个参数，并根据结束时间以递增方式排序。

目前我在指数p。我想找到数组的最大索引（= j），这样 time[j].second <= time[p].first.
例如
time = { (1,5), (4,7) , (6, 12) } 并且如果 p = 2（基于 0 的索引）则 j 应该 = 0（因为 5 <= 6 但 7 > 6）但是 upper_bound 给我 j = 2.

我怎样才能做到这一点？

Answer 1

您的 cmp 函数没有任何问题，当您尝试将 std::upper_bound 的 return 值存储到 int j 时出现错误。

根据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.

所以要获取找到的元素在你的time数组中的位置，你需要修改你的代码如下：

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

或等效地，使用 std::distance 函数。

此外，不要忘记检查这样的元素是否存在（即在这种情况下是否 std::upper_bound returned time + p）。

Answer 2

以下代码可以完成工作:)

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

如何在 C++ 中对 <int,int> 数组使用 upper_bound？

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

arrays

c++11

std-pair

upperbound