带透明比较器的std::set是否需形成等价类？合规性咨询

先给出定义的带透明特性的prefix_comparator比较器代码：

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 {
        // 仅比较到前缀的长度
        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;
    }
};

该比较器中，prefix_comparator::prefix{ "XYZ" }会被视为与所有以"XYZ"开头的std::string_view等价。现在需要明确：将其用于std::set是否会触发未定义行为（UB）？

核心问题分析 #

该比较器无法与prefix_comparator::prefix类型形成合法的等价类：例如equiv("XYZABC", prefix{ "XYZ" })和equiv(prefix{ "XYZ" }, "XYZabc")均成立，但equiv("XYZABC", "XYZabc")不成立。不过std::set中并未存储prefix对象，这让很多人疑惑此问题是否会影响容器的行为。

实际测试表现 #

基于libstdc++的std::set测试显示：

• count()会返回正确的大于1的值
• equal_range()能返回包含所有匹配前缀元素的迭代器范围
• 但find()仅返回单个元素的迭代器，返回的可能是任意一个匹配前缀的元素

是否触发未定义行为？ #

答案分两种情况：

1. 仅使用std::string_view类型操作容器时：比如插入std::string_view元素、用std::string_view查找、遍历容器等，此时比较器仅在std::string_view之间进行比较，而operator()(std::string_view, std::string_view)实现的是标准字典序小于，完全满足std::set要求的严格弱序，这部分操作不会触发UB。

2. 使用透明接口传入prefix类型参数时：比如调用find(prefix{"XYZ"})、count(prefix{"XYZ"})等，此时比较器需要跨类型比较，而等价关系的传递性被破坏（如前面的"XYZABC"、prefix{"XYZ"}、"XYZabc"的例子），违反了C++标准对比较器的严格弱序要求，这属于未定义行为。

实际测试中libstdc++的表现看似正常，但这只是特定实现的行为，标准并不保证这种情况的结果可预期，其他编译器或标准库实现可能出现异常、崩溃或错误结果。而find()传入prefix时返回的元素是未指定的，也属于UB的范畴。

内容的提问来源于stack exchange，提问作者Artyer