我第一次使用地图,我意识到有很多方法可以插入元素。您可以使用emplace()
, operator[]
or insert()
, 以及使用value_type
or之类的变体make_pair
。虽然有很多关于所有这些的信息和关于特定案例的问题,但我仍然无法理解大局。所以,我的两个问题是:
他们每个人比其他人有什么优势?
是否需要在标准中添加 emplace?没有它,有什么是不可能的吗?
我第一次使用地图,我意识到有很多方法可以插入元素。您可以使用emplace()
, operator[]
or insert()
, 以及使用value_type
or之类的变体make_pair
。虽然有很多关于所有这些的信息和关于特定案例的问题,但我仍然无法理解大局。所以,我的两个问题是:
他们每个人比其他人有什么优势?
是否需要在标准中添加 emplace?没有它,有什么是不可能的吗?
在地图的特定情况下,旧选项只有两个: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
将返回 a 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
在 [5] 中,std::pair<const K, V>
没有创建并传递给emplace
,而是传递对t
和u
对象的引用,然后emplace
将它们转发给value_type
数据结构内的子对象的构造函数。在这种情况下,根本不会复制std::pair<const K,V>
,这是emplace
C++03 替代方案的优势。在这种情况下,insert
它不会覆盖地图中的值。
我没有考虑过的一个有趣的问题是如何emplace
为地图实际实现,这在一般情况下不是一个简单的问题。
Emplace:利用右值引用来使用您已经创建的实际对象。这意味着不调用复制或移动构造函数,这对 LARGE 对象有好处!O(log(N)) 时间。
插入:具有标准左值引用和右值引用的重载,以及要插入的元素列表的迭代器,以及关于元素所属位置的“提示”。使用“提示”迭代器可以将插入时间缩短到恒定时间,否则为 O(log(N)) 时间。
Operator[]:检查对象是否存在,如果存在,则修改对该对象的引用,否则使用提供的键和值在两个对象上调用make_pair,然后做与插入函数相同的工作。这是 O(log(N)) 时间。
make_pair:只做一对。
没有“需要”将 emplace 添加到标准中。在 c++11 中,我相信添加了 && 类型的引用。这消除了移动语义的必要性,并允许优化某些特定类型的内存管理。特别是右值引用。重载的 insert(value_type &&) 运算符没有利用 in_place 语义,因此效率低得多。虽然它提供了处理右值引用的能力,但它忽略了它们的关键目的,即就地构造对象。
以下代码可以帮助您理解insert()
与emplace()
.
代码摘要:Foo
该类使用static int foo_counter
跟踪Foo
迄今为止已构造/移动的对象总数。每个Foo
对象还将foo_counter
(在其创建时)的值存储在局部变量中int val;
,如果val
是,8
则该Foo
对象将被称为“ foo8
”或“ Foo
8”等。每次Foo
调用构造函数时,它都会输出有关调用的信息stdout
(例如调用Foo(11)
将输出“Foo(int) with val: 11”)。中的代码main()
打印到stdout
将要执行的语句(例如umap.emplace(11, d)
),然后执行它。
#include <iostream>
#include <unordered_map>
#include <utility>
//Foo simply outputs what constructor is called with what value.
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;
int d; //Some int that will be umap's value. It is not important.
//Print the statement to be executed and then execute it.
std::cout << "\nFoo foo0, foo1, foo2, foo3;\n";
Foo foo0, foo1, foo2, foo3;
std::cout << "\numap.insert(std::pair<Foo, int>(foo0, d))\n";
umap.insert(std::pair<Foo, int>(foo0, d));
//Side note: 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)));
//Side note: 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 foo0, foo1, foo2, foo3;
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
insert()
此代码及其输出显示和之间的主要“大图”区别emplace()
是:
虽然 using
insert()
几乎总是需要在 ' 的范围内构造或预先存在某些Foo
对象main()
(随后是复制或移动),但如果 usingemplace()
则对构造函数的任何调用Foo
完全在内部完成unordered_map
(即在emplace()
方法定义的范围内)。您传递给的键的参数emplace()
直接转发到 's 定义中的Foo
构造函数调用unordered_map::emplace()
(可选的附加详细信息:此新构造的对象立即合并到unordered_map
's 的成员变量之一中,以便在以下情况下不调用析构函数执行离开emplace()
并且不调用移动或复制构造函数)。
注意:上面“几乎总是”中的“几乎”的原因是因为一个重载实际上相当于. 如此 cppreference.com 页面中所述,重载(即此 cppreference.com 页面上的重载(2) )等效于. 我不会再讨论这个特定的技术性问题。insert()
emplace()
template<class P> std::pair<iterator, bool> insert(P&& value)
insert()
emplace(std::forward<P>(value))
我现在将详细介绍代码及其输出。
unordered_map
总是在内部将Foo
对象(而不是Foo *
s)存储为键,当 被销毁时这些对象都将unordered_map
被销毁。在这里,unordered_map
的内部键是 foos 13、11、5、10、7 和 9。unordered_map
实际上存储了std::pair<const Foo, int>
对象,而对象又存储了Foo
对象。但要理解与(见上面突出显示的方框)有何emplace()
不同的“大局观”,可以暂时将这个对象想象为完全被动的。一旦你理解了这个“大局观”,重要的是要备份并理解这个中间对象的使用如何引入微妙但重要的技术细节。insert()
std::pair
std::pair
unordered_map
insert()
foo0
对,foo1
和中的每foo2
一个进行调用 2 次调用其中一个Foo
的复制/移动构造函数和 2 次调用Foo
的析构函数(正如我现在描述的那样):
insert()
分别创建一个临时对象(foo0
和) ,然后在插入完成后立即调用其析构函数。此外,当执行到.foo1
foo4
foo6
unordered_map
Foo
foo
unordered_map
main()
insert()
foo2
,我们首先显式创建了一个非临时的对对象(称为pair
),该对象调用了Foo
的复制构造函数foo2
(创建foo8
为 的内部成员pair
)。然后我们insert()
编辑了这对,这导致unordered_map
再次调用复制构造函数(on foo8
)来创建它自己的内部副本(foo9
)。与foo
s 0 和 1 一样,最终结果是对这个insert()
ion 的两次析构函数调用,唯一的区别是foo8
只有在我们到达末尾时才调用析构函数,main()
而不是在完成后立即调用insert()
。emplace()
ingfoo3
导致仅 1 次复制/移动构造函数调用(在foo10
内部创建unordered_map
)和仅 1 次调用Foo
的析构函数。调用umap.emplace(foo3, d)
被调用Foo
的非常量复制构造函数的原因如下:由于我们使用emplace()
的是,编译器知道foo3
(非常量Foo
对象)是某个Foo
构造函数的参数。在这种情况下,最合适Foo
的构造函数是非常量复制构造函数Foo(Foo& f2)
。这就是为什么没有umap.emplace(foo3, d)
调用复制构造函数的原因umap.emplace(11, d)
。
对于foo11
,我们直接将整数 11 传递给,emplace(11, d)
以便在其方法内执行时unordered_map
调用Foo(int)
构造函数。emplace()
与 (2) 和 (3) 不同,我们甚至不需要一些预先存在的foo
对象来执行此操作。重要的是,请注意只Foo
发生了 1 次对构造函数的调用(它 created foo11
)。
然后我们直接将整数 12 传递给insert({12, d})
. 与 with 不同emplace(11, d)
(召回导致只有 1 次调用Foo
构造函数),此调用insert({12, d})
导致两次调用Foo
的构造函数(创建foo12
和foo13
)。
结语:从这里去哪里?
一个。玩弄上面的源代码并学习在线找到的insert()
(例如这里)和emplace()
(例如这里)的文档。如果您使用的是 Eclipse 或 NetBeans 等 IDE,那么您可以轻松地让您的 IDE 告诉您哪个重载insert()
或emplace()
正在被调用(在 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}}));
您很快就会看到std::pair
构造函数的哪个重载(请参阅参考资料)最终被使用unordered_map
会对复制、移动、创建和/或销毁的对象数量以及这一切发生的时间产生重要影响。
湾。看看当你使用其他容器类(例如std::set
or std::unordered_multiset
)而不是std::unordered_map
.
C。现在使用一个Goo
对象(只是 的重命名副本Foo
)而不是 anint
作为 an 中的范围类型unordered_map
(即使用unordered_map<Foo, Goo>
而不是unordered_map<Foo, int>
),并查看调用了多少以及哪些Goo
构造函数。(剧透:有效果,但不是很戏剧化。)
除了优化机会和更简单的语法之外,插入和就位之间的一个重要区别是后者允许显式转换。(这适用于整个标准库,而不仅仅是地图。)
这是一个示例来演示:
#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
}
诚然,这是一个非常具体的细节,但是当您处理用户定义的转换链时,请牢记这一点。
在功能或输出方面,它们都是相同的。
对于两个大内存,对象 emplace 是内存优化的,不使用复制构造函数
对于简单的详细解释 https://medium.com/@sandywits/all-about-emplace-in-c-71fd15e06e44