C++ 浅析 STL 中的 list 容器

今天药忘吃喽~ 2022-08-04 10:42 119阅读 0赞

list - 擅长插入删除的链表  
链表对于数组来说就是相反的存在。  
数组本身是没有动态增长能力的（程序中也必须重新开辟内存来实现），  
而链表强悍的就是动态增长和删除的能力。  
但对于数组强悍的随机访问能力来说的话，链表却很弱。

list - 是一个**双向链表**的实现。  
为了提供双向遍历的能力，list要比一般的数据单元多出两个指向前后的指针。  
这也是没办法的，毕竟现在的PC内存结构就是一个大数组，链表要在不同的环境中实现自己的功能就需要花更多空间。  
list提供了**push\_back，push\_front，pop\_back，pop\_front**四个方法来方便操作list的两端数据的增加和删除，不过少了vector的at和\[\]运算符的随机访问数据的方法随机访问数据的方法。并不是不能实现，而是list的设计者并不想让list去做那些事情，因为他们会做得非常差劲。对于list来说，清除容器内所有的元素是一件苦力活，因为所有数据单元的内存都不连续，list只有一个一个遍历来删除。

相关博文

详见：[C++ stack queue vector 中 易混淆的常用方法 浅析][C_ stack queue vector _ _]

详址：http://blog.csdn.net/u013630349/article/details/46860117

Level 1 - 仅仅作为Map使用：采用静态数组  
Level 2 - 保存定长数据，使用时也是全部遍历：采用动态数组（长度一开始就固定的话静态数组也行）  
Level 3 - 保存不定长数组，需要动态增加的能力，侧重于寻找数据的速度：采用vector  
Level 3 - 保存不定长数组，需要动态增加的能力，侧重于增加删除数据的速度：采用list  
Level 4 - 对数据有复杂操作，即需要前后增删数据的能力，又要良好的数据访问速度：采用deque  
Level 5 - 对数据中间的增删操作比较多：采用list，建议在排序的基础上，批量进行增删可以对运行效率提供最大的保证  
Level 6 - 上述中找不到适合的：组合STL容器或者自己建立特殊的数据结构来实现

有黑必有白，世界万物都是成对出现的。

性能总结与使用建议

![0_13012806490ZTe.gif][]

[C_ stack queue vector _ _]: http://blog.csdn.net/u013630349/article/details/46860117
[0_13012806490ZTe.gif]: /images/20220731/0fad6c55deb249e7b0029e933ddbc492.png