c++ - 具有透明比较器的集合是否需要形成一个等价类？

Question

假设我有一个带有这样比较器的集合:

struct prefix_comparator {
    using is_transparent = void;
    struct prefix {
        std::string_view of;
    };
    bool operator()(std::string_view l, std::string_view r) const {
        return l < r;
    }
    bool operator()(std::string_view l, prefix r) const {
        // Only compare up to the size of the prefix
        auto result = l.compare(0, r.of.length(), r.of);
        return result < 0;
    }
    bool operator()(prefix l, std::string_view r) const {
        auto result = r.compare(0, l.of.length(), l.of);
        return result > 0;
    }
};

( Full example usage )

因此 prefix_comparator::prefix{ "XYZ"} 使用此比较器比较等效于以 "XYZ" 开头的任何字符串。在 std::set 中使用它会是 UB 吗？

它不会与类型为 prefix_comparator::prefix 的东西形成等价类，因为 prefix 对象不能相互比较，比如 equiv("XYZABC", prefix{ "XYZ"}) && equiv(prefix{ "XYZ"}, "XYZabc") 但不是 equiv("XYZABC", "XYZabc")。但是该集合不存储 prefix 对象，所以我不知道这是否适用。

它在实践中似乎工作正常(使用 libstdc++ std::set):count() 返回大于 1 的正确值, equal_range 可以返回一个大于一个元素的迭代器范围，等等。我不确定 find 是否可用，因为它只返回一个指向单个元素的迭代器(可能它只返回任意元素？)

Answer 1

来自draft standard .

[associative.reqmts.general]/24.2.7.1

Each associative container is parameterized on Key and an ordering relation Compare that induces a strict weak ordering ([alg.sorting]) on elements of Key.

没有“顶级”要求非 Key 类型元素严格弱排序。

方法和参数是有限制的。这是常用的集合:

(7.20) kl is a value such that a is partitioned ([alg.sorting]) with respect to c(x, kl), with x the key value of e and e in a;

(7.21) ku is a value such that a is partitioned with respect to !c(ku, x), with x the key value of e and e in a;

(7.22) ke is a value such that a is partitioned with respect to c(x, ke) and !c(ke, x), with c(x, ke) implying !c(ke, x) and with x the key value of e and e in a;

(7.23) kx is a value such that

(7.23.1) a is partitioned with respect to c(x, kx) and !c(kx, x), with c(x, kx) implying !c(kx, x) and with x the key value of e and e in a, and

(7.23.2) kx is not convertible to either iterator or const_­iterator; and [...]

这些与 a_tran 一起使用，这是标准用于“Compare 具有 is_transparent 时的关联容器”的快捷方式，描述当您打开 is_transparent 时获得的大多数(全部？)额外方法的要求。

因此，在此之下，重要的部分是实际使用的非键元素实际上使用存储在容器中的实际键对容器进行分区:

a_tran.erase(kx)

122 # Result: size_­type

123 # Effects: Erases all elements in the container with key r such that !c(r, kx) && !c(kx, r) is true.

这意味着您必须检查每个方法要求是否符合预期。计数，例如:

a_tran.count(ke)

150 # Result: size_­type

151 # Returns: The number of elements with key r such that !c(r, ke) && !c(ke, r).

152 # Complexity: log(a_tran.size())+a_tran.count(ke)

所以这里的参数必须是ke，所以传入的具体值必须是关联容器当前内容的一个“nice”分区。