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 回答