c++ 在std::unordered_set上放置或合并

1l5u6lss  于 2023-03-20  发布在  其他
关注(0)|答案(2)|浏览(243)

我正在尝试实现此替换或合并

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函数修改了它的第二个参数,保留了它的散列值。我关心的是在merge情况下使用std::move(t),因为emplace可能已经移动了它。我读过微软的unordered_set实现,有一个非常好的特殊情况。它认识到其自变量std::move(t)可以被直接散列(并且直接与operator==比较),而无需构造另一个对象T,并且当存在unordered_set中的等价值时立即返回该等价值。
这种特殊的情况会出现在标准库的所有实现中吗?如果不是,我有未定义的行为,我想知道是否有其他的方法来编码这个EmplaceOrMerge

ny6fqffe

ny6fqffe1#

不,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下。
Demo .
我想知道是否有另一种方法来编码这个EmplaceOrMerge
您无法回避libstdc
只会在已经构造的节点上调用Hash这一事实。(例如从提取的密钥到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);
}

Demo .
在您的情况下,您可以缩短move-assign返回的时间,因此开销仅为一次移动(和额外的节点分配):

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;
}
f4t66c6m

f4t66c6m2#

std::unordered_set存储唯一的键,因此在插入之前,它会检查该键是否已经存在于哈希表中。如果该键已经存在,则不会进行插入,因此不会就地构造该元素。在cppreference中,emplace成员函数被描述为“将新元素插入到构造于如果容器中没有带键的元素,则用给定的参数放置“。下面还写着”即使容器中已经有带键的元素,也可以构造该元素,在这种情况下,新构造的元素将立即销毁“。因此,这个动作可能会使元素处于未指定的状态,这取决于它的move构造函数的实现。核心问题是你不应该使用emplace(Args&&...),因为我前面提到过,特别是,当你只是移动T的时候它会执行原地构造。如果您真的希望就地构造元素,则应该使用完全转发将参数传递给emplace,而不是使用移动。
因为@krisz给我的评论是关于insert(value_type&&)成员函数的一个有趣的答案,它会使元素处于一个未指定的状态(它不能确保只有当键不存在时才调用移动赋值运算符或移动构造函数,然后必须有效地执行插入),我建议您更改代码,并在插入或移动键之前检查键是否已经存在。

相关问题