c++ - emplace 的性能比 check 后跟 emplace 差

Question

我有一个 std::unordered_map，它的 value_type 没有默认构造函数，所以我不能执行以下操作

auto k = get_key();
auto& v = my_map[k];

我最终写了一个辅助函数

value_type& get_value(key_type& key)
{
    return std::get<0>(my_map.emplace(
                              std::piecewise_construct,
                              std::forward_as_tuple(key),
                              std::forward_as_tuple(args_to_construct_value)
                      ))->second;
}

但性能明显低于以下版本(即 value_type 的构造函数出现在 perf 中)。

value_type& get_value(key_type& key)
{
    auto it = my_map.find(key);
    if (it == my_map.end())
        return std::get<0>(my_map.emplace(
                                  std::piecewise_construct,
                                  std::forward_as_tuple(key),
                                  std::forward_as_tuple(args_to_construct_value)
                          ))->second;
    else
        return it->second;
}

我读自std::unordered_map::emplace object creation该 emplace 需要构造对象才能查看是否存在。但是 emplace 在返回之前会检查 map 中是否存在这个键值对。

我是否以错误的方式使用了 emplace？有没有更好的模式我应该遵循:

1. 不会在每次查找时都构建我的 value_type(如我的第一种方法)
2. 不会两次检查我的 map 中是否存在 value_type(如我的第二种方法)

谢谢

Answer 1

不幸的是，您的代码目前是标准库的最佳选择。

问题是 emplace操作旨在避免复制，而不是避免不必要的映射类型构造。实际上，发生的事情是实现分配并构造一个节点，其中包含 map value_type。即 pair<const Key, T> ，然后then对key进行哈希，判断构建的节点是否可以链接到容器中；如果发生冲突，则删除该节点。

只要hash和 equal_to不太昂贵，您的代码不应该做太多额外的工作。

另一种方法是使用自定义分配器拦截映射类型的 0 参数构造；问题是检测这样的构造非常繁琐:

#include <unordered_map>
#include <iostream>

using Key = int;
struct D {
    D() = delete;
    D(D const&) = delete;
    D(D&&) = delete;
    D(std::string x, int y) { std::cout << "D(" << x << ", " << y << ")\n"; }
};
template<typename T>
struct A {
    using value_type = T;
    using pointer = T*;
    using const_pointer = T const*;
    using reference = T&;
    using const_reference = T const&;
    template<typename U> struct rebind { using other = A<U>; };
    value_type* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }
    void deallocate(T* c, std::size_t n) { std::allocator<T>().deallocate(c, n); }
    template<class C, class...Args> void construct(C* c, Args&&... args) { std::allocator<T>().construct(c, std::forward<Args>(args)...); }
    template<class C> void destroy(C* c) { std::allocator<T>().destroy(c); }

    std::string x; int y;
    A(std::string x, int y): x(std::move(x)), y(y) {}
    template<typename U> A(A<U> const& other): x(other.x), y(other.y) {}
    template<class C, class...A> void construct(C* c, std::piecewise_construct_t pc, std::tuple<A...> a, std::tuple<>) {
        ::new((void*)c)C(pc, a, std::tie(x, y)); }
};

int main() {
    using UM = std::unordered_map<Key, D, std::hash<Key>, std::equal_to<Key>, A<std::pair<const Key, D>>>;
    UM um(0, UM::hasher(), UM::key_equal(), UM::allocator_type("hello", 42));
    um[5];
}