首页 > 代码库 > 《STL源码剖析》---stl_deque.h阅读笔记(1)
《STL源码剖析》---stl_deque.h阅读笔记(1)
双端队列deque是容器的一种。它比vector更强大，vector只可以在尾端插入元素，deque不只是可以再尾端插入，也可以在队列头插入。下面借助《STL源代码剖析》的图片讲解。
1、deque的内存结构
vector是开辟一段连续的内存，deque可以在前端插入元素，如果像vector开辟一段连续的内存，向前面插入元素不易维护。例如如果只是开辟一段连续内存，那么前端到开辟内存的起始位置要空多少个位置？当这段内存满了时，拷贝到更大内存时，前端空留多少位置？显然难以维护。deque在STL中是维护多个连续内存的，多个连续的内存不一定连续，一段连续的内存叫做缓冲区。STL用一个叫“中控器”的结构map来维护，如下图：
图（1）
map是一个指针的指针，它执向一段连续内存，这段连续内存的内容也是指针，指向缓冲区的起始位置。当map满了的话，可以扩大map到更大的地方。
2、deque的迭代器
deque在内存结构上面讲过了，那么deque的迭代器应该是什么样子的呢？
首先，它应该知道自己在哪个缓冲区。其次，自己在缓冲区哪个位置，在首还是在尾。如果移动出这段缓冲区，那么应该移动到相邻的缓冲区，所以迭代器还应该知道自己所在缓冲区在中控器所处的位置。
综上所述，大概可以得出迭代器的样子，如下图：
图（2）
迭代器有4个元素，cur指向当前所指的deque结点，first指向迭代器所指结点所在缓冲区的起始位置，last指向迭代器所指结点所在缓冲区的结尾位置，node指向中控器的某个位置，这个位置指向迭代器所指结点所在的缓冲区。
3、deque的操作
deque的结构中有两个重要的迭代器，一个start指向deque的头，一个finish指向deque尾的下一个位置。如下图：
图（3）
当向deque插入/删除（在头或者在尾）元素时，如果所操作结点在缓冲区的头或者尾，都要考虑开辟/释放缓冲区的问题。
例如，向图（2）deque末尾插入4个元素0、1、2、3。当插入最后一个元素时，finish迭代器就要移动下一个缓冲区。如下图：
图（4）
当向图（4）deque的头插入元素99时，也会开辟新的缓冲区。如下图：
图（5）
当在首或者尾删除元素时，可能会涉及缓冲区的释放，不难想象。
当在deque中间删除元素时，就会涉及其他元素的移动。deque首尾都可以移动，它会判断怎么可以少移动元素，如果删除位置距离头更近，它会把前面的元素向后移；反之，把后面元素向前移。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。