Assignment7.5

这周想给大家分享一下STL的Deque。（这是给同学们的拓展阅读）

STL的deque

1. 支持随机存取（相对于链表）。 常数复杂度取出 deque[i]， 而链表则是从表头开始遍历 linkList[i] 的复杂度是O(n)
2. 和vector 相比支持push_front, pop_front
3. STL的stack是deque的适配。 默认底层容器是deque

STL源码剖析 page 143 页 比较详细地接受了STL的deque实现。 简单地说， 是加了一个索引。 然后增长和收缩的时候操纵索引。 从而避免了像vector那样大量数据进行拷贝移动。 具体又是如何支持随机存取的呢？ 请到书里的章节中去阅读（2 hour）

在对deque有里基本的了解之后， 我们可以知道deque是比vector复杂的数据结构，虽然理论上存取都是常数，但是,因为deque的复杂性， 其常数相比deque较大。那么 为什么要用deque作为stack的默认容器呢？

这里对vector和deque做了一个简单的比较 指出了

A deque uses memory in a more operating system-friendly way, particularly on systems without virtual memory. For 
example, a 10-megabyte vector uses a single 10-megabyte block of memory, which is usually less efficient in practice 
than a 10-megabyte deque that can fit in a series of smaller blocks of memory. 

虚拟内存，和分页相关知识会在计原和操作系统课程中接触到。

这里你需要了解的是。 deque对连续存储空间的要求比较低。 因为vector支持的随机存取是依赖于改vector的存储空间连续。 而deque则自己管理。

最后TA自己在阅读完源码剖析的deque章节后， 写了一个功能简化版的deque https://github.com/ds-sww/codebase/pull/366/files 实现了随机存取和push_front & push_back 未实现pop相关操作。 能基本说明STLdeque的内部结构。 需者自取。

对于有兴趣深入了解的同学，我建议大家

0. 大致阅读源码剖析相关章节
1. 阅读TA的功能简单般代码
2. 再细读源码剖析
3. 阅读STL源码, /usr/include/c++/../..
4. 如有较多时间和余力，可以自己实现一遍(1 day)

Have fun & Good luck!~