一、deque的一些特点
- 支持随机访问，即支持[ ]以及at()，但是性能没有vector好。
- 可以在内部进行插入和删除操作，但性能不及list。
- deque 两端 都能够快速插入和删除元素，而vector只能在尾端进行。
- deque的元素存取和迭代器操作会稍微慢一些，因为deque的内部结构会多一个间接过程。
- deque迭代器是特殊的智能指针，而不是一般指针，它需要在不同的区块之间跳转。
- deque可以包含更多的元素，其max_size可能更大，因为不止使用一块内存。
- deque不支持对容量和内存分配时机的控制。（？）
- 在除了首尾两端的其他地方插入和删除元素**，都将会导致指向deque元素的任何pointers、references、iterators失效**。但，deque的内存重分配优于vector，因为其内部结构显示不需要复制所有元素。
- deque的内存区块不再被使用时，会被释放，deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实际操作版本定义。
- deque 不提供容量操作：capacity()和reverse()，但是vector可以
二、deque实现框架
直接用侯捷老师的deque底层示意图说明其数据结构吧，
结合上述的特点我们就能明白deque的线性空间其实是一个假象，真实的底层是用一个map主管来管理每一小块连续内存的地址，是一种分段连续的存储空间， 因此迭代器需要在不同区块之间跳转，也就造成了随机访问和内部插入删除比不上vector和list。
ok， 开始deque的设计框架
1， 从图片可知基本信息
从上述分析我们知道了deque容器采用一种分段式存储空间，那么支持随机访问的deque就需要对迭代器进行处理，从图我们就知道的是：
1，首先我们要保证每一个小连续内存的容量（缓冲区容量）都是一样的；
2，需要两个迭代器，start和finish，分别指向第一个有效的map节点及其缓冲区，和最后一个有效的map节点及对应缓冲区，依旧是严格的STL原则左闭右开
3，最重要的一点，start和finish对应的缓冲区的空或满判断是不一样的，每一个缓冲区都有三个指针first、cur、last，开头缓冲区start满了是start.cur == start.first，空了是start.cur == start. last， 而finish缓冲区对应的就是我们下意识的状态， 满了就是finish.cur == finish.last
4，当然还有管理中心map
2，deque框架代码
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
