我可以合法地使用带有重载operator()的结构作为比较std :: upper_bound吗？

Question

我有这样的结构(简化的类型来承载这一点),生活在std::vector:

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

在向量中,它们按顺序排列first.如果添加first和count,你得到的first下一个区域的; 所以基本上这个结构向量描述了连续数字范围的元数据.

现在给出一个整数,我想查找元数据.由于区域已分类,我可以使用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 &reg, int index){…}是行不通的).

我实际上通过在使用前面提到的lambda时追踪错误消息来提出解决方案.cppreference.com上std :: upper_bound的文档写下了第四个参数:

比较函数对象(即满足Compare要求的对象),如果第一个参数小于第二个参数,则返回true.

比较函数的签名应等效于以下内容:

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

签名不需要const &,但函数对象不得修改传递给它的对象.类型Type1和Type2 必须使得类型的对象T可以被隐式转换为两个Type1和Type2,和类型的对象ForwardIt可以被解除引用,然后隐式转换为两个Type1和Type2.

类型Type1必须是类型的对象T可以隐式转换为Type1.类型Type2必须使得类型的对象ForwardIt可以被解除引用然后隐式转换为Type2.

(自我发布此问题以来,cppreference 已得到修复,感谢@TC)

这里T是第三个参数std::upper_bound,ForwardIt是前两个参数的类型.这个引用没有谈到函数对象实际上是一个结构,它重载它operator()以覆盖"前进"和"反向"情况.

那么在Rules-As-Written中,这是合法的,还是我特定的编译器/标准库组合(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;
}

Answer 1

现在,这种情况发生的工作,因为upper_bound可以在内部挑选相匹配的要求,超载,因为它同时呼吁 Comp()(Region, int)和Comp()(int, Region)(这就是为什么一个原因[](const Region &reg, int index){…}是行不通的).

不,upper_bound只有电话Comp的第二次超载.这正是你的(固定 - 感谢@TC!)引用的内容:比较器的第一个参数始终是第三个参数upper_bound.应该交换lambda的参数.

operator()在比较器内部重载upper_bound/ lower_bound本质上没有意义,因为这些算法只能选择一个重载.

operator()应该像你在使用时所显示的那样超载equal_range,这样做是合法的,因为比较器(或任何仿函数)的内部细节与库无关:你只需要确保订购是严格(即正确的语义)和明确的重载.