专栏首页方亮C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(ubuntu g++)——插入

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

        操作系统是ubuntu 18.04.1 server amd64,gcc是 7.3.0。编译产出是64位测试程序。(转载请指明出于breaksoftware的csdn博客)

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

        文中将测试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

insert_begin_16384_highest

        往vector容器头部插入数据,所需要的时间会随着容器元素增多而变得很慢。

        除去vector,其他容器的表现是

insert_begin_16384

        表现最好的是forward_list、list、deque和unordedset。

        我们再将x轴变短

元素个数<1024

insert_begin_1024_highest

        vector在元素个数超过800左右时,性能开始“一骑绝尘”的差。

元素个数<256

insert_begin_256_highest

         对于这种小容器,unordered_map最差,其次是unordered_set,然后是multiset和set。

        vector容器只是比上述容器好点。

        最好的还是forward_list,其次是list、multimap、map和deque。

对比结果:

        性能持续最好的是forward_list、list和deque。

        unordered_set小容器时表现不是很突出,但是随着元素增多,性能还是可以的。

        map和unordered_map在小容器时表现还可以,但是随着元素增多,性能下降明显。

        vector在大容器时,表现很糟糕。

中间插入

元素个数>15000

insert_mid_16384_highest

        表现最差的还是vector,其次是unordered_map。

        除去vector,看看其他容器的表现

insert_mid_16384

        表现最好的是forward_list和list,然后是set、deque以及multiset。

元素个数<4096

insert_mid_4096_highest

        vector大概在元素个数超过1500左右时,开始“差”过所有的容器。在此之前,它大部分时候比unordered_map和set要好。

元素个数<256

insert_mid_256_highest

        set容器在元素个数超过250左右时,执行了高耗时操作。

        此时表现最好的是forward_list、deque。

对比结果:

        持续表现最好的是forward_list。

        小容器时,list表现不好。但是元素个数超过500左右时,list表现可以媲美forward_list。

        vector容器表现最差。

尾部插入

元素个数>15000

insert_end_16384_highest

        表现最好的是vector。

        表现最差的是unordered_mutlimap。map表现也不好。

元素个数<256

insert_end_256_highest

        小容器时,表现最好的是vector和forward_list。

对比结果:

        vector的表现最好。

结论:

        vector容器在头部、中间插入时性能随着元素个数增多,性能变的非常糟糕。但是在尾部插入场景下,性能是极好的。

        forward_list和deque的插入操作性能在各种场景下,都比较好。

        list容器在头部和中间插入时,效率很好。但是在尾部插入时,性能不太好。

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

            相关环境和说明在《C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(ubuntu g++)——插入》已给出。本文将分析从头部、中间和...

    方亮
  • Redis源码解析——双向链表

            相对于之前介绍的字典和SDS字符串库,Redis的双向链表库则是非常标准的、教科书般简单的库。但是作为Redis源码的一部分,我决定还是要讲一讲...

    方亮
  • VC开发Windows客户端软件之旅——前言

            从第一次拖着行李入京找活,至今已工作若干年了。这些年一直追逐自己的梦想,跑过三个城市,换了三份工作,认识了很多业内的朋友。和朋友们闲聊时,发现很...

    方亮
  • 响铃:好生意还是好故事,这或是快递最后100米的真相

    好消息是,由于快递人工成本的上升,社区安全等限制条件或快递员配送时间紧等原因,往往在最后的末端配送环节达不到“门到门”的服务标准,于是给了创业者机会。目前站在这...

    曾响铃
  • Java8StreamAPI实例

    filter内部使用的是lamda表达式,也是Java8的功能,o代表集合中每一个元素,o>5表示这个元素的值若大于5就返回true,就获取结果。collect...

    崔笑颜
  • 三分钟使用 Python 处理 Nginx 日志

    有什么 有 14 台机器(意味着我们有14份日志) 一台可以连到这 14 太机器的机器(有 Python 2.6) 要做什么 获取 14 台机器上某时间段内...

    临书
  • 【专知荟萃02】自然语言处理NLP知识资料大全集(入门/进阶/论文/Toolkit/数据/综述/专家等)(附pdf下载)

    【导读】主题荟萃知识是专知的核心功能之一,为用户提供AI领域系统性的知识学习服务。主题荟萃为用户提供全网关于该主题的精华(Awesome)知识资料收录整理,使得...

    WZEARW
  • Docker实践(七): EFK Stack搭建日志管理系统

    Logstash: 是一个灵活的数据传输和处理系统,Logstash的任务读取原始日志,并对其进行分析和过滤,然后将其转发给其他组件(比如 Elasticsea...

    loong576
  • STM32L1学习笔记04 晶振设置

    关于STM32的学习,初学者很容易被晶振这个东西给坑了。要在一个新平台上开发,先要把晶振搞定。

    twowinter
  • 如何用Python做词云?(基础篇视频教程)

    (由于微信公众号外部链接的限制,文中的部分链接可能无法正确打开。如有需要,请点击文末的“阅读原文”按钮,访问可以正常显示外链的版本。)

    王树义

扫码关注云+社区

领取腾讯云代金券