std :: unordered_map :: emplace对象创建 [英] std::unordered_map::emplace object creation

问题描述

我正在选择将事物放入unordered_map的两种方法之一：

  std :: unordered_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 [a]; 
 if（value.isDefaultInitialized（））
 value = DifferentValue（b，c，d）; 
  

我做了一些实验，看哪个在插入唯一元素时表现更好， （就效率而言）基本上是等价的。

但是，在插入重复项的情况下，考虑到Value或DifferentValue的构造并非无关紧要，我感到很惊讶可以发现emplace会构造对象，而不管它是否将其插入。

因此，在这种情况下，第二种方法似乎已经成功，因为默认的构造函数

对于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）; 
} 
返回std :: make_pair（_M_insert_unique_node（__ bkt，__code，__node），true）; 
} 
  

因此，尽管我要使用第二种方法（即使它需要移动分配和移动构造函数以及额外的字段），我想知道为什么emplace创建了一个后来被忽略的对象有很好的理由？也就是说，是否应该先检查是否需要创建对象，然后是否早已存在？

（请注意，在我的特殊情况下，不考虑默认的初始化项）是有效的，所以问题实际上只是关于位）

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

 作用：插入由std :: forward< Args>（args）...构造的value_type对象t，且仅当且仅当键等于t的
键的容器。 
  

我认为这将允许不创建对象。

效果：构造一个 value_type 对象 t 和 std :: forward< Args>（args）... 。当且仅当容器中没有这样的元素且其键等于 t t >。

原因是：函数 emplace 的实现必须构造 t 以便查找是否存在具有等效键的元素，因为实现必须调用 hash 函数和等于谓词。但是，通常只能使用 value_type 类型的对象调用它们，而不能使用用于构造这些对象的 tuples 调用。

理论上，可以指定一个 emplace 函数，如果存在的话，该函数不会构造 t 已经是具有等效键的元素。有趣的是，C ++ 14将为 std :: map :: find 添加类似的东西。请参阅以下文档：

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

有两个重载，可以使用任意类型，只要 compare 函数满足一些其他要求。有趣的是， std :: unordered_map 没有这样的重载。

I was in the process of selecting one of two methods of putting things into an 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);

I did some experiments to see which one would perform better to find that when inserting unique elements, the behaviour (as in efficiency) was basically equivalent.

However, in the case of inserting duplicate items, and consider that the construction of Value or DifferentValue is not trivial, I was surprised to find is that emplace constructs the object regardless of whether it will insert it or not.

So, the second method seems to win by far in that case since the default constructor just has isDefaultInitialized_(true) in there and not much more.

For emplace, the code seems to be:

... _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);
}

So, although I'm going to go with the second method (even if it requires move assignment and move constructors and extra fields), I was wondering is there a good rationale for why emplace creates an object that it later disregards? That is, should it first check if it needs to create the object and early out if it already exists?

(note that for my particular case default initialized items are not considered valid, so the question is really just about emplace)

For the record, I found something under 23.2.4 table 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.

which I think would allow for not creating the object.

解决方案

In my opinion, the quoted part from the standard is misleading, because it suggests, that the object is only constructed if there is no matching element in the container. I guess they are trying to state:

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

The reason is: The implementation of the function emplace has to construct t in order to find out if an element with an equivalent key exists, because the implementation has to invoke the hash function and the equals predicate. However, in general they can only be invoked with objects of type value_type, not with tuples used to construct these objects.

In theory, it would be possible to specify an emplace function, that doesn't construct t if there is already an element with an equivalent key. Interestingly, something similar will be added with C++14 for std::map::find. See the following documentation:

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

There are two overloads, that can be used with arbitrary types, as long as the compare function fulfills some additional requirements. Interestingly enough, there is no such overload for std::unordered_map.

这篇关于std :: unordered_map :: emplace对象创建的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！