在 C++ 地图中插入 vs emplace vs operator[]

2021-12-10 00:00:00 dictionary operators insert c++ emplace

我第一次使用地图,我意识到有很多方法可以插入一个元素.您可以使用 emplace()operator[]insert(),以及使用 value_type 或 <代码>make_pair.虽然有很多关于所有这些的信息和关于特定案例的问题,但我仍然无法理解大局.所以,我的两个问题是:

I'm using maps for the first time and I realized that there are many ways to insert an element. You can use emplace(), operator[] or insert(), plus variants like using value_type or make_pair. While there is a lot of information about all of them and questions about particular cases, I still can't understand the big picture. So, my two questions are:

  1. 它们中的每一个相对于其他的有什么优势?

  1. What is the advantage of each one of them over the others?

是否需要将 emplace 添加到标准中?没有它,以前有什么是不可能的吗?

Was there any need for adding emplace to the standard? Is there anything that wasn't possible before without it?

推荐答案

在地图的特殊情况下,旧的选项只有两个:operator[]insert(insert 的不同风格).所以我将开始解释这些.

In the particular case of a map the old options were only two: operator[] and insert (different flavors of insert). So I will start explaining those.

operator[] 是一个 find-or-add 操作符.它将尝试在地图内找到具有给定键的元素,如果存在,它将返回对存储值的引用.如果没有,它将创建一个新元素插入到位并使用默认初始化并返回对它的引用.

The operator[] is a find-or-add operator. It will try to find an element with the given key inside the map, and if it exists it will return a reference to the stored value. If it does not, it will create a new element inserted in place with default initialization and return a reference to it.

insert 函数(在单元素风格中)接受一个 value_type (std::pair),它使用密钥(first 成员)并尝试插入它.因为 std::map 不允许重复,如果有一个现有元素,它不会插入任何东西.

The insert function (in the single element flavor) takes a value_type (std::pair<const Key,Value>), it uses the key (first member) and tries to insert it. Because std::map does not allow for duplicates if there is an existing element it will not insert anything.

两者的第一个区别是operator[]需要能够构造一个默认初始化的value,因此对于不能被初始化的值类型是不可用的默认初始化.两者之间的第二个区别是当已经存在具有给定键的元素时会发生什么.insert 函数不会修改地图的状态,而是返回一个迭代器到元素(以及一个 false 表示它没有被插入).

The first difference between the two is that operator[] needs to be able to construct a default initialized value, and it is thus unusable for value types that cannot be default initialized. The second difference between the two is what happens when there is already an element with the given key. The insert function will not modify the state of the map, but instead return an iterator to the element (and a false indicating that it was not inserted).

// assume m is std::map<int,int> already has an element with key 5 and value 0
m[5] = 10;                      // postcondition: m[5] == 10
m.insert(std::make_pair(5,15)); // m[5] is still 10

insert 的情况下,参数是一个value_type 的对象,可以用不同的方式创建.您可以使用适当的类型直接构造它或传递可以从中构造 value_type 的任何对象,这是 std::make_pair 发挥作用的地方,因为它允许std::pair 对象的简单创建,虽然它可能不是你想要的......

In the case of insert the argument is an object of value_type, which can be created in different ways. You can directly construct it with the appropriate type or pass any object from which the value_type can be constructed, which is where std::make_pair comes into play, as it allows for simple creation of std::pair objects, although it is probably not what you want...

以下调用的净效果类似:

K t; V u;
std::map<K,V> m;           // std::map<K,V>::value_type is std::pair<const K,V>

m.insert( std::pair<const K,V>(t,u) );      // 1
m.insert( std::map<K,V>::value_type(t,u) ); // 2
m.insert( std::make_pair(t,u) );            // 3

但实际上并不相同... [1] 和 [2] 实际上是等效的.在这两种情况下,代码都会创建一个相同类型的临时对象 (std::pair) 并将其传递给 insert 函数.insert 函数将在二叉搜索树中创建适当的节点,然后将 value_type 部分从参数复制到节点.使用 value_type 的好处是,value_type 总是匹配 value_type,你不能错误输入std::pair 参数!

