STL地图插件效率：[]对插入

有地图插入的方式有两种：STL地图插件效率：[]对插入

m[key] = val;

或者

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

我的问题是，其运算速度更快？人们通常会说第一个比较慢，因为STL标准最初'插入'一个默认元素，如果'key'不存在于map中，然后将'val'赋给默认元素。

但我没有看到第二种方式更好，因为'make_pair'。 make_pair实际上是一个方便的方式，与pair<T1, T2>(key, val)进行比较。无论如何，他们都做了两个任务，一个是将'key'分配给'pair.first'，另外两个是将'val'分配给'pair.second'。配对完成后，map插入由'pair.second'初始化的元素。

所以第一种方式是1“default construct of typeof(val)” 2.分配第二种方式是1分配2“copy construct of typeof(val)”

来源

2011-04-17 DerekFOol

另请参阅：http://stackoverflow.com/q/1594631/78845 – Johnsyweb 2011-04-17 07:44:13

两个完成不同的事情。

m[key] = val;

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

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

只会插入一对，如果key不存在，它绝不会覆盖旧值。所以，根据你想要完成的选择。
对于什么更有效的问题：配置文件。：P可能是我说的第一种方式。这个任务（aka copy）就是这种情况，所以唯一的区别在于施工。正如我们都知道并且应该实施的那样，默认的建设应该基本上是无效的，因此非常有效。副本就是 - 副本。所以在方法一中我们得到一个“禁用”和一个副本，在方法二中我们得到两个副本。
编辑：最后，请相信你的分析能告诉你什么。我的分析就像@Matthieu在他的评论中提到的那样，但那是我的猜测。 :)

以后，我们的C++ 0x的到来，并在第二路双副本将化为乌有，因为该货币对可以简单地搬到现在。所以最后，我认为它回到了我的第一点：用正确的方式来完成你想要做的事情。

来源

2011-04-17 07:39:50 Xeo

+1用于从语义选择而非性能。我认为，分析有点不合适。第一种方式应该比较慢（通过默认构造），因为在这两种情况下键和值都被复制。 – 2011-04-17 10:48:44

@Matthieu：恩，真够的。我会编辑一下，但会让我的分析保持。这再次表明，分析将真正告诉你什么更快。 – Xeo 2011-04-17 10:52:14

'std :: map <> :: operator []'不默认 - 初始化值，它_value-initializes_ values，因此像'std :: map > :: operator []'可能会非常浪费。 – ildjarn 2012-05-02 21:06:52

在用大量的存储器，这代码轻负载系统：

#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-17 09:48:46

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

我做了一个类似的实验（以NBT）与（int - >集）的地图。我知道这是一件可怕的事情，但是，对于这种情况来说也是说明性的。在这个例子中，“值”是一组整数，其中有20个元素。

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

[] = set | 10731个周期

insert（make_pair <>）| 26100个周期

它显示了由于复制而增加的罚分的大小。当然，CPP11（move ctor's）会改变图片。

来源

2014-11-20 21:33:19 KalyanS

表现明智我认为他们大体上是相同的一般。对于包含大对象的地图可能会有一些例外情况，在这种情况下，您应该使用[]或者可能会创建比'insert'更少的临时对象的emplace。有关详细信息，请参阅讨论here。

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

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

“插入”操作可以降低到一定的时间（从数（n））的，如果你给一个很好的提示（通常情况下，如果你知道你正在添加东西在你的地图的后面）。

来源

2015-04-22 18:37:48

我对它的看法：值得提醒的是，地图是一个平衡的二叉树，大部分的修改和检查都需要O（logN）。

确实取决于您尝试解决的问题。

1）如果你只是想插入值，知道它现在还没有，则[]会做两件事情：一）检查项目是否有或没有二）如果它不存在将创建一对并做什么插入（ O（logN））的双重工作，所以我会使用插入。如果你不确定它是否存在或不存在，那么a）如果你通过做类似if（map.find（item）== mp.end几行上面的某处，然后使用插入，因为双重工作[]会执行b）如果你没有检查，那么它取决于，原因插入不会修改值，如果它在那里，[]会，否则他们等于

来源

2017-03-15 01:24:39

STL地图插件效率：[]对插入

回答

相关问题