在std::unordered_set上使用emplace或merge

Question

我正在尝试实现这个emplace或merge

template<typename T>
T& EmplaceOrMerge(std::unordered_set<T>& s,
                  T&& t,
                  std::function<void(T&& a, T& b)> merge)
{
    auto it = s.emplace(std::move(t));
    T& u = const_cast<T&>(*it.first);
    if (!it.second)
        merge(std::move(t), u);
    return u;
}

merge 函数以一种保留其哈希值的方式修改了它的第二个参数。我关注于在合并情况下使用 std::move(t)，因为 emplace 可能已经将它移动了。我已经阅读了微软的 unordered_set 实现，发现了一个非常好的特殊情况，即 if constexpr (_In_place_key_extractor::_Extractable)，它认识到它的参数 std::move(t) 可以直接哈希（并直接用 operator== 进行比较），无需构造另一个对象 T，并且在存在等效值时立即返回 unordered_set 中的等效值。

这个特殊情况在所有标准库实现中都出现吗？如果不是，则会导致未定义行为，我想知道是否有另一种方法来编写此 EmplaceOrMerge。

- V. Semeria

---

这里的 const_cast<T&>(*it.first); 很可疑。像这样修改集合很可疑。std::move 并不会有问题，因为 std::move 不做任何事情。它只是转换引用类型，如果 emplace 没有实际移动对象，则对象仍然有效，您可以尝试再次移动它。 - Marek R

@MarekR std::move并不会做任何事情，但是emplace可能会。修改unordered_set的内容是可以的，只要保留哈希值（这在问题中已经写明）。如果哈希值不是通过emplace计算而来，则参数已被移动。 - V. Semeria

Answer 1

不，libstdc++ 不执行此优化。

struct A {
    A() = default;
    A(A&&) { std::format_to(std::ostreambuf_iterator<char>(std::cout), "A(A&&)\n"); }
    bool operator==(A const&) const = default;
};
template<> struct std::hash<A> { std::size_t operator()(A const&) const { return 0; } };
int main() {
    std::unordered_set<A> s;
    A a;
    std::format_to(std::ostreambuf_iterator<char>(std::cout), "{}\n",
        s.emplace(std::move(a)).second);
    std::format_to(std::ostreambuf_iterator<char>(std::cout), "{}\n",
        s.emplace(std::move(a)).second);
}

这个程序会打印：

A(A&&)
true
false

在libc++（以及可能是MS-STL）下，但打印

A(A&&)
true
A(A&&)
false

在libstdc++下。

演示。

---

我在想是否有另一种方法来编写这个 EmplaceOrMerge 函数。

无论如何，libstdc++只会在已经构造的节点上调用哈希函数。如果您不能更改数据结构（例如从提取的键改为 std::unordered_map），则一个选择是使用 node-handle 接口，它可以避免插入失败时的副作用。使用它可能仍然需要移动并移回分配内存的开销，但希望这样的代价相对较小。

template<class T>
auto try_emplace(std::unordered_set<T>& s, std::type_identity_t<T>&& t) {
    std::unordered_set<T> s2;
    auto nh = s2.extract(s2.insert(std::move(t)).first);
    auto const ins = s.insert(std::move(nh));
    if (not ins.inserted)
        t = std::move(ins.node.value());
    return std::pair(ins.position, ins.inserted);
}

演示。

在你的情况下，你可以快捷地移动分配回来，因此开销只有一个移动（和额外的节点分配）：

template<typename T>
T& EmplaceOrMerge(std::unordered_set<T>& s,
                  T&& t,
                  std::function<void(T&& a, T& b)> merge)
{
    std::unordered_set<T> s2;
    auto nh = s2.extract(s2.insert(std::move(t)).first);
    auto const ins = s.insert(std::move(nh));
    T& u = const_cast<T&>(*ins.position);
    if (not ins.inserted)
        merge(std::move(ins.node.value()), u);
    return u;
}

- ecatmur

---

谢谢，那我将把我的类分成关键类和值类，并使用unordered_map。我一开始有些犹豫，因为这会改变我的项目中许多函数的签名。 - V. Semeria

Answer 2

std::unordered_set 存储唯一的键，因此在插入之前，它会检查哈希表中是否已经存在该键。如果键已经存在，则不进行插入，因此元素不会被就地构造。 在 cppreference 中，emplace 成员函数被描述为“使用给定参数就地构造一个新元素插入到容器中，如果容器中没有具有该键的元素”。下面还写着“即使容器中已经有了具有该键的元素，元素也可能被构造，此时新构造的元素将立即被销毁”。因此，这个操作可能会使元素处于未指定状态，这取决于其移动构造函数的实现方式。 核心问题是你不应该使用 emplace(Args&&...)，因为正如我之前提到的，它执行的是就地构造，而你只是在移动 T。如果你真的想就地构造元素，而不是使用移动，请使用完美转发将参数传递给 emplace。

由于@krisz给我提供了一个有趣的答案，关于insert(value_type&&)成员函数，它可能会使元素处于未指定状态（仅当键不存在时才确保调用移动赋值运算符或移动构造函数，然后必须有效地执行插入），因此我建议您在插入或移动之前检查键是否已经存在，并更改您的代码。

- LoS

---

t 不是一个右值引用，它是一个转发引用（也称为通用引用）；区别在于 T 是一个模板类型，因此 T&& 是转发引用，而不是右值引用。在一般情况下，元素不需要被构造（我认为在这种情况下它将被构造，但如果集合和元素分别被模板化，则可以是用于构造元素的对象，而不是完全构造的元素）。 - ShadowRanger

那个cppreference页面并不是很长，所以我想知道你是怎么错过这句话的：“即使容器中已经有一个具有相同键的元素，该元素也可以被构造，此时新构造的元素将立即被销毁。” - krisz

@ShadowRanger，@krisz，非常感谢你们的反馈。我稍微修改了我的回答。然而，我认为核心问题在于在这种情况下使用emplace是错误的。 - LoS

我同意insert可能更好，但这仍然不能保证任何事情。请参见c++ - std::unordered_set<T>::insert(T&&): is argument moved if it exists - Stack Overflow。 - krisz