C++的STL模板库中提供了3种容器类：vector,list,deque
对于这三种容器，在觉得好用的同时，经常会让我们困惑应该选择哪一种来实现我们的逻辑。
在少量数据操作的程序中随便哪一种用起来感觉差别并不是很大，
但是当数据达到一定数量后，会明显感觉性能上有很大差异。
本文就试图从介绍，以及性能比较两个方面来讨论这个问题。
- vector - 会自动增长的数组
- list - 擅长插入删除的链表
- deque - 拥有vector和list两者优点的双端队列
- 性能竞技场
- 性能总结与使用建议
- 测试程序清单
vector - 会自动增长的数组vector又称为向量数组，他是为了解决程序中定义的数组是
不能动态改变大小这个缺点而出现的。
一般程序实现是在类创建的时候同时创建一个定长数组，
随着数据不断被写入，一旦数组被填满，则重新开辟一块更大的内存区，
把原有的数据复制到新的内存区，抛弃原有的内存，如此反复。
由于程序自动管理数组的增长，对于我们程序员来说确实轻松了不少，
只管把数据往里面插就行了，当然把物理内存和虚拟内存插爆掉了
就是操作系统来找你麻烦了:-)
vector由于数组的增长只能向前，所以也只提供了后端插入和后端删除，
也就是push_back和pop_back。当然在前端和中间要操作数据也是可以的，
用insert和erase，但是前端和中间对数据进行操作必然会引起数据块的移动，
这对性能影响是非常大的。
对于所有数组来说，最大的优势就是随机访问的能力。
在vector中，提供了at和[]运算符这两个方法来进行随机访问。
由于每个数据大小相同，并且无间隔地排列在内存中，
所以要对某一个数据操作，只需要用一个表达式就能直接计算出地址：
address = base + index * datasize
同样，对vector进行内存开辟，初始化，清除都是不需要花大力气的，
从头到尾都只有一块内存。
list - 擅长插入删除的链表有黑必有白，世界万物都是成对出现的。
链表对于数组来说就是相反的存在。
数组本身是没有动态增长能力的（程序中也必须重新开辟内存来实现），
而链表强悍的就是动态增长和删除的能力。
但对于数组强悍的随机访问能力来说的话，链表却很弱。
list是一个双向链表的实现。
为了提供双向遍历的能力，list要比一般的数据单元多出两个指向前后的指针。
这也是没办法的，毕竟现在的PC内存结构就是一个大数组，
链表要在不同的环境中实现自己的功能就需要花更多空间。
list提供了push_back，push_front，pop_back，pop_front四个方法
来方便操作list的两端数据的增加和删除，不过少了vector的at和[]运算符的
随机访问数据的方法。并不是不能实现，而是list的设计者
并不想让list去做那些事情，因为他们会做得非常差劲。
对于list来说，清除容器内所有的元素是一件苦力活，
因为所有数据单元的内存都不连续，list只有一个一个遍历来删除。
deque - 拥有vector和list两者优点的双端队列黑与白，处于这两个极端之间的就是令人愉悦的彩色了。
deque作为vector和list的结合体，确实有着不凡的实力。
STL的deque的实现没有怎么去看过，不过根据我自己的猜测，
应该是把数组分段化，在分段的数组上添加指针来把所有段连在一起，
最终成为一个大的数组。
deque和list一样，提供了push_back，push_front，
pop_back，pop_front四个方法。可以想象，如果要对deque的两端进行操作，
也就是要对第一段和最后一段的定长数组进行重新分配内存区，
由于分过段的数组很小，重新分配的开销也就不会很大。
deque也和vector一样，提供了at和[]运算符的方法。
要计算出某个数据的地址的话，虽然要比vector麻烦一点，
但效率要比list高多了。
首先和list一样进行遍历，每次遍历的时候累积每段数组的大小，
当遍历到某个段，而且baseN <= index < baseN + baseN_length的时候，
通过address = baseN + baseN_index就能计算出地址
由于分过段的后链表的长度也不是很长，所以遍历对于
整体性能的影响就微乎其微了。
看起来deque很无敌吧，不过deque和希腊神话的阿吉里斯一样，
再怎么强大也是有自己的弱点的，之后的测试数据中就能看到了。
P.S.请搜索「阿吉里斯的脚后跟」来获取详细内容
性能竞技场为了能更好地进行比较，我们让静态数组（程序中写死的）和
动态数组（程序中new出来的）也参加了部分竞技。
竞技项目：
- 初始化：对于静态和动态数组，逐一赋值，对于容器，push_back插入
- 前向遍历：从0到n-1，每个数据自加1
- 后向遍历：从n-1到0，每个数据自减1
- 随机访问：在0到n-1中，随机抽取一定数量的数据进行读取
- 后端插入：用push_back在后端插入一定数量的数据
- 后端移除：用pop_back在后端移除一定数量的数据
- 前端插入：用push_front在前端插入一定数量的数据
- 前端移除：用pop_front在前端移除一定数量的数据
- 中间插入：用insert在中间插入一定数量的数据
- 中间移除：用erase在中间移除一定数量的数据
- 反初始化：对于静态和动态数组，ZeroMemory删除所有数据，对于容器，调用clear方法
规则：
- vector，list，deque都调用默认的构造函数来创建
- 数组和容器的数据项都是1,000,000个
- 前端和后端插入的数据项是10,000个
- 前端和后端删除的数据项是10,000个
- 随机访问的数据项是10,000个
- 数据类型采用int型
- 计时采用RDTSC高精度计时器来计时
- 随机访问的数据的位置序列在测试前随机生成，所有数组和容器都采用这个序列
- 测试采用Debug版(Release版会对代码进行优化，可能会对测试产生一定的影响)
- 测试3次，取平均值
测试机配置：
Intel(R) Core(TM)2 CPU T7400 2.16GHz 2.16GHz
2.00GB内存
测试结果：（单位 秒）
| 测试项目 | 静态数组 | 动态数组 | vector | list | deque | 备注 | | 初始化 | 0.00551 | 0.00461 | 0.207 | 1.30 | 0.352 | list每个数据项都有附加数据，速度稍慢了一些 | | 前向遍历 | 0.00381 | 0.00549 | 0.0796 | 0.0756 | 0.0713 | | | 后向遍历 | 0.00422 | 0.00478 | 0.885 | 0.879 | 0.690 | | | 随机访问 | 0.000334 | 0.000342 | 0.00119 | 148 | 0.0115 | list把时间都耗在了找寻相应数据上 | | 后端插入 | N/A | N/A | 0.00192 | 0.0128 | 0.00260 | | | 后端移除 | N/A | N/A | 0.00131 | 0.0293 | 0.00194 | | | 前端插入 | N/A | N/A | 10.2 | 0.0128 | 0.00547 | vector对前端操作很苦手啊 | | 前端移除 | N/A | N/A | 10.3 | 0.0297 | 0.00135 | 同上 | | 中间插入 | N/A | N/A | 195 | 187 | 764 | 看似万能的deque的最大弱点，因为复杂的结构导致中间数据操作带来的复杂性大大增加，体现在操作时间是其他两个的几倍 | | 中间移除 | N/A | N/A | 195 | 209 | 753 | 同上 | | 反初始化 | 0.00139 | 0.00290 | 0.0000106 | 0.693 | 0.305 | vector貌似是直接抛弃内存的，其他两个就没那么简单了 |
性能总结与使用建议| 测试项目 | 静态数组 | 动态数组 | vector | list | deque | | 初始化 | ★★★★★ | ★★★★★ | ★★★★☆ | ★★★☆☆ | ★★★★☆ | | 前向遍历 | ★★★★★ | ★★★★★ | ★★★★☆ | ★★★★☆ | ★★★★☆ | | 后向遍历 | ★★★★★ | ★★★★★ | ★★★★☆ | ★★★★☆ | ★★★★☆ | | 随机访问 | ★★★★★ | ★★★★★ | ★★★★☆ | ★☆☆☆☆ | ★★★☆☆ | | 后端插入 | N/A | N/A | ★★★★★ | ★★★★☆ | ★★★★★ | | 后端移除 | N/A | N/A | ★★★★★ | ★★★★☆ | ★★★★★ | | 前端插入 | N/A | N/A | ★★☆☆☆ | ★★★★☆ | ★★★★★ | | 前端移除 | N/A | N/A | ★★☆☆☆ | ★★★★☆ | ★★★★★ | | 中间插入 | N/A | N/A | ★★☆☆☆ | ★★☆☆☆ | ★☆☆☆☆ | | 中间移除 | N/A | N/A | ★★☆☆☆ | ★★☆☆☆ | ★☆☆☆☆ | | 反初始化 | ★★★★★ | ★★★★★ | ★★★★★ | ★★★★☆ | ★★★★☆ |
一些使用上的建议：
Level 1 - 仅仅作为Map使用：采用静态数组
Level 2 - 保存定长数据，使用时也是全部遍历：采用动态数组（长度一开始就固定的话静态数组也行）
Level 3 - 保存不定长数组，需要动态增加的能力，侧重于寻找数据的速度：采用vector
Level 3 - 保存不定长数组，需要动态增加的能力，侧重于增加删除数据的速度：采用list
Level 4 - 对数据有复杂操作，即需要前后增删数据的能力，又要良好的数据访问速度：采用deque
Level 5 - 对数据中间的增删操作比较多：采用list，建议在排序的基础上，批量进行增删可以对运行效率提供最大的保证
Level 6 - 上述中找不到适合的：组合STL容器或者自己建立特殊的数据结构来实现
测试程序清单>>>main.cpp<<<
|