在c映射中插入vs emplace vs operator\[\]

Question

我第一次使用地图，我意识到有很多方法可以插入元素。 You can use emplace() , operator[] or insert() , plus variants like using value_type or make_pair .虽然有很多关于所有这些的信息和关于特定案例的问题，但我仍然无法理解大局。所以，我的两个问题是：

1. 他们每个人比其他人有什么优势？

2. 是否需要在标准中添加 emplace？没有它，有什么是不可能的吗？

原文由 German Capuano 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在地图的特定情况下，旧选项只有两个： operator[] 和 insert （不同风格的 insert ）。所以我将开始解释这些。

operator[] 是一个 查找或添加 运算符。它将尝试在地图中查找具有给定键的元素，如果存在，它将返回对存储值的引用。如果没有，它将使用默认初始化创建一个插入到位的新元素并返回对它的引用。

The insert function (in the single element flavor) takes a value_type ( std::pair<const Key,Value> ), it uses the key ( first member) and试图插入它。因为 std::map 如果存在现有元素则不允许重复，因此不会插入任何内容。

两者的第一个区别是 operator[] 需要能够构造一个默认的初始化 _值_，因此不能用于不能默认初始化的值类型。两者之间的第二个区别是当已经存在具有给定键的元素时会发生什么。 insert 函数不会修改映射的状态，而是返回一个迭代器到元素（和一个 false 表明它没有被插入）。

 // 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 对象，虽然它可能不是你想要的……

以下调用的净效果是 相似 的：

 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<const K,V> ）并将其传递给 insert 函数。 insert 函数将在二叉搜索树中创建适当的节点，然后将 value_type 部分从参数复制到节点。 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 。签名是：

 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<K,V> 缺失的 const ）。签名需要 value_type 接近 但与调用 std::make_pair 的返回值不同。因为它足够接近，它将创建一个正确类型的临时文件并复制初始化它。这将依次复制到节点，总共创建两个副本。

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

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

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

到目前为止，我们有不同的调用方式 insert 需要在外部创建 value_type 并将该对象的副本复制到容器中。或者，您可以使用 operator[] 如果类型是 默认可构造 和 可分配 的（故意只关注 m[k]=v ），它需要一个对象的默认初始化并将值 复制 到该对象中目的。

在 C++11 中，通过可变参数模板和完美转发，有一种新方法可以通过 _放置_（就地创建）将元素添加到容器中。不同容器中的 emplace 函数基本上做同样的事情：该函数不是获取 复制 到容器的 _源_，而是获取将转发给存储在容器。

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

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到 emplace 将它们转发到数据结构内的 value_type 子对象的构造函数。在这种情况下， 根本不会 复制 std::pair<const K,V> ，这是 emplace 优于 C++03 替代方案的优势。就像 insert 它不会覆盖地图中的值。

---

一个我没有想到的有趣问题是 emplace 可以如何实际用于地图，这在一般情况下不是一个简单的问题。

原文由 David Rodríguez - dribeas 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

在其他答案中还有一个尚未讨论的附加问题，它适用于 std::map 以及 std::unordered_map 、 std::set std::unordered_set ：

• insert 与键对象一起使用，这意味着如果容器中已经存在键，则 不需要分配节点。

• emplace 需要先构造key，一般每次调用都 需要分配一个节点。

从这个角度来看，如果密钥已经存在于容器中， emplace 的效率可能低于 insert 。 （例如，在具有线程本地字典的多线程应用程序中，这可能很重要，其中分配需要同步。）

现场演示： https ://godbolt.org/z/ornYcTqW9。请注意，对于 libstdc++ ， emplace 分配 10 次，而 insert 仅分配一次。对于 libc++ ，也只有一个分配 emplace ；似乎有一些优化可以复制/移动键* 。我使用 Microsoft STL 得到了相同的结果，因此实际上似乎 libstdc++ 中缺少一些优化。然而，整个问题可能不仅仅与标准容器有关。例如，来自 Intel/oneAPI TBB 的 concurrent_unordered_map 在这方面与 libstdc++ 的行为相同。

---

*请注意，此优化不适用于键既 不可复制 又 不可移动的 情况。在这个现场演示中，即使使用 emplace 和 libc++，我们也有 10 个分配： https ://godbolt.org/z/1b6b331qf。 （当然，对于不可复制和不可移动的密钥，我们不能使用 insert 或 try_emplace ，所以没有其他选择。）

原文由 Daniel Langr 发布，翻译遵循 CC BY-SA 4.0 许可协议