C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入

栏目: C++ · 发布时间: 6年前

内容简介:因为加入测量,就会导致误差。我已经尽量将环境影响降低,但是还是难免有误差。大家可以通过文后附的工程自行测量,结果可能和我存在一定的出入。文中将测试vector、list、forward_list、deque、set(multiset)、unordered_set(unordered_multiset)、map(multimap)和unordered_map(unordered_multimap)。没有讨论stack、queue和priority_queue,是因为它们底层是使用deque或者vector实

因为加入测量,就会导致误差。我已经尽量将环境影响降低,但是还是难免有误差。大家可以通过文后附的工程自行测量,结果可能和我存在一定的出入。

文中将测试vector、list、forward_list、deque、set(multiset)、unordered_set(unordered_multiset)、map(multimap)和unordered_map(unordered_multimap)。没有讨论stack、queue和priority_queue,是因为它们底层是使用deque或者vector实现的。

template <class T, class Container = deque<T> > class stack;
template <class T, class Container = deque<T> > class queue;

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

增加和删除操作将从容器的头部、中部、尾部三个位置进行对比;这儿的三个位置并非是指其物理地址关系,而是指通过迭代器表现的位置关系。

遍历分为从头部和尾部两个方向遍历;

查找操作只对比set和map系列容器。因为其他容器的查找都需要遍历进行对比,性能远不及这两类容器。

插入

头部插入

元素个数>15000

C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入
insert_begin_16384_highest

vector性能最差,且和其他容器相比,要差好几倍。我们再看看其他容器的表现

C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入
insert_begin_16384

表现最好的是deque。

元素个数<1024

C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入
insert_begin_1024_highest

元素个数在900左右以上时,vector的效率开始差于所有的容器。

元素个数在650到900之间,list的效率比其他容器都差。

元素个数<256

C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入
insert_begin_256_highest

vector的效率要高于除了unordered_set之外的其他关联容器。

结果对比:

deque的性能是最好的,其次是unordered_set(神一般的存在)。

当元素个数比较多时,vector的性能是最差的。

forward_list要优于list。

除了unordered_set,其他关联容器性能都比非关联容器(除了vector)要差。

当元素个数比较多(大概大于2500)时,set的性能要高于map。multi系列的都要优于非multi系列(除了unordered_set)。比如multimap优于map;unordered_multimap优于unordered_map。

当元素个数比较少(大概小于256)时,有序关联容器的性能比无序(unordered)关联容器要高(除了unordered_set)。

中间插入

元素个数>15000

C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入
insert_mid_16384_highest

vector容器性能是最差的。再看下其他容器

C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入
insert_mid_16384

forward_list和list的性能是最好的。然后是deque和set。

set容器是所有关联容器中性能最好的。

map和multimap性能仅优于vector。

元素个数<4096

C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入
insert_mid_4096_highest

元素个数大于2000左右开始,vector的性能将比所有容器都要差。

元素个数<256

C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入
insert_mid_256_highest

vector的性能要优于其他容器。

当元素个数超过255时,deque的性能才超过vector。

结果对比:

当元素个数小于256时,vector的效率是最高的。但是随着元素个数增多,vector将变成性能最差的容器。

forward_list、list和deque在不同元素个数时表现的都很优异。

set容器是所有关联容器中性能最好的。

尾部插入

元素个数>15000

C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入
insert_end_16384_highest

vector性能是最好的,其次是deque。

map性能是最差的。

结论:

在尾部插入时,vector的性能是最好的。其他两个场景下,vector的性能都是最差的。但是在中间插入场景,容器元素个数小于256时,vector还是最优的。但是之后衰退严重。

deque在头部和尾部插入元素场景下性能优异。

list和forward_list在中间插入元素场景下性能优异。

在关联容器中,只有在头部插入场景下的unordered_set性能极其优异。

当元素个数较多时,set的性能要优于map。

文中图例可从如下地址获取: https://github.com/f304646673/stl_perf/tree/master/windows


以上所述就是小编给大家介绍的《C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——插入》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

五子连珠必胜法

五子连珠必胜法

新井华石 / 张书 / 人民体育出版社 / 1997-10 / 12.00元

《五子连珠必胜法》经日本国虹有社授权,译自日本连珠社已故理事长新井华石九段经典著作《连珠必胜法》一书。内容阐述和介绍五子连珠的基本着法和各种常用的布局定式。全书分两大编。连珠基本编介绍连珠棋的发展历史、连珠棋的规则和规定以及基本珠形。连珠必胜编分为六章分别阐述和介绍各种常用布局定式,包括二号连浦月、五号连花月、一号连云月、二号桂名月、三号桂岚月、二号间恒星六种布局定式。一起来看看 《五子连珠必胜法》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换