C++ 浅析 STL 中的 list 容器-蒲公英云

C++ 浅析 STL 中的 list 容器

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

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

相关博文

详见：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容器或者自己建立特殊的数据结构来实现

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

性能总结与使用建议