18

地图插入有两种方式：

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.' default construct of typeof(val)' 2. assignment 第二种方式是 1. assignment 2. ' copy construct of typeof(val)'

4

6 回答 6

20

两者完成不同的事情。 

m[key] = val;

key如果不存在，将插入一个新的键值对，或者key如果它已经存在，它将覆盖映射到的旧值。 

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

key如果该对尚不存在，则只会插入该对，它永远不会覆盖旧值。因此，请根据您想要完成的任务进行选择。
对于更有效的问题：profile。:P 可能是我想说的第一种方式。分配（又名副本）是两种方式的情况，因此唯一的区别在于构造。众所周知并且应该实现，默认构造基本上应该是无操作的，因此非常有效。副本就是这样 - 副本。所以在方式一中我们得到一个“no-op”和一个副本，在方式二中我们得到两个副本。
编辑：最后，相信你的分析告诉你的。我的分析不像@Matthieu 在他的评论中提到的那样，但这是我的猜测。:)

然后，我们有 C++0x 来了，第二条路上的双重复制将是无效的，因为现在可以简单地移动这对。所以最后，我想还是回到我的第一点：用正确的方式完成你想做的事情。

于 2011-04-17T07:39:50.920 回答
7

在具有大量内存的轻负载系统上，此代码：

#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

或重复运行的类似值。所以插入（在这种情况下）稍微快一点。

于 2011-04-17T09:48:46.117 回答
2

性能方面，我认为它们大体上是相同的。带有大对象的地图可能会有一些例外情况，在这种情况下，您应该使用 [] 或者可能创建的临时对象少于“插入”的 emplace。有关详细信息，请参阅此处的讨论。

但是，如果您在插入运算符上使用“提示”功能，则可以在特殊情况下获得性能提升。因此，从这里查看选项2：

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

如果您给出一个好的提示（如果您知道要在地图后面添加东西，通常是这种情况），“插入”操作可以减少到恒定时间（从 log(n) 开始）。

于 2015-04-22T18:37:48.437 回答
0

我们必须通过提到相对性能也取决于被复制对象的类型（大小）来改进分析。

我用（int -> set）的地图做了一个类似的实验（对nbt）。我知道这是一件很糟糕的事情，但是，这说明了这种情况。“值”，在这种情况下是一组整数，其中有 20 个元素。

我执行 []= Vs 的一百万次迭代。插入操作并执行 RDTSC/iter-count。

[] = 设置 | 10731 次循环

插入（make_pair<>）| 26100 次循环

它显示了由于复制而增加的惩罚幅度。当然，CPP11(move ctor's) 会改变画面。

于 2014-11-20T21:33:19.307 回答
0

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

真正取决于您要解决的问题。

1）如果你只是想插入知道它还不存在的值，那么 [] 会做两件事：a）检查项目是否存在 b）如果它不存在将创建对并执行什么插入确实（O（logN）的双重工作），所以我会使用插入。

2）如果您不确定它是否存在，那么 a）如果您确实通过执行 if( map.find( item ) == mp.end() ) 上面几行来检查该项目是否存在某处，然后使用插入，因为双重工作 [] 会执行 b）如果你没有检查，那么它取决于，因为插入不会修改值，如果它在那里，[] 会，否则它们是相等的

于 2017-03-15T01:24:39.833 回答
0

我的答案不是效率而是安全，这与选择插入算法有关：

[]andinsert()调用将触发元素的析构函数。如果你的析构函数内部有关键行为，这可能会产生危险的副作用。

在这样的危险之后，我不再依赖 STL 的隐式延迟插入功能，并且总是使用显式检查我的对象是否在其 ctors/dtors 中有行为。

请参阅此问题： 将对象添加到 std::list 时调用对象的析构函数

于 2019-09-19T07:45:32.543 回答