我们可以使用异构查找比较器在STL关联容器上执行“部分匹配”搜索吗？

Question

因此，我研究了对STL的关联容器(自C++14)中的异构查找的支持，并对我们可以做什么和不应该做什么感到有点困惑。

下面的片段

#include <algorithm>
#include <iostream>
#include <set>

struct partial_compare : std::less<>
{
    //"full" key_type comparison done by std::less
    using less<>::operator();

    //"sequence-partitioning" comparison: only check pair's first member
    bool operator ()(std::pair<int, int> const &lhs, int rhs) const
    {
        return lhs.first < rhs;
    }

    bool operator ()(int lhs, std::pair<int, int> const &rhs) const
    {
        return lhs < rhs.first;
    }
};

int main()
{
    //Using std::set's lookup
    {
        std::cout << "std::set's equal_range:\n";
        std::set <std::pair<int, int>, partial_compare> s{{1,0},{1,1},{1,2},{1,3},{2,0}};

        auto r = s.equal_range (1);

        for (auto it = r.first; it != r.second; ++it)
        {
            std::cout << it->first << ", " << it->second << '\n';
        }

        std::cout << "std::set's lower_bound + iteration on equivalent keys:\n";
        auto lb = s.lower_bound(1);

        while (lb != std::end(s) && !s.key_comp()(lb->first, 1) && !s.key_comp()(1, lb->first))
        {
            std::cout << lb->first << ", " << lb->second << '\n';
            ++lb;
        }
    }

    //Using algorithms on std::set
    {
        std::cout << "std::equal_range\n";
        std::set <std::pair<int, int>> s{{1,0},{1,1},{1,2},{1,3},{2,0}};

        auto r = std::equal_range (std::begin(s), std::end(s), 1, partial_compare{});
        for (auto it = r.first; it != r.second; ++it)
        {
            std::cout << it->first << ", " << it->second << '\n';
        }
    }
    return 0;
}

在用clang-5/libc++编译时产生以下输出：

std::set's equal_range:
1, 1
std::set's lower_bound + iteration on equivalent keys:
1, 0
1, 1
1, 2
1, 3
std::equal_range
1, 0
1, 1
1, 2
1, 3

下面是用gcc-7.1.0编译的：

std::set's equal_range:
1, 0
1, 1
1, 2
1, 3
std::set's lower_bound + iteration on equivalent keys:
1, 0
1, 1
1, 2
1, 3
std::equal_range
1, 0
1, 1
1, 2
1, 3

通过阅读最初的N3465提案，我认为我在这里所做的应该很好，并且在概念上应该与提案的初始示例相同:在查找过程中进行“部分匹配”，依赖于“序列分区的概念”。

现在，如果我的理解是正确的，那么标准中的最终结果是N3657，但这似乎并没有改变这个概念，因为它“只是”关注于确保只在提供比较器"is_transparent“时才提供异构查找成员模板。

所以，我真的不明白为什么在clang/libc++中使用std：：set的equal_range成员模板不会产生gcc的相同结果或类似的"lower_bound +扫描“。我是不是遗漏了什么，用这种方式使用异构查找实际上违反了标准(然后clang是对的，equal_range和lower_bound +扫描之间的区别可能是UB造成的)，还是clang/libc++是错误的？

编辑:在阅读了现在被接受的答案之后，我找到了libc++的相关libc++。

还有一个关于equal_range模板成员在libc++和libstdc++ 这里 on之间的行为差异的具体问题，这样我在搜索时就找不到了。

不确定这是应该删除还是关闭，因为我已经链接的那个没有一个被接受的答案。

Answer 1

这是libc++中的一个bug :它的范围实现 (at r315179)在找到“相等”元素时立即返回两个迭代器，即使进行了异构比较。