相关环境和说明在《C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(ubuntu g++)——插入》已给出。本文将分析各个容器中遍历和查找的性能。(转载请指明出于breaksoftware的csdn博客)

遍历

从前往后

元素个数>15000

traversal_begin_16384_highest
traversal_begin_16384_highest

        表现最差的是unordered_multiset。其在遍历到1000个左右的元素时发生较高的延时操作,然后又稳定下来。

        除了这个容器,再看下其他容器的表现。

traversal_begin_16384
traversal_begin_16384

        可以看出这些容器的遍历效率差距不大。最快的vector比倒数第二慢的unorderedset快50%左右。

        vector容器在元素个数大于8000左右开始,效率优于list。之前list是最优的。

元素个数<4096

traversal_begin_4096
traversal_begin_4096

        因为unordered_multiset效率还是很差,所以上图例没有将其列出。

        deque在最开始时,发了高耗时的操作。之后它的效率还是可以的。

元素个数<1024

traversal_begin_1024_highest
traversal_begin_1024_highest

        unordered_multiset在元素个数超过200左右时,效率将差于其他容器。

        deque在元素个数低于200左右时,效率低于所有容器。

结果对比:

        元素个数大于8000左右时,vector效率是最好的。

        元素个数小于8000左右时,list效率是最好的。

        元素个数大于200左右时,unordered_multiset效率是最差的。

        元素个数小于200左右时,deque效率是最差的。主要原因是开始时一次高耗时操作,但是之后每次操作耗时均不多(线的变化率)。

从后往前

        支持从后向前遍历的容器并不多,只有:vector、deque、list、set、map、multiset和multimap。

元素个数>15000

traversal_end_16384_highest
traversal_end_16384_highest

        vector效率最高,其次是deque和list。

结论:

        vector在各个方向的遍历效率均比较优秀。

        list在从前往后遍历时比deque优秀。

        deque在从后向前遍历时比list优秀。

        关联容器的遍历效率没有非关联容器高。

查找

         因为非关联容器的查找只能通过遍历,其效率和关联容器的查找没法比。所以我们只比较关联容器

元素个数>15000

find_16384_highest
find_16384_highest

        最优的是unordered_multiset,其次是unordered_map和unordered_set。

        最差的是set。

元素个数<1024

find_1024_highest
find_1024_highest

        元素个数小于600左右时,unordered_multimap是最差的。

        元素个数大于600左右时,set是最差的。

结果对比:

        unordered_multiset的效率一直是最好的。

        set在元素较多时效率是最差的,其他时候也很差。

结论:

        unordered系列容器比ordered系列容器效率高。

        ordered系列容器中,map系列比set系列对应的容器效率高。比如map比set优,multimap比multiset优。

        set效率最差。

        unordered_multiset最优。

        文中图例可从以下地址获取:stl_perf/linux at master · f304646673/stl_perf · GitHub

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