我有这样的结构(类型被简化以延续这一点)，生活在 std::vector:

struct Region {
    int first;
    int count;
    struct Metadata region_metadata;
};

在 vector 中，它们按first排序。如果将first和count相加，则得到下一个区域的first；所以基本上这个结构 vector 描述了连续数字范围的元数据。

现在给定一个整数，我想查找元数据。对区域进行排序后，我可以使用 std::upper_bound。我是这样实现的:

struct Comp
{
    inline bool operator()(const Region &region, int index) const
    {
        return region.first < index;
    }

    inline bool operator()(int index, const Region &region) const
    {
        return index < region.first;
    }
};

这有效，当调用 std::upper_bound 时:

auto iter = std::upper_bound(m_regions.begin(),
                             m_regions.end(),
                             index,
                             Comp());

现在这恰好可以工作，因为 upper_bound 可以在内部选择符合其要求的重载，因为它同时调用 Comp()(Region, int) 和 Comp()(int, Region)(这就是 [](const Region ®, int index){…} 不起作用的原因)。

我实际上是通过在使用我之前提到的 lambda 时跟踪错误消息来提出解决方案的。 docs for std::upper_bound at cppreference.com写下第四个论点:

comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than the second.

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

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

The signature does not need to have const &, but the function object must not modify the objects passed to it. The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly converted to both Type1 and Type2.

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

(cppreference has been fixed 因为我发布了这个问题，谢谢@T.C.)

这里，T 是 std::upper_bound 的第三个参数，ForwardIt 是前两个参数的类型。这句话并没有提到函数对象实际上是一个结构，它重载了它的 operator() 以涵盖“正向”和“反向”情况。

那么在写成的规则中，这是合法的，还是我的特定编译器/标准库组合 (g++ 5.3.1) 的产物？

我对 C++14 或 C++17 的特定答案感兴趣。

完整示例:

#include <algorithm>
#include <iostream>
#include <vector>


struct Region {
    Region(int first, int count, int n):
        first(first),
        count(count),
        n(n)
    {

    }

    int first;
    int count;
    int n; // think struct Metadata
};


struct Comp
{
    inline bool operator()(const Region &region, int index) const
    {
        return region.first < index;
    }

    inline bool operator()(int index, const Region &region) const
    {
        return index < region.first;
    }
};


int main() {
    std::vector<Region> regions;
    regions.emplace_back(0, 10, 1);
    regions.emplace_back(10, 10, 2);
    regions.emplace_back(20, 10, 3);

    const int lookup = 10;

    auto iter = std::upper_bound(
        regions.begin(),
        regions.end(),
        lookup,
        Comp());

    // yes, I omitted error checking here, with error being iter == regions.begin()
    std::cout << lookup << " is in region with n = " << (iter-1)->n << std::endl;
}

最佳答案

Now this happens to work, because upper_bound can internally pick the overload which matches its requirements, as it calls both Comp()(Region, int) and Comp()(int, Region) (which is the reason why a [](const Region &reg, int index){…} would not work).

不，upper_bound 只调用 Comp 的第二个重载。这正是您的(固定 - 感谢@T.C.!)引用的内容:比较器的第一个参数始终是 upper_bound 的第三个参数。应该交换 lambda 的参数。

在 upper_bound/lower_bound 的比较器中重载 operator() 本质上是没有意义的，因为这些算法只会选择一个重载.

operator() 应该像您在使用 equal_range 时显示的那样被重载，并且这样做是合法的，因为比较器(或任何仿函数)与库无关:您只需要确保排序是严格的(即正确的语义)并且重载是明确的。

关于c++ - 我可以合法地使用重载 operator() 的结构作为 std::upper_bound 的比较吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36007500/