这是我第一次使用映射,我意识到插入元素的方法有很多种。您可以使用emplace(),操作符[]或insert(),加上使用value_type或make_pair等变量。虽然有很多关于他们所有人的信息和关于特定案例的问题,但我仍然不能理解大局。 我的两个问题是:

它们各自的优势是什么? 是否有必要在标准中增加放置位置?在没有它之前,有什么事情是不可能的吗?


当前回答

放置:利用右值引用来使用您已经创建的实际对象。这意味着没有复制或移动构造函数被调用,这对大型对象很好!O (log (N))的时间。

Insert:具有标准左值引用和右值引用的重载,以及指向要插入元素列表的迭代器,以及关于元素所属位置的“提示”。使用“hint”迭代器可以将插入所花费的时间降低到常数时间,否则就是O(log(N))时间。

操作符[]:检查对象是否存在,如果存在,则修改对该对象的引用,否则使用提供的键和值对这两个对象调用make_pair,然后执行与insert函数相同的工作。这是O(log(N))次。

make_pair:只做一对。

There was no "need" for adding emplace to the standard. In c++11 I believe the && type of reference was added. This removed the necessity for move semantics, and allowed optimization of some specific type of memory management. In particular, the rvalue reference. The overloaded insert(value_type &&) operator does not take advantage of the in_place semantics, and is therefore much less efficient. While it provides the capability of dealing with rvalue references, it ignores their key purpose, which is in place construction of objects.

其他回答

放置:利用右值引用来使用您已经创建的实际对象。这意味着没有复制或移动构造函数被调用,这对大型对象很好!O (log (N))的时间。

Insert:具有标准左值引用和右值引用的重载,以及指向要插入元素列表的迭代器,以及关于元素所属位置的“提示”。使用“hint”迭代器可以将插入所花费的时间降低到常数时间,否则就是O(log(N))时间。

操作符[]:检查对象是否存在,如果存在,则修改对该对象的引用,否则使用提供的键和值对这两个对象调用make_pair,然后执行与insert函数相同的工作。这是O(log(N))次。

make_pair:只做一对。

There was no "need" for adding emplace to the standard. In c++11 I believe the && type of reference was added. This removed the necessity for move semantics, and allowed optimization of some specific type of memory management. In particular, the rvalue reference. The overloaded insert(value_type &&) operator does not take advantage of the in_place semantics, and is therefore much less efficient. While it provides the capability of dealing with rvalue references, it ignores their key purpose, which is in place construction of objects.

除了优化机会和更简单的语法之外,插入和插入之间的一个重要区别是,后者允许显式转换。(这适用于整个标准库,而不仅仅是地图。)

下面是一个例子:

#include <vector>

struct foo
{
    explicit foo(int);
};

int main()
{
    std::vector<foo> v;

    v.emplace(v.end(), 10);      // Works
    //v.insert(v.end(), 10);     // Error, not explicit
    v.insert(v.end(), foo(10));  // Also works
}

诚然,这是一个非常具体的细节,但是当您处理用户定义的转换链时,有必要记住这一点。

在映射的特殊情况下,旧的选项只有两个:操作符[]和插入(不同风格的插入)。我将开始解释这些。

操作符[]是一个查找或添加操作符。它将尝试在映射中找到具有给定键的元素,如果它存在,它将返回对存储值的引用。如果没有,它将创建一个新元素插入到默认初始化的位置,并返回对该元素的引用。

insert函数(在单元素类型中)接受一个value_type (std::pair<const Key,Value>),它使用键(第一个成员)并尝试插入它。因为std::map不允许重复,如果有一个现有的元素,它将不会插入任何东西。

两者之间的第一个区别是操作符[]需要能够构造一个默认初始化值,因此它不适用于不能默认初始化的值类型。两者之间的第二个区别是,当已经有一个具有给定键的元素时会发生什么。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部分复制到该节点。使用value_type的好处是,value_type总是匹配value_type,你不能把std::pair参数的类型输入错误!

差值是[3]。函数std::make_pair是一个模板函数,它将创建一个std::pair。签名为:

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

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.

这可以通过提供模板参数来修复:

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

但这仍然很容易出错,就像显式地键入情况[1]中的类型一样。

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

在c++ 11中,有了可变模板和完美转发,就有了一种通过放置(在适当位置创建)的方式向容器中添加元素的新方法。不同容器中的emplace函数做的基本相同的事情:该函数不是获取要复制到容器中的源,而是接受将转发到容器中存储的对象的构造函数的参数。

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

在[5]中,std::pair<const K, V>没有被创建并传递给emplace,而是将对t和u对象的引用传递给emplace,并将它们转发给数据结构内部value_type子对象的构造函数。在这种情况下,std::pair<const K,V>根本不会被复制,这是emplace相对于c++ 03的优势。与插入的情况一样,它不会覆盖映射中的值。


一个有趣的问题是,我没有想过如何在地图上实现放置,这在一般情况下并不是一个简单的问题。

就功能或输出而言,它们都是相同的。

对于这两个大内存,对象放置是内存优化,不使用复制构造函数

简单详细的解释 https://medium.com/@sandywits/all-about-emplace-in-c-71fd15e06e44

还有一个没有在其他答案中讨论的附加问题,它适用于std::map以及std::unordered_map, std::set和std::unordered_set:

Insert使用键对象,这意味着如果键已经存在于容器中,则不需要分配节点。 Emplace需要首先构造键,这通常需要在每次调用它时分配一个节点。

从这个角度来看,如果键已经存在于容器中,那么放置可能比插入效率低。(这对于多线程应用程序来说可能很重要,例如在线程本地字典中,需要同步分配。)

Live demo: https://godbolt.org/z/ornYcTqW9. Note that with libstdc++, emplace allocates 10 times, while insert only once. With libc++, there is only one allocation with emplace as well; it seems there is some optimization that copies/moves keys*. I got the same outcome with Microsoft STL, so it actually seems that there is some missing optimization in libstdc++. However, the whole problem may not be related only to standard containers. For instance, concurrent_unordered_map from Intel/oneAPI TBB behaves the same as libstdc++ in this regard.


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