vector<pair<int,int>>的上界

Question

我正在尝试在一个vector<pair<int,int>>上使用upper_bound，就像这样：

vector<pair<int,int>> data;
auto up = upper_bound(data.begin(), data.end(), 0);

我使用VS2012时遇到了以下错误：

error C2784: 'bool std::operator <(const std::vector<_Ty,_Alloc> &,const std::vector<_Ty,_Alloc> &)' : could not deduce template argument for 'const std::vector<_Ty,_Alloc> &' from 'const int'

为什么它要将一个 const int 与一个 pair<int,int> 进行比较？我尝试编写自己的比较函数，但这并没有改变任何东西。如果我这样做，编译器会尝试将 pair<int,int> 转换为 const int。

- Simon-Okp

---

在这个调用中 upper_bound(data.begin(), data.end(), 0);，最后一个参数显然是一个数字。请展示你的比较器。 - Bartek Banachewicz

Answer 1

您正在将一对值与数字进行比较，但是没有预定义的比较运算符可用。您可能想将其更改为以下内容：

auto up = upper_bound(data.begin(), data.end(), make_pair(0, 0));

如果您的应用程序中有特定的逻辑用于将一对数字与单个数字进行比较，您可以提供自己的比较函数：

或者，如果您的应用程序中有特定的逻辑用于将一对数字与单个数字进行比较，则可以提供自己的比较函数：

bool cmp(int n, pair<int, int> const& p)
{
    // For instance...
    return ((p.first < n) && (p.second < n));
}

int main()
{
    vector<pair<int,int>> data;
    auto up = upper_bound(data.begin(), data.end(), 0, cmp);
}

- Andy Prowl

---

这难道不是完全等价的吗？ - Lightness Races in Orbit

哈哈，我已经找了一个小时的复杂问题，但我甚至没有想到去看参数（我只是输入0来进行测试）。对于这个问题感到抱歉，现在感到很尴尬！ - Simon-Okp

@LightnessRacesinOrbit：是的，没错。那里的“例如…”是为了说明它可以被更改。 - Andy Prowl

Answer 2

为什么要用一个常量整数与一对值进行比较？

因为您告诉它那样做。 您的比较值为“0”，但您的元素类型为“pair ”。

咦！显而易见！

也许您正在寻找：

auto up = upper_bound(data.begin(), data.end(), make_pair(0, 0));

- Lightness Races in Orbit

Answer 3

std::upper_bound 的第三个参数是返回的迭代器所指向的元素应该大于的值。您如何确定一个 std::pair<int,int> 是否大于 0？

您传递的几乎肯定应该是一个 std::pair<int,int>：

auto up = upper_bound(data.begin(), data.end(), std::make_pair(first, second));

然而，first和second取决于您要解决的问题。

- Joseph Mansfield

---

取决于情况。在某些情况下，搜索数字绝对是有意义的。实际上，我正好有这样一个用例（我正在搜索包含线上某一点的区间）。 - Konrad Rudolph

@Light 不，为什么？标准库中的排序数组搜索算法是专门为这种用例设计的（查看比较函数的文档）。这是一种合法的用法，实际上是一种相当常见的用法 - 它是表示范围集合的一种简单有效的方式。 - Konrad Rudolph

Answer 4

如果您正在搜索不兼容的类型，则需要在比较函数中特别小心。引用自cppreference.com：

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

[…] The type Type1 must be such that an object of type T can be implicitly converted to Type1. The type Type2 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type2.​

- 在您的情况下，Type1 = int，Type2 = std::pair<int，int>。这应该能解决问题。

- Konrad Rudolph