在c++Map中插入vs放置vs运算符[]

cvxl0en2  于 2022-12-24  发布在  其他
关注(0)|答案(6)|浏览(131)

我是第一次使用Map,我意识到有很多种方法可以插入元素。你可以使用emplace()operator[]insert(),还有value_typemake_pair这样的变体。虽然有很多关于它们的信息和关于特定情况的问题,但我仍然不能理解全局。所以,我的两个问题是:
1.它们中的每一个相对于其他的优势是什么?
1.有没有必要在标准中增加emplace?有没有什么事情是以前没有它就不可能的?

aemubtdh

aemubtdh1#

在Map的特殊情况下,旧的选择只有两个:operator[]insertinsert的不同风格),所以我将开始解释它们。
operator[]是一个 find-or-add 操作符。它将尝试在map中查找具有给定键的元素,如果它存在,它将返回对存储值的引用。如果它不存在,它将创建一个新元素,并使用默认初始化在适当的位置插入,并返回对它的引用。
insert函数(在单元素风格中)接受一个value_typestd::pair<const Key,Value>),它使用键(first成员)并尝试插入它。因为std::map不允许重复,如果存在一个现有的元素,它将不插入任何东西。
第一个区别是operator[]需要能够构造一个默认初始化的 value,因此它不能用于不能默认初始化的值类型;第二个区别是当已经有一个元素具有给定键时会发生什么; insert函数不会修改Map的状态。而是返回到该元素的迭代器(以及指示它未被插入的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_typeclose,但与调用std::make_pair的返回值不同。因为它足够接近,所以它将创建一个正确类型的临时变量,并复制初始化它,然后将其复制到节点,总共创建两个副本。
这可以通过提供模板参数来解决:

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

但这仍然容易出错,就像在case [1]中显式键入类型一样。
到目前为止,我们有不同的调用insert的方法,需要在外部创建value_type并将该对象复制到容器中,或者如果类型是 *default constructable * 和 assignable,则可以使用operator[](有意只关注m[k]=v),并且它需要一个对象的默认初始化以及将值 * 复制 * 到该对象中。
在C++11中,使用可变模板和完全转发,有一种新的方法可以通过 emplacing(就地创建)将元素添加到容器中。不同容器中的emplace函数基本上做相同的事情:该函数不是获取一个要从其“复制”到容器中的“源”,而是获取将被转发到存储在容器中的对象的构造函数的参数。

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

在[5]中,没有创建std::pair<const K, V>并将其传递给emplace,而是将对tu对象的引用传递给emplaceemplace将它们转发给数据结构中value_type子对象的构造函数。在这种情况下,根本没有完成std::pair<const K,V>的复制。这是emplace优于C++03的优点。在insert的情况下,它不会覆盖Map中的值。
一个我没有想到的有趣问题是,emplace实际上如何为Map实现,在一般情况下,这不是一个简单的问题。

hjzp0vay

hjzp0vay2#

利用右值引用来使用已经创建的实际对象。这意味着不需要调用复制或移动构造函数,这对LARGE对象来说很好!O(log(N))时间。
Insert:有标准左值引用和右值引用的重载,以及要插入的元素列表的迭代器,以及元素所属位置的“提示”。使用“提示”迭代器可以使插入时间降为常数时间,否则为O(log(N))时间。
Operator[]:检查对象是否存在,如果存在,则修改对该对象的引用,否则使用提供的键和值对两个对象调用make_pair,然后执行与insert函数相同的工作,这是O(log(N))时间。
make_pair:只做一对。
没有“需要”在标准中添加emplace。在c++11中,我相信添加了&&类型的引用。这消除了移动语义的必要性,并允许优化某些特定类型的内存管理。特别是右值引用。重载的insert(value_type &&)运算符没有利用in_place语义,因此效率低得多。虽然它提供了处理右值引用的能力,它忽略了它们的关键目的,即就地构造对象。

ogq8wdun

ogq8wdun3#

假设你要把Foo对象添加到set<Foo>对象中,Foo(int)是一个构造函数,Foo有复制/移动构造函数,那么主要的“大画面”区别是:

  • emplace(0)-调用set::emplace(int && my_args)- * 转发 * 给定的参数(即int0)到set::emplace方法定义中某处的Foo构造函数(例如,在该方法的代码中某处有类似Foo(0)的调用)。未调用Foo复制或移动构造函数。
  • insert(0)-它首先调用set::insert(Foo && value)(1)创建Foo对象Foo(0)(因为0具有int类型,但insert需要Foo类型的对象作为输入),用作方法的参数然后(2)该Foo对象(在value中)被用作set::insert方法的定义中某处的Foo(复制或移动)构造函数的自变量。

下面的代码显示了insert()emplace()的区别,它跟踪每个构造函数调用,并在调用发生时告诉你它们的信息。将输出与代码进行比较,insert()emplace()之间的区别就会很明显。
代码很简单,但是有点长,所以为了保存时间,我建议您阅读摘要,然后快速浏览代码(这应该足以理解代码及其输出)。

代码摘要
*Foo:使用static int foo_counter跟踪已构造的Foo对象的总数(或移动,复制,等等)。每个Foo对象存储foo_counter在其本地变量val中创建时的(唯一)值。val == 8的唯一对象称为“foo8“或“Foo 8”(12等也是如此)。每个构造函数/析构函数调用都会打印有关调用的信息(例如,调用Foo(11)将输出“Foo(int) with val: 11“)。
*main()的正文insert() s和emplace() s Foo对象转换为unordered_map<Foo,int>对象umap,调用方式为“umap.emplace(Foo(11), 0);“和“umap.insert({12, 0})“(0只是某个任意的int,它可以是任何值)。

代码

#include <iostream>
#include <unordered_map>
#include <utility>
using namespace std;

//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++;
    cout << "Foo() with val:                " << val << '\n';
  }
  Foo(int value) : val(value) { foo_counter++;
    cout << "Foo(int) with val:             " << val << '\n';
  }
  Foo(Foo& f2) { val = foo_counter++;
    cout << "Foo(Foo &) with val:           " << val
         << " \tcreated from:      \t" << f2.val << '\n';
  }
  Foo(const Foo& f2) { val = foo_counter++;
    cout << "Foo(const Foo &) with val:     " << val
         << " \tcreated from:      \t" << f2.val << '\n';
  }
  Foo(Foo&& f2) { val = foo_counter++;
    cout << "Foo(Foo&&) moving:             " << f2.val
         << " \tand changing it to:\t" << val << '\n';
  }
  ~Foo() { cout << "~Foo() destroying:             " << val << '\n'; }
  Foo& operator=(const Foo& rhs) {
    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
template<> struct std::hash<Foo> {
   size_t operator()(const Foo &f) const { return hash<int>{}(f.val); }
};

int main() {
    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.

    cout << "\nFoo foo0, foo1, foo2, foo3;\n";
    Foo foo0, foo1, foo2, foo3;

    cout << "\numap.insert(pair<Foo, int>(foo0, d))\n";
    umap.insert(pair<Foo, int>(foo0, d));
    //Side note: equivalent to: umap.insert(make_pair(foo0, d));

    cout << "\numap.insert(move(pair<Foo, int>(foo1, d)))\n";
    umap.insert(move(pair<Foo, int>(foo1, d)));
    //Side note: equiv. to: umap.insert(make_pair(foo1, d));
    
    cout << "\npair<Foo, int> pair(foo2, d)\n";
    pair<Foo, int> pair(foo2, d);

    cout << "\numap.insert(pair)\n";
    umap.insert(pair);

    cout << "\numap.emplace(foo3, d)\n";
    umap.emplace(foo3, d);
    
    cout << "\numap.emplace(11, d)\n";
    umap.emplace(11, d);

    cout << "\numap.insert({12, d})\n";
    umap.insert({12, d});

    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(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(move(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

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()之间的主要“大图片”差异是:
而使用insert()almost**†**always 需要在main()的作用域中构造或预先存在某个Foo对象(后面是拷贝或移动),如果使用emplace(),则对Foo构造函数的任何调用都完全在unordered_map内部完成(即在emplace()方法定义的作用域内)。传递给emplace()的键的参数直接转发给unordered_map::emplace()定义内的Foo构造函数调用(可选的附加细节:其中该新构造的对象被立即合并到X1 M66 N1 X的成员变量之一中,使得当执行离开X1 M67 N1 X时不调用析构函数,并且不调用移动或复制构造函数)。

**†*上述“ 几乎总是 ”中的“ 几乎 *”是因为insert()的一个重载实际上 * 等价于 * emplace()。如in this cppreference.com page所述,重载template<class P> pair<iterator, bool> insert(P&& value)(这是insert()在该页上的重载(2))等价于emplace(forward<P>(value))。由于我们对差异感兴趣,我将忽略这个重载,不再提及这个特殊的技术细节。

逐步执行代码

现在,我将详细介绍代码及其输出。
1.首先,注意unordered_map总是在内部存储Foo对象(而不是Foo *)作为密钥,当unordered_map被销毁时,这些对象也会被销毁,这里,unordered_map的内部密钥是foos 13、11、5、10、7和9。

  • 所以从技术上讲,我们的unordered_map实际上存储pair<const Foo, int>对象,而pair<const Foo, int>对象又存储Foo对象。(见上面的高亮框),可以暂时把pair对象想象成完全被动的,一旦你理解了这个“大画面想法”,“重要的是,然后备份并理解X1 M85 N1 X如何使用这个中间X1 M84 N1 X对象引入微妙但重要的技术细节。

  • insert()foo0foo1foo2进行操作需要对Foo的复制/移动构造函数中的一个进行2次调用,以及对Foo的析构函数进行2次调用(如我现在所描述的):

  • insert()分别使用foo0foo1创建了一个临时对象(分别为foo4foo6),其析构函数在插入完成后立即被调用。一旦执行到达X1 M101 N1 X的末尾,当X1 M100 N1 X被销毁时,X1 M97 N1 X的内部X1 M98 N1 X(其是X1 M99 N1 X5和7)也调用它们的析构函数。

  • 对于insert()foo2,我们首先显式创建一个非临时对对象(称为pair),它在foo2上调用Foo的复制构造函数(创建foo8作为pair的内部成员)。然后,我们对该对进行insert()处理,这导致unordered_map再次调用复制构造函数(在foo8上)创建自己的内部副本(foo9)。与foo的0和1一样,最终结果是对该insert() Ionic 两个析构函数调用,唯一的区别是foo8 "的析构函数仅在到达main()末尾时调用,而不是在insert()完成后立即调用。

  • emplace()foo3的调用只导致了一次复制/移动构造函数调用(在unordered_map内部创建foo10)和一次对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在其emplace()方法中执行时调用Foo(int)构造函数。(2)及(3),我们甚至不需要一些预先存在的foo对象来做这件事。注意,只发生了对Foo构造函数的1次调用(这创建了foo11)。

  • 然后我们直接将整数12传递给insert({12, d}),与emplace(11, d)不同(调用emplace(11, d)只调用了一次Foo构造函数),这次调用insert({12, d})导致了两次Foo构造函数的调用(创建了foo12foo13)。

尾声

从这里去哪里?
a.使用上述源代码并研究insert()的文档(例如here)和emplace()(例如here)。如果您使用的是Eclipse或NetBeans之类的IDE,则可以轻松地让IDE告诉您正在调用insert()emplace()的哪个重载(在eclipse中,只需将鼠标光标稳定地停留在函数调用上一秒钟)。下面是一些可以尝试的代码:

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!

cout << "\numap.insert(pair<const Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(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?
cout << "\numap.insert(pair<Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(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 { }.
cout << "\numap.insert({pair<Foo, int>({" << Foo::foo_counter << ", d})})\n";
umap.insert({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;
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}});

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(initializer_list<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".
cout << "\numap.insert(initializer_list<pair<const Foo, int>>({{" << Foo::foo_counter << ", d}}))\n";
umap.insert(initializer_list<pair<const Foo, int>>({{Foo::foo_counter, d}}));

您很快就会看到,unordered_map最终使用的是pair构造函数的哪个重载(请参见reference),这对复制、移动、创建和/或销毁对象的数量以及这些操作何时发生有重要影响。
b.看看使用其他容器类(例如setunordered_multiset)代替unordered_map时会发生什么。
c.现在使用Goo对象(只是Foo的重命名副本)而不是int作为unordered_map中的范围类型(即使用unordered_map<Foo, Goo>而不是unordered_map<Foo, int>),并查看调用了多少个以及哪些Goo构造函数。(剧透:有一个效果,但不是很戏剧化。)

des4xlb0

des4xlb04#

除了优化机会和更简单的语法之外,insert和embplacement之间的一个重要区别是后者允许 * 显式 * 转换(这适用于整个标准库,不仅仅适用于map)。
下面是一个示例:

#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
}

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

yacmzcpb

yacmzcpb5#

还有一个问题尚未在其他答案中讨论,它适用于std::map以及std::unordered_mapstd::setstd::unordered_set

  • insert使用key对象,这意味着如果key已经存在于容器中,则它不需要分配节点
  • emplace需要首先构造密钥,这通常需要在每次调用时分配节点

从这个Angular 来看,如果容器中已经存在键,那么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。(当然,对于不可复制和不可移动的密钥,我们不能使用inserttry_emplace,因此没有其他选项。)
6psbrbz9

6psbrbz96#

在功能或输出方面,它们都是相同的。
对于两种大内存,对象置入都是内存优化的,不使用复制构造函数
简单详细说明https://medium.com/@sandywits/all-about-emplace-in-c-71fd15e06e44

相关问题