安慰的表现比检查后的安慰更糟糕

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对象创建中读取了emplace需要构造对象以查看是否存在.但是,在返回之前,emplace正在检查地图中是否存在此键值对.

我用错误的方式使用emplace吗？是否有一个更好的模式我应该遵循:

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

谢谢

Answer 1

不幸的是，您的代码对于当前的标准库来说是最佳的。

问题在于该emplace操作的目的是避免复制，而不是避免不必要地构造映射类型。实际上，发生的情况是该实现分配并构造了一个节点，该节点包含map value_type即pair<const Key, T>，然后哈希键以确定所构造的节点是否可以链接到容器中；如果冲突，则删除该节点。

只要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];
}