• 《vector和list 的对比》


    vector的优点:

    1.下标随机访问:

            vector这个类中重载了[]这个符号,可以让其去下标访问,但是他自己本生是一个重载函数的调用,所以会存在一定的性能问题。

    2.尾插尾删效率高:

            因为vector本质上就是一块连续的空间,所以再这块空间中,尾插尾删除数据是非常高的,直接使用下标访问就行,删除直接让其的size的大小减一。

    3.cpu高速缓存命中率高:

            因为内存空间是连续的,当cpu告诉缓存加载数据的时候,是加载一部分的空间,不仅仅是你需要的一块数据的空间,所以你访问时,你加加的时候,不需要重新加载一块新的空间,这也就节省了很多时间和提升了程序运行的效率。

    vector的缺点:

    1.头插头删效率低

            头插头删效率很低,因为你需要挪动后面一整块数据,时间复杂度为O(N),这是一件非常恼火的事情。

    2.扩容有消耗,还存在一定的空间浪费

            扩容的时候,会将原本的空间丢弃,然后开辟出一块新的空间,这样就会造成计算机额外的消耗,且开辟的空间大小无论是原本的两倍,一点五倍或者其他,都会存在一定的空间浪费,如果你开始数据小的,浪费的并不是十分明显,如果当数据量达到一定的时候,你就会发现,你开辟两倍的空间,是非常多余的。

    list的优点:

    1.按需申请释放,无需扩容。

            因为list的底层就是一个带头的双向链表,所以当你需要插入节点的时候,你只需要申请一个节点,然后将这个节点插入即可,是没有空间浪费的。

    2.任意位置插入数据

            从底层我们也知道,list就是一个带头双向链表,既然是个链表,我们就可以随意的插入数据,空间复杂度为O(1)。且不需要挪动数据。

    list的缺点:

    1.不支持下标随机访问

            你如果想要寻找其中的数据或者是找到某个特殊的节点,你只能使用迭代器一个个去遍历,这也是一件十分恼火的事情。

    2.cpu高速缓存命中率低

            因为list本生就是一个带头双向链表,不存在连续空间存储的问题,所以cpu告诉缓存率低。这也是一件非常恼火的事情。

    【二】迭代器失效的问题

            迭代器失效这个问题在我们写代码的时候需要时刻注意的,因为迭代器失效之后轻则代码失效,重则,出现野指针问题,导致代码直接崩溃。

           vector中只有删除和插入会出现迭代器失效的问题,因为插入会扩容,扩容会展现一块新的地址空间,而你的迭代器还是指向原本的那块空间,这样就出现了越界的问题,而删除的时候,你将原本的数据删除了,但是你的迭代器还是指向那块空间,得不到更新,这样的话就会使你的程序产生错误。

            list中仅仅会有一个erase会出现迭代器失效的问题,因为它是一个带头双向链表,不存在扩容的问题。而erase掉之后,你的迭代器指向的还是原本的那块空间,此时那块空间已经被释放了,也就是不存在了,会出现野指针的问题。

    string其实也有迭代器失效问题,insert/erase失效和vector类似

            但是一般情况下,我们是不关注string的失效,因为string/erase常用函数都是下标支持的,迭代器支持的函数调用时非常少。

            以上就是这期的全部内容了,如果哪里阐明的有问题的话,还请一部于评论区进行斧正,如果没错的话还请一件三连。毕竟码字不易。

  • 相关阅读:
    【数据结构】双向循环链表
    【嵌入式 – GD32开发实战指南(ARM版本)】第2部分 外设篇 - 第3章 温度传感器DS18B20
    python画box图并标记
    iText生成PDF文件
    【教程8】疯壳·ARM功能手机-GPIO实验教程
    计算机毕业设计ssm+vue+elementUI基于html的戒烟网站
    Java多线程 深入理解volatile关键字 volatile的使用和原理分析
    只需两步折叠GoLand的控制台中多余的信息,控制台显示无效内容太多(GOROOT、GOPATH)
    jupyter使用教程及python语法基础
    【Spring事务】事务和事务传播机制
  • 原文地址:https://blog.csdn.net/wuqin668/article/details/128142470