关联容器中透明比较的传递性保证

Question

假设我们有一个带有自定义 Key 和传递比较器 Less 的有序容器，我们在其中进行查找，如下所示：

struct Key {
    int a, b;
    auto operator <=> (const Key&) const noexcept = default;
};

struct Less {
    bool operator ()(const Key& lhs, const Key& rhs) const noexcept {
        return lhs < rhs;
    }

    using is_transparent = void;
    bool operator ()(const Key& lhs, int rhs) const noexcept {
        return lhs.a < rhs;
    }
    bool operator ()(int lhs, const Key& rhs) const noexcept {
        return lhs < rhs.a;
    }
};

set<Key, Less> s = {{1, 1}, {1, 2}, {2, 1}, {2, 2}, {3, 1}, {3, 2}};
auto [begin, end] = s.equal_range(2);

现在的问题是：s.equal_range(2) 是由 c++ 标准保证 return 范围包含元素 {2, 1}, {2, 2} 还是有一些基于传递性的 UB？

换句话说：透明传递性的标准 guarantees/requirements 与有序容器中密钥传递性的 guarantees/requirements 有什么不同吗？

Answer 1

s.equal_range(ke) 定义为等同于 std::make_pair( s.lower_bound(ke), s.upper_bound(ke));

和std::set应该根据comp(x, ke)和!comp(ke, x)进行划分（c(x, ke)意味着!c(ke, x)）。

有关正式要求，请参阅 container.requirements#associative.reqmts.general-8。

所以在你的情况下你很好

{{1, 1}, {1, 2},   {2, 1}, {2, 2},   {3, 1}, {3, 2}}
//        x < 2  |    !(x < 2)
//                    !(2 < x)     |    2 < x
//

关联容器中透明比较的传递性保证

Transitivity guarantee for transparent comparisons in associative containers

c++

c++-standard-library