如何在 C++ 中的 pair<int，int> 数组上使用upper_bound？

Question

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

代码：

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

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

目前我在索引 p。我想找到数组( = j(的最大索引，这样time[j].second <= time[p].first.
例如。时间 = { (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的返回值存储到int j中时，引发了错误。

根据参考资料，std::upper_bound：

返回一个迭代器，该迭代器指向区域 [first， last( 中大于值的第一个元素，如果未找到此类元素，则返回 last。

因此，要获取找到的元素在time数组中的位置，您需要按如下方式修改代码：

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

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

另外，不要忘记检查此类元素是否存在(即在这种情况下是否返回std::upper_boundtime + 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;
}