std::unordered_map::emplace对象创建

Question

我正在选择将东西放入unordered_map中的两种方法之一：

std::unordered_map<Key, Value> map;
map.emplace(
  std::piecewise_construct,
  std::forward_as_tuple(a),
  std::forward_as_tuple(b, c, d));

vs

std::unordered_map<Key, DifferentValue> map;
auto& value = map[a];
if (value.isDefaultInitialized())
  value = DifferentValue(b, c, d);

我做了一些实验，发现在插入唯一元素时，它们的表现相当。然而，在插入重复项时（考虑到 Value 或 DifferentValue 的构建不是微不足道的），令我惊讶的是，无论是否插入对象，emplace 都会构造对象。因此，在这种情况下，第二种方法似乎要胜出得多，因为默认构造函数只有 isDefaultInitialized_（true）而已，没有更多的功能。对于 emplace，代码似乎是：

... _M_emplace(std::true_type, _Args&&... __args) {
  __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
  const key_type& __k = this->_M_extract()(__node->_M_v);
  ...
  if (__node_type* __p = _M_find_node(__bkt, __k, __code)) {
     _M_deallocate_node(__node);
     return std::make_pair(iterator(__p), false);
  }
  return std::make_pair(_M_insert_unique_node(__bkt, __code, __node), true);
}

因此，尽管我将使用第二种方法（即使需要移动赋值和移动构造函数以及额外的字段），但我想知道为什么emplace创建一个稍后会被忽略的对象是否有充分的理由？也就是说，它是否应该首先检查是否需要创建对象并在已存在时提前退出？

（请注意，对于我的特定情况，默认初始化的项不被认为是有效的，因此问题实际上只涉及emplace）

记录一下，我在23.2.4表102下找到了一些内容：

Effects: Inserts a value_type object t constructed with std::forward<Args>(args)...
if and only if there is no element in the container with key equivalent to the
key of t.

我认为这样可以避免创建对象。

- vmpstr

---

至少必须创建 key 才能使用 hash 和 comparison 函数。这个问题在 C++14 中已经得到解决，适用于 std::map。对于 std::map，可以在不构造相应对象的情况下查找 _key_。请参见 http://en.cppreference.com/w/cpp/container/map/find。不幸的是，对于 std::unordered_map，这是不可能的。 - nosid

哦，有趣，我完全忽略了那个。所以为了获取键，它必须构建对象，因此这不是操作顺序的选择，而是必须创建它才能找出是否已经存在具有该键的对象？ - vmpstr

是的，它必须创建_key_来判断对象是否已经存在。 - nosid

Answer 1

在我看来，标准中的引用部分是误导性的，因为它暗示了只有在容器中没有匹配元素时才会构造对象。我猜他们试图表达的是：

“效果”：使用“std::forward(args)...”构造一个“value_type”对象“t”。仅当容器中不存在与“t”的键等效的元素时，才插入构造的对象“t”。

原因是：为了找出是否存在具有等效键的元素，函数“emplace”的实现必须构造“t”，因为实现必须调用“哈希”函数和“相等”谓词。然而，通常它们只能用“value_type”类型的对象调用，而不能用用于构造这些对象的“元组”调用。

理论上，可以指定一个emplace函数，如果已经存在具有相同键的元素，则不构造t。有趣的是，C++14中将添加类似的功能用于std::map::find。请参阅以下文档：

• http://en.cppreference.com/w/cpp/container/map/find

有两种重载方式可与任意类型一起使用，只要compare函数满足一些额外要求即可。有趣的是，std::unordered_map没有这样的重载。

- nosid

---

关键是散列，而不是值。那么为什么需要构造一个值类型对象来计算哈希呢？ - haelix

@haelix：value 由 key 和 mapped value 组成。std::map::emplace 是一个可变成员函数模板，参数与 key 之间没有直接映射关系。因此，在不构造 value 的情况下，实现无法简单地访问 _key_。 - nosid

我认为std::piecewise_construct恰好是用来告诉哪些参数是用于键的。无论如何，我对此感到失望。似乎unordered_map并不知道它实际上是一个键值映射 - 因此它无法仅操作键？ - haelix

我也觉得emplace的行为方式相当令人恼火。对我来说，这是一个问题，因为第二次插入会创建一个具有副作用的析构函数调用。我认为这可以通过使用像你所说的piecewise_construct来轻松解决。只需创建一个使用piecewise_construct（如pair的构造函数）的重载，并使用第一个元组仅创建一个键，然后执行所需的哈希和比较即可。这种方法的唯一缺点是，如果插入成功，您将同时调用键的构造函数和移动构造函数。 - dcmm88

@dcmm88：前一段时间，我实际上实现了这样一个emplace函数（以及相应的put函数，也称为insert_or_update），作为概念证明（供自己参考）。请参见http://pastebin.com/8nKZLMaC。 - nosid

Answer 2

是的，std::unordered_map::emplace() 的第一件事情是在内存中创建要插入的键值对，然后再查找是否已经存在具有刚刚构造的 KEY 的元素。如果找到这样的元素，emplace() 将立即销毁新创建的元素。通常人们使用 emplace() 的原因不是为了这个，而是为了避免不必要的对象创建！

std::(unordered_)map::emplace() 设计上的问题可能是，如果先创建 KEY，然后再检查 KEY 是否存在，则需要能够将 KEY 移动或复制到其在键值对中的最终位置（如果未找到 KEY）。由于 emplace() 是专门用于处理不可复制和不可移动对象的 STL 容器，所以依赖于可移动/可复制 KEY 的 emplace() 实现将是不完整的。

然而，99%的合理KEY都可以被复制构造或移动构造，所以它们应该与VALUE分开处理，因为VALUE的构造可能更加复杂。而且在C++17（又称C++1z）中，这门语言的神灵对我们很好，添加了try_emplace()方法：它的参数是对已经构造的KEY的引用和仅需要构造相应VALUE的参数。try_emplace()首先搜索KEY。只有当KEY是新的时，才会通过复制或移动KEY并在原地构造VALUE来构造新的KEY-VALUE对。欢呼！

- Kai Petzke