10

我有一个没有默认构造函数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 是否存在于我的地图中两次（如在我的第二种方法中）

谢谢

4

3 回答 3

5

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

问题在于该emplace操作旨在避免复制，而不是避免不必要的映射类型构造。实际上，发生的情况是实现分配并构造一个节点，其中包含映射value_typeie pair<const Key, T>，然后对 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];
}
于 2014-06-13T20:09:05.320 回答
3

您可以使用boost::optional<T>以便能够默认构造映射类型，然后T稍后为其分配初始化。

#include <cassert>
#include <unordered_map>
#include <boost/optional.hpp>

struct MappedType
{
  explicit MappedType(int) {}
};

int main()
{
  std::unordered_map<int, boost::optional<MappedType>> map;
  boost::optional<MappedType>& opt = map[0];
  assert(!opt.is_initialized());
  opt = MappedType(2);
  assert(opt.is_initialized());
  MappedType& v = opt.get();
}
于 2014-06-13T18:37:57.353 回答
1

詹姆斯，你基本上已经回答了你自己的问题。

在任何一种实现中，您都没有做错任何事情。emplace只是做更多的工作find，尤其是当密钥已经存在于您的unordered_map.

如果您的get_value辅助函数主要接收重复项，那么emplace每次调用都会导致您观察到的性能热点。

于 2014-06-13T19:06:13.553 回答