But the are not really the same... [1] and [2] are actually equivalent. In both cases the code creates a temporary object of the same type (std::pair<const K,V>) and passes it to the insert function. The insert function will create the appropriate node in the binary search tree and then copy the value_type part from the argument to the node. The advantage of using value_type is that, well, value_type always matches value_type, you cannot mistype the type of the std::pair arguments!

不同之处在于 [3].函数 std::make_pair 是一个模板函数,它将创建一个 std::pair.签名是:

The difference is in [3]. The function std::make_pair is a template function that will create a std::pair. The signature is:

template <typename T, typename U>
std::pair<T,U> make_pair(T const & t, U const & u );

我故意不向 std::make_pair 提供模板参数,因为这是常见用法.这意味着模板参数是从调用中推导出来的,在这种情况下是 T==K,U==V,所以调用 std::make_pair 将返回一个 std::pair(注意缺少的 const).签名要求 value_type close 但与调用 std::make_pair 的返回值不同.因为它足够接近它会创建一个正确类型的临时文件并复制初始化它.这将依次复制到节点,共创建两个副本.

I have intentionally not provided the template arguments to std::make_pair, as that is the common usage. And the implication is that the template arguments are deduced from the call, in this case to be T==K,U==V, so the call to std::make_pair will return a std::pair<K,V> (note the missing const). The signature requires value_type that is close but not the same as the returned value from the call to std::make_pair. Because it is close enough it will create a temporary of the correct type and copy initialize it. That will in turn be copied to the node, creating a total of two copies.

这可以通过提供模板参数来解决:

This can be fixed by providing the template arguments:

m.insert( std::make_pair<const K,V>(t,u) );  // 4

但这仍然容易出错,就像在 case [1] 中显式键入类型一样.

But that is still error prone in the same way that explicitly typing the type in case [1].

到目前为止,我们有不同的调用 insert 的方法,需要在外部创建 value_type 并将该对象复制到容器中.或者,您可以使用 operator[] 如果类型是默认可构造 和 assignable(有意只关注 m[k]=v),它需要对一个对象进行默认初始化,并将值复制到该对象中.

Up to this point, we have different ways of calling insert that require the creation of the value_type externally and the copy of that object into the container. Alternatively you can use operator[] if the type is default constructible and assignable (intentionally focusing only in m[k]=v), and it requires the default initialization of one object and the copy of the value into that object.

在 C++11 中,通过可变模板和完美转发,提供了一种通过 emplacing(就地创建)将元素添加到容器中的新方法.不同容器中的 emplace 函数做的事情基本上是一样的:不是获取 source 从中copy 到容器中,该函数需要将被转发到存储在容器中的对象的构造函数的参数.

In C++11, with variadic templates and perfect forwarding there is a new way of adding elements into a container by means of emplacing (creating in place). The emplace functions in the different containers do basically the same thing: instead of getting a source from which to copy into the container, the function takes the parameters that will be forwarded to the constructor of the object stored in the container.

m.emplace(t,u);               // 5

在 [5] 中,std::pair 没有被创建并传递给 emplace,而是对 t 的引用u 对象被传递给 emplace,后者将它们转发给数据结构内的 value_type 子对象的构造函数.在这种情况下,没有 std::pair 的副本被完成,这是 emplace 的优势C++03 替代品.与 insert 的情况一样,它不会覆盖地图中的值.

In [5], the std::pair<const K, V> is not created and passed to emplace, but rather references to the t and u object are passed to emplace that forwards them to the constructor of the value_type subobject inside the data structure. In this case no copies of the std::pair<const K,V> are done at all, which is the advantage of emplace over the C++03 alternatives. As in the case of insert it will not override the value in the map.

一个我没有想到的有趣问题是 emplace 如何为地图实际实现,这在一般情况下不是一个简单的问题.

An interesting question that I had not thought about is how emplace can actually be implemented for a map, and that is not a simple problem in the general case.

相关文章