Ger*_*ano 167 c++ dictionary insert operators emplace
我第一次使用地图,我意识到有很多方法可以插入元素.您可以使用emplace(),operator[]或者insert()使用value_type或使用或等变体make_pair.虽然有很多关于所有这些信息以及有关特定案例的问题的信息,但我仍然无法理解大局.所以,我的两个问题是:
每个人比其他人的优势是什么？
是否需要在标准中添加安全性？没有它之前有什么是不可能的吗？
Dav*_*eas 201
在地图的特定情况下,旧选项只有两个:operator[]和insert(不同的风格insert).所以我将开始解释这些.
这operator[]是一个查找或添加运算符.它将尝试在地图中找到具有给定键的元素,如果存在,则将返回对存储值的引用.如果没有,它将使用默认初始化创建一个插入到位的新元素,并返回对它的引用.
的insert功能(在单个元件味)取value_type(std::pair<const Key,Value>),它使用密钥(first部件),并试图将其插入.因为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部分从参数复制到节点.使用的好处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 );
我故意不提供模板参数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
但这仍然容易出错,就像在[1]中明确键入类型一样.
到目前为止,我们有不同的调用方式insert,需要创建value_type外部和该对象的副本到容器中.或者,您可以使用,operator[]如果类型是默认可构造和可分配(仅故意聚焦m[k]=v),则需要将一个对象的默认初始化和值的副本复制到该对象中.
在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>完成任何副本,这是emplaceC++ 03替代方案的优势.在insert它的情况下,它不会覆盖地图中的值.
我没有想到的一个有趣的问题是如何emplace实际为地图实现,这在一般情况下不是一个简单的问题.
Chr*_*sCM 13
Emplace:利用rvalue引用来使用您已创建的实际对象.这意味着不会调用复制或移动构造函数,这对LARGE对象很有用!O(log(N))时间.
Insert:具有标准左值引用和右值引用的重载,以及要插入的元素列表的迭代器,以及关于元素所属位置的"提示".使用"提示"迭代器可以使插入时间缩短到持续时间,否则为O(log(N))时间.
Operator []:检查对象是否存在,如果存在,则修改对该对象的引用,否则使用提供的键和值在两个对象上调用make_pair,然后执行与insert函数相同的工作.这是O(log(N))时间.
make_pair:只是做一对.
没有"需要"为标准添加安慰.在c ++ 11中,我相信添加了&&类型的引用.这消除了移动语义的必要性,并允许优化某些特定类型的内存管理.特别是右值参考.重载的insert(value_type &&)运算符不利用in_place语义,因此效率低得多.虽然它提供了处理右值引用的能力,但它忽略了它们的关键目的,即构建对象.
Ker*_* SB 10
除了优化机会和更简单的语法之外,插入和放置之间的一个重要区别是后者允许显式转换.(这是整个标准库,而不仅仅是地图.)
这是一个示例:
#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()区别的"大局观" emplace():
#include <iostream>
#include <unordered_map>
#include <utility>
struct Foo {
static int foo_counter; //Track how many Foo objects have been created.
int val; //This Foo object was the val-th Foo object to be created.
Foo() { val = foo_counter++;
std::cout << "Foo() with val: " << val << '\n';
}
Foo(int value) : val(value) { foo_counter++;
std::cout << "Foo(int) with val: " << val << '\n';
}
Foo(Foo& f2) { val = foo_counter++;
std::cout << "Foo(Foo &) with val: " << val
<< " \tcreated from: \t" << f2.val << '\n';
}
Foo(const Foo& f2) { val = foo_counter++;
std::cout << "Foo(const Foo &) with val: " << val
<< " \tcreated from: \t" << f2.val << '\n';
}
Foo(Foo&& f2) { val = foo_counter++;
std::cout << "Foo(Foo&&) moving: " << f2.val
<< " \tand changing it to:\t" << val << '\n';
}
~Foo() { std::cout << "~Foo() destroying: " << val << '\n'; }
Foo& operator=(const Foo& rhs) {
std::cout << "Foo& operator=(const Foo& rhs) with rhs.val: " << rhs.val
<< " \tcalled with lhs.val = \t" << val
<< " \tChanging lhs.val to: \t" << rhs.val << '\n';
val = rhs.val;
return *this;
}
bool operator==(const Foo &rhs) const { return val == rhs.val; }
bool operator<(const Foo &rhs) const { return val < rhs.val; }
};
int Foo::foo_counter = 0;
//Create a hash function for Foo in order to use Foo with unordered_map
namespace std {
template<> struct hash<Foo> {
std::size_t operator()(const Foo &f) const {
return std::hash<int>{}(f.val);
}
};
}
int main()
{
std::unordered_map<Foo, int> umap;
Foo foo0, foo1, foo2, foo3;
int d;
std::cout << "\numap.insert(std::pair<Foo, int>(foo0, d))\n";
umap.insert(std::pair<Foo, int>(foo0, d));
//equiv. to: umap.insert(std::make_pair(foo0, d));
std::cout << "\numap.insert(std::move(std::pair<Foo, int>(foo1, d)))\n";
umap.insert(std::move(std::pair<Foo, int>(foo1, d)));
//equiv. to: umap.insert(std::make_pair(foo1, d));
std::cout << "\nstd::pair<Foo, int> pair(foo2, d)\n";
std::pair<Foo, int> pair(foo2, d);
std::cout << "\numap.insert(pair)\n";
umap.insert(pair);
std::cout << "\numap.emplace(foo3, d)\n";
umap.emplace(foo3, d);
std::cout << "\numap.emplace(11, d)\n";
umap.emplace(11, d);
std::cout << "\numap.insert({12, d})\n";
umap.insert({12, d});
std::cout.flush();
}
我得到的输出是:
Foo() with val: 0
Foo() with val: 1
Foo() with val: 2
Foo() with val: 3
umap.insert(std::pair<Foo, int>(foo0, d))
Foo(Foo &) with val: 4 created from: 0
Foo(Foo&&) moving: 4 and changing it to: 5
~Foo() destroying: 4
umap.insert(std::move(std::pair<Foo, int>(foo1, d)))
Foo(Foo &) with val: 6 created from: 1
Foo(Foo&&) moving: 6 and changing it to: 7
~Foo() destroying: 6
std::pair<Foo, int> pair(foo2, d)
Foo(Foo &) with val: 8 created from: 2
umap.insert(pair)
Foo(const Foo &) with val: 9 created from: 8
umap.emplace(foo3, d)
Foo(Foo &) with val: 10 created from: 3
umap.emplace(11, d)
Foo(int) with val: 11
umap.insert({12, d})
Foo(int) with val: 12
Foo(const Foo &) with val: 13 created from: 12
~Foo() destroying: 12
~Foo() destroying: 8
~Foo() destroying: 3
~Foo() destroying: 2
~Foo() destroying: 1
~Foo() destroying: 0
~Foo() destroying: 13
~Foo() destroying: 11
~Foo() destroying: 5
~Foo() destroying: 10
~Foo() destroying: 7
~Foo() destroying: 9
请注意:
一个unordered_map始终在内部存储Foo对象(而不是,说,Foo *S)作为键,这是在当全部被毁unordered_map被破坏.这里unordered_map的内部键是第13,11,5,10,7和9号.
unordered_map实际上存储了std::pair<const Foo, int>对象,而对象又存储了Foo对象.但要理解"大局观"的emplace()不同之处insert()(见下面突出显示的方框),暂时可以想象这个std::pair对象是完全被动的.一旦你理解了这个"全局的想法",那么重要的是std::pair通过unordered_map引入微妙但重要的技术性来备份和理解这个中间对象的使用方式.将每个的foo0,foo1以及foo2需要2调用之一Foo的复制/移动的构造和图2点的调用Foo的析构函数(如我现在描述):
一个.插入每个foo0并foo1创建一个临时对象(foo4和foo6分别),然后在插入完成后立即调用其析构函数.另外,Foo当unordered_map被销毁时,unordered_map的内部s(foos 5和7)也会调用它们的析构函数.
湾 为了插入foo2,我们首先明确地创建了一个非临时的对象对象(被称为pair),它被称为Foo复制构造函数foo2(创建foo8为内部成员pair).然后我们insert()编辑了这一对,这导致unordered_map再次调用复制构造函数(on foo8)来创建自己的内部副本(foo9).与foos 0和1一样,最终结果是两个析构函数调用此插入,唯一的区别是foo8析构函数仅在我们到达结束时main()被调用,而不是在insert()完成后立即调用.
Emplacing foo3只导致1个复制/移动构造函数调用(在foo10内部创建unordered_map),只有1个调用Foo析构函数.(我稍后会回到这里).
因为foo11,我们直接传递整数11,emplace(11, d)以便在执行时在其方法内unordered_map调用Foo(int)构造函数emplace().与(2)和(3)不同,我们甚至不需要一些预先退出的foo对象来执行此操作.重要的是,请注意只Foo发生了一次对构造函数的调用.
然后我们直接将整数12传递给foo11.与之不同的是insert({12, d}),此调用emplace(11, d)导致对Foo的构造函数的两次调用.
这说明之间的主要"大画面"有什么区别Foo和insert({12, d})是:
尽管使用
Foo几乎总是需要在范围内构造或存在某个foo12对象foo13(后跟复制或移动),但如果使用,insert()那么对emplace()构造函数的任何调用都完全在内部完成insert()(即在Foo方法定义的范围内).为重点,你传递给参数(一个或多个)main()被直接转发到emplace()内部构造函数调用Foo(可选额外的细节:其中此新构造的对象被立即纳入一个unordered_map小号的成员变量",以便没有析构函数被调用时执行的叶子emplace()和没有移动或复制构造函数被调用).
注:究其原因,几乎在几乎总是在我解释)以下.
emplace()被调用Foo的非常量复制构造函数的原因如下:由于我们正在使用unordered_map,编译器知道unordered_map(非const emplace()对象)是一个umap.emplace(foo3, d)构造函数的参数.在这种情况下,最合适的Foo构造函数是非const复制构造emplace().这就是为什么foo3称为复制构造函数而Foo不是.结语:
I.请注意,一个重载Foo实际上相当于 Foo.如所描述的在此cppreference.com页,过载Foo(Foo& f2)(其为过载(2)的umap.emplace(foo3, d)此cppreference.com页)等效于umap.emplace(11, d).
II.然后去哪儿？
一个.玩上面的源代码和研究文档insert()(例如这里)和emplace()(例如这里)在网上找到.如果您正在使用诸如eclipse或NetBeans之类的IDE,那么您可以轻松地让IDE告诉您调用哪个template<class P> std::pair<iterator, bool> insert(P&& value)或哪个重载insert()(在eclipse中,只需将鼠标光标稳定在函数调用上一秒钟).这里有一些试用的代码:
std::cout << "\numap.insert({{" << Foo::foo_counter << ", d}})\n";
umap.insert({{Foo::foo_counter, d}});
//but umap.emplace({{Foo::foo_counter, d}}); results in a compile error!
std::cout << "\numap.insert(std::pair<const Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(std::pair<const Foo, int>({Foo::foo_counter, d}));
//The above uses Foo(int) and then Foo(const Foo &), as expected. but the
// below call uses Foo(int) and the move constructor Foo(Foo&&).
//Do you see why?
std::cout << "\numap.insert(std::pair<Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(std::pair<Foo, int>({Foo::foo_counter, d}));
//Not only that, but even more interesting is how the call below uses all
// three of Foo(int) and the Foo(Foo&&) move and Foo(const Foo &) copy
// constructors, despite the below call's only difference from the call above
// being the additional { }.
std::cout << "\numap.insert({std::pair<Foo, int>({" << Foo::foo_counter << ", d})})\n";
umap.insert({std::pair<Foo, int>({Foo::foo_counter, d})});
//Pay close attention to the subtle difference in the effects of the next
// two calls.
int cur_foo_counter = Foo::foo_counter;
std::cout << "\numap.insert({{cur_foo_counter, d}, {cur_foo_counter+1, d}}) where "
<< "cur_foo_counter = " << cur_foo_counter << "\n";
umap.insert({{cur_foo_counter, d}, {cur_foo_counter+1, d}});
std::cout << "\numap.insert({{Foo::foo_counter, d}, {Foo::foo_counter+1, d}}) where "
<< "Foo::foo_counter = " << Foo::foo_counter << "\n";
umap.insert({{Foo::foo_counter, d}, {Foo::foo_counter+1, d}});
//umap.insert(std::initializer_list<std::pair<Foo, int>>({{Foo::foo_counter, d}}));
//The call below works fine, but the commented out line above gives a
// compiler error. It's instructive to find out why. The two calls
// differ by a "const".
std::cout << "\numap.insert(std::initializer_list<std::pair<const Foo, int>>({{" << Foo::foo_counter << ", d}}))\n";
umap.insert(std::initializer_list<std::pair<const Foo, int>>({{Foo::foo_counter, d}}));
您很快就会发现emplace(std::forward<P>(value))构造函数的重载(请参阅参考资料)最终被使用insert()会对复制,移动,创建和/或销毁多少对象以及何时发生这种情况产生重要影响.
湾 看看当你使用其他容器类(例如emplace()或insert())代替时会发生什么emplace().
C.现在使用一个std::pair对象(只是重命名的副本unordered_map)而不是std::set作为范围类型std::unordered_multiset(即使用std::unordered_map而不是Goo),并查看Foo调用了多少和哪些构造函数.(剧透:有效果,但不是很戏剧化.)