C++:value_type与make_pair,对于地图插入更快？

Question

typedef map<KeyType, ValType> KVMap;
KVMap kvmap;

kvmap.insert( KVMap::value_type( key, val ) );
kvmap.insert( make_pair( key, val ) );

要插入STL地图的上述哪个选项总是更快？为什么？

注意:我很清楚这insert()比[]=用于向地图添加(不更新)键值对更快.请假设我的查询是关于添加,而不是更新.因此我限制它insert().

Answer 1

有可能第一个将是'epsilon-faster',因为这个(从标准中的23.3.1):

typedef pair<const Key, T> value_type;

[...]

pair<iterator, bool> insert(const value_type& x);

• 在第一个版本中,您可以直接构造期望的相应类型 std::map<K,V>::insert

• 在第二个版本中,std::pair涉及使用模板构造函数的转换.事实上,std::make_pair将最有可能推断出其模板参数KeyType和ValType信息,并返回一个std::pair<KeyType, ValType>.

  这与参数类型不匹配std::map<K,V>::insert,即std::pair<const KeyType, ValType>(const首先是- 限定的差异).该std::pair转换构造函数将被用来建立一个std::pair<const K, V>从std::pair<K, V>.

公平地说,我不相信你甚至可以衡量差异(我甚至不确定流行的编译器实际上会为这些编译生成不同的代码).

Answer 2

这里实际上是要做出一个参数value_type上make_pair.这是因为,出于各种神秘的原因,make_pair通过值接受其参数.另一方面,value_typefor的别名std::pair<const Key, value>将使用const引用传递的参数调用其构造函数.make_pair相对于参考传递,传递价值可能会导致效率下降,理论上这可能会对您的计划产生显着影响.

需要担心的另一个问题make_pair是,make_pair通常会创建一对类型std::pair<Key, Value>而不是std::pair<const Key, Value>内部需要的类型map.这意味着可能会有另一个不必要的副本,这次是pair为了使转换正常工作.

简而言之,使用make_pair可能会导致两个完全不必要的键和值的副本,而使用value_type构造函数则没有.

Answer 3

这只是一个补充。

insert( make_pair(...) ) 由于其他回答者提到的原因，名义上调用复制构造函数 4 次。

insert( value_type(...) ) 调用复制构造函数 2 次。

operator[] 在典型的实现中，调用默认构造函数一次并调用复制构造函数两次。operator[]默认构造函数在for 内部调用insert( value_type( ..., mapped_type() ) )。复制构造函数被调用一次以复制 的insert()argument( pair) ，并调用一次以复制构造映射的内部节点。

因此，如果您使用insertwith make_pair，则不能说它insert总是比operator[]添加更快。或许，这要视情况而定。如您所知，鉴于上述情况，emplace提出了新标准。