STL map插入效率：[] vs. insert

Question

有两种映射插入的方式：

m[key] = val;

或者

m.insert(make_pair(key, val));

我的问题是哪一个操作更快？通常人们说第一种方式较慢，因为STL标准首先会在map中插入一个默认元素，如果'key'不存在，然后将'val'赋值给该默认元素。

但是我不认为第二种方式更好，因为使用'make_pair'实际上比pair<T1, T2>(key, val)更方便。无论如何，它们都执行了两个赋值操作，一个是将'key'赋值给'pair.first'，另一个是将'val'赋值给'pair.second'。创建了pair之后，map插入由'pair.second'初始化的元素。

因此，第一种方式是1. 'typeof(val)'的默认构造 2. 赋值操作；第二种方式是1. 赋值操作 2. 'typeof(val)'的复制构造。

- DerekFOol

---

参见：https://dev59.com/VXI-5IYBdhLWcg3w9thw - johnsyweb

Answer 1

两者实现不同的功能。

m[key] = val;

如果这个key还不存在，那么会插入一个新的键值对，否则它将会覆盖已经存在的key所映射的旧值。

m.insert(make_pair(key, val));

如果key不存在，它只会插入键值对，永远不会覆盖旧值。因此，请根据您要完成的任务选择相应的方法。
对于问题“哪种方式更有效率”：请进行性能分析。:P 我可能会首选第一种方式。赋值（又称复制）对两种方式都是必需的，因此唯一的区别在于构建。正如我们所知道并应该实施的那样，默认构造应基本上是一个无操作，并且因此非常高效。复制就是这样——复制。因此，在第一种方法中，我们获得了一个“无操作”和一个副本，在第二种方法中，我们获得了两个副本。
编辑：最终，相信您的性能分析结果。我的分析像@Matthieu在他的评论中提到的那样是错误的，但那是我的猜测。:)

---

随着C++0x的到来，第二种方式上的双重复制将会消失，因为现在可以直接移动对。因此，我认为最终回归到我的第一点：使用正确的方式完成您想要做的事情。

- Xeo

---

+1 是因为选择语义而不是性能。不过，我认为分析有点偏差。第一种方式应该会更慢（通过默认构造），因为在两种情况下都复制了键和值。 - Matthieu M.

@Matthieu：嗯，确实如此。我会稍微编辑一下，但是会让我的分析保持不变。这再次表明，性能分析真的可以告诉你什么更快。 - Xeo

std::map<>::operator[] 不会默认初始化值，它会进行“值初始化”，因此像 std::map<K, std::array<int, 1000>>::operator[] 这样的操作可能会非常浪费资源。 - ildjarn

Answer 2

在一个内存充足、负载较轻的系统上，这段代码为：

#include <map>
#include <iostream>
#include <ctime>
#include <string>

using namespace std;

typedef map <unsigned int,string> MapType;
const unsigned int NINSERTS = 1000000;

int main() {
    MapType m1;
    string s = "foobar";
    clock_t t = clock();
    for ( unsigned int i = 0; i < NINSERTS; i++ ) {
        m1[i] = s;
    }
    cout << clock() - t << endl;
    MapType m2;
    t = clock();
    for ( unsigned int i = 0; i < NINSERTS; i++ ) {
        m2.insert( make_pair( i, s ) );
    }
    cout << clock() - t << endl;
}

生成：

1547
1453

在重复运行时，插入操作的速度（在这种情况下）略微更快。

- user2100815

Answer 3

从性能方面来看，我认为它们在一般情况下大致相同。但是在具有大型对象的地图中可能会有一些例外情况，在这种情况下，您应该使用[]或者也许是emplace函数，因为它比“insert”创建较少的临时对象。详情请参见此处的讨论。

然而，如果您在插入运算符上使用“hint”函数，您可以在特殊情况下获得性能提升。因此，查看此处选项2和这里：

iterator insert (const_iterator position, const value_type& val);

“插入”操作如果有良好的提示（通常情况下，如果您知道要将东西添加到映射的末尾），可以将其时间复杂度从log(n)降至常数时间。

- Craig Robinson

Answer 4

我的回答不涉及效率，而是安全问题，这与选择插入算法有关：

[]和insert()调用将触发元素的析构函数。如果您的析构函数具有重要行为，则可能会产生危险的副作用。

因此，在遇到这种情况之后，我停止依赖STL的隐式延迟插入功能，并始终使用明确的检查来确定我的对象在其构造函数/析构函数中是否存在行为。

请参见以下问题：将对象添加到std::list时调用析构函数

- kakyo

Answer 5

我的看法是：值得提醒的是，映射是一种平衡二叉树，大多数修改和检查需要O(logN)的时间。

这真的取决于你要解决的问题。

1）如果你只想插入值，知道它还不存在，那么[]会做两件事情： a）检查项目是否存在 b）如果不存在，将创建一对并执行插入操作（O(logN)的双倍工作），因此我会使用insert。

2）如果你不确定它是否存在，那么a）如果你通过执行类似if(map.find(item)==mp.end())的代码行在某个地方检查了该项是否存在，则使用insert，因为[]会执行双倍工作；b）如果你没有检查，则取决于情况，因为如果存在，insert不会修改值，[]会修改值，否则它们是相等的。

- Pavel P

Answer 6

我们必须通过提及被复制对象的类型（大小）来精细化分析。

我进行了一项类似于nbt的实验，使用(int -> set)的映射。我知道这是一件可怕的事情，但对于这种情况很有说明性。在这种情况下，“值”是一个包含20个元素的int集合。

我执行了一百万次[] = Vs.插入操作，并进行RDTSC/iter-count测量。

[] = set | 10731 cycles

insert(make_pair<>) | 26100 cycles

它显示了由于复制而添加的惩罚的数量级。当然，CPP11(move ctor's)将改变这种情况。

- KalyanS