[C++] 在c ++ map中插入vs emplace vs operator []


Answers

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

插入:具有标准左值引用和右值引用的重载,以及要插入的元素列表的迭代器,以及元素所属位置的“提示”。 使用“提示”迭代器可以使时间插入占用时间,否则它是O(log(N))时间。

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

make_pair:只不过是一对。

没有必要为标准添加emplace。 在c ++ 11中,我相信&&类型的引用被添加。 这消除了移动语义的必要性,并允许优化某些特定类型的内存管理。 特别是右值引用。 重载插入(value_type &&)运算符没有利用in_place语义,因此效率更低。 虽然它提供了处理右值引用的能力,但它忽略了它们的关键目的,这就是对象的构建。

Question

我第一次使用地图,我意识到有很多方法可以插入元素。 您可以使用emplace()operator[]insert() ,以及使用value_typemake_pair等变体。 虽然关于所有这些信息以及关于特定情况的问题都有很多信息,但我仍然无法理解大局。 所以,我的两个问题是:

  1. 他们每个人的优势是什么?

  2. 有没有必要为标准添加emplace? 没有它之前有什么是不可能的吗?




下面的代码可以帮助你理解insert()emplace()不同之处:

#include <iostream>
#include <unordered_map>
#include <utility>

struct Foo {
  static int foo_counter;
  int val;

  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

请注意:

  1. 一个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() emplace()不同的“ emplace()图”(请参阅​​下面突出显示的框), 暂时将此std::pair对象视为完全被动是可以的。 一旦你理解了这个“大局观念”,重要的是要备份和理解unordered_map如何使用这个中间std::pair对象引入微妙但重要的技术。
  2. 插入foo0foo1foo2每一个都需要2次调用Foo的复制/移动构造函数和2次调用Foo的析构函数(如我现在描述的):

    一个。 插入foo0foo1每一个foo0创建一个临时对象(分别为foo4foo6 ),然后在插入完成后立即调用析构函数。 另外,unordered_map的内部Foo (它们是foos 5和7)在unordered_map被销毁时也调用了它们的析构函数。

    湾 为了插入foo2 ,我们首先创建了一个非临时对( foo8 ),它叫做Foo的拷贝构造函数,然后插入它,导致unordered_map再次调用拷贝构造函数来创建一个内部拷贝( foo9 )。 与foos 0和1一样,最终的结果是两次析构函数调用这个插入,唯一的区别是只有当我们到达main()的末尾时才调用foo8的析构函数。

  3. 放置foo3只导致1次复制/移动构造函数调用(内部创建foo10 ),并且只有1次调用Foo的析构函数。 (我将在稍后回顾)。

  4. 对于foo11 ,我们直接传递了整数11,以便unordered_map将调用Foo(int)构造函数。 与(3)不同,我们甚至不需要一些预先存在的foo对象来做到这一点。

这显示了insert()emplace()之间的主要“大图”区别是:

而使用insert() 几乎总是需要在main()的作用域(后跟一个拷贝或移动)中构造或存在某个Foo对象,如果使用emplace()则任何对构造函数的调用完全是在unordered_map (即在emplace()方法定义的范围内)。 您传递给emplace()的键的参数直接转发到unordered_mapFoo构造函数调用(可选的附加细节:这个新构造的对象立即被并入到unordered_map的成员变量之一中,从而没有析构函数在执行离开emplace()时被调用,并且不调用移动或复制构造函数)。

注意: 几乎总是几乎总是在下面的I)中解释。

  1. 继续:调用umap.emplace(foo3, d)调用Foo的非const拷贝构造函数的原因如下:由于我们使用emplace() ,编译器知道foo3 (非const Foo对象)是意图成为一些Foo构造函数的参数。 在这种情况下,最合适的Foo构造函数是非const复制构造Foo(Foo& f2) 。 这就是为什么umap.emplace(foo3, d)调用复制构造函数而umap.emplace(11, d)没有。

结语:

I.请注意, insert()一个重载实际上等同于 emplace() 。 如本cppreference.com页面所述,重载template<class P> std::pair<iterator, bool> insert(P&& value) (这是cppreference.com页面上insert()重载(2))是等价的emplace(std::forward<P>(value))

II。 然后去哪儿?

一个。 玩弄上面的源代码,并研究在线发现的insert() (例如here )和emplace() (例如here )的文档。 如果您使用的是IDE(例如eclipse或NetBeans),那么您可以轻松地让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 to 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 cals
// 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构造函数(请参阅reference )的哪个重载最终会被unordered_map使用,这可能会影响复制,移动,创建和/或销毁多少个对象以及何时发生这种情况。

湾 看看当你使用一些其他容器类(例如std::setstd::unordered_multiset )而不是std::unordered_map

C。 现在使用Goo对象(只是Foo的重命名副本)而不是int作为unordered_map的范围类型(​​即,使用unordered_map<Foo, Goo>而不是unordered_map<Foo, int> ),并查看有多少个Goo构造函数叫做。 (破坏者:有效果,但不是很戏剧性。)