std::unordered_set的EmplaceOrMerge实现疑问及替代方案咨询

MSVC专属扩展的兼容性 #

微软标准库中_In_place_key_extractor的特殊逻辑是非标准的MSVC独有的优化，不属于C标准的要求。GCC的libstdc、Clang的libc++等其他主流标准库实现都没有这个处理。

根据C++标准，std::unordered_set::emplace的行为是：将传入的参数转发给元素的构造函数。如果容器中已经存在等效元素，标准库实现可能会先构造一个临时T对象来完成哈希计算和相等性比较——此时你的右值t会被移动构造这个临时对象，导致t进入有效但状态未定义的状态。这时再对t执行std::move并传入merge函数，属于未定义行为，因为移动后的对象仅允许被销毁或赋值，其他操作的结果不可预测。

另外，原代码里的const_cast<T&>需要格外注意：std::unordered_set的元素默认是const的，这是为了防止修改元素破坏容器的哈希结构。你必须严格保证merge函数只修改不影响哈希值和相等性判断的成员，否则会导致容器内部结构混乱，引发未定义行为。

安全实现EmplaceOrMerge的两种方式 #

方式一：先查找再插入（简单易用） #

先尝试查找容器中是否存在等效元素，存在则直接合并，不存在再插入新元素。这种方式会执行两次哈希计算（查找和插入各一次），但对大多数场景来说性能影响可以接受：

template<typename T>
T& EmplaceOrMerge(std::unordered_set<T>& s, T&& t, std::function<void(T&&, T&)> merge) {
    auto it = s.find(t);
    if (it != s.end()) {
        // 此时t未被移动，可安全传入merge
        merge(std::move(t), const_cast<T&>(*it));
        return const_cast<T&>(*it);
    } else {
        // 插入新元素，t被移动后直接返回新元素
        return const_cast<T&>(*s.emplace(std::move(t)).first);
    }
}

方式二：避免重复哈希（性能优化） #

如果需要避免两次哈希计算，可以利用C++20的异构查找特性（前提是你的std::unordered_set的哈希和相等性比较器支持异构类型）。例如，若T的核心键可以提取为独立的Key类型，可先通过键查找：

template<typename T>
T& EmplaceOrMerge(std::unordered_set<T>& s, T&& t, std::function<void(T&&, T&)> merge) {
    // 假设extract_key是你实现的从T中提取键的函数
    const auto key = extract_key(t);
    auto it = s.find(key);
    if (it != s.end()) {
        merge(std::move(t), const_cast<T&>(*it));
        return const_cast<T&>(*it);
    } else {
        return const_cast<T&>(*s.emplace(std::move(t)).first);
    }
}

这种方式只需要计算一次键的哈希值，但需要你为std::unordered_set配置支持异构查找的哈希函数和相等性比较器。

内容的提问来源于stack exchange，提问作者V. Semeria