概述
vector是单向开口的连续空间，deque则是双向开口的连续空间，可以在头尾两端分别做元素的插入和删除。
deque与vector最大的差异在于：
- deque允许在常数时间内对起头端进行元素的插入或者移除。
- deque没有容量的概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。亦既是在vector中那样"因为旧空间不足而重新分配空间，然后复制元素，再释放旧空间"这样的事情在deque中不会发生，因此没有必要保留reserve等容量相关。
deque由2部分组成：
- 缓冲区：一段连续的内存空间。
- map：指向缓冲区的指针数组。
deque.png
template <typename T>
class Deque {
......
private:
T **_map; // 动态数组
iterator _begin;
iterator _end;
size_t _mapSize = 1; // map的数量
size_t _pageSize = 3; // 缓冲区的大小
}
迭代器
deque是分段的连续空间，维持其"整体连续"假象的任务，就落在了迭代器身上。为此迭代器必须能够做到：
- 能够指向缓冲区的元素
- 能够判断自己是否已处于缓冲区的边缘。当自己处于缓冲区的边缘时，能够跳跃至上一个缓冲区或者下一个缓冲区，需要知道自己在map中哪个位置。
所以，在其中应该要保留一个指向容器（其中有map）的指针，一个所处map为重的索引， 指向元素的指针。
class DequeIterator {
private:
Deque<T> *_containerPtr; // 保存对容器的连接，重点是能访问到map。
T *_cur; // 指向缓冲区的元素
size_t _mapIndex; // map数组的索引，向前跳跃或者向后跳跃
};
迭代器.png
DequeIterator &operator++();
_cur = isPageTail() ? _containerPtr->_map[++_mapIndex] : ++_cur; // 判断是否是缓冲区末尾
return *this;
DequeIterator &operator--()
_cur = isPageHead() ? _containerPtr->_map[--_mapIndex] + (getPageSize()-1) : --_cur; // 判断是否是缓冲区头部
return *this;
添加元素
void push_back(const T &value)
- 如果没有空间容纳新元素
- 申请新的map
- 拷贝原deque的缓冲区中的元素
- 构造元素
if (isLastPageTail()) // 是否是Deque缓冲区的最后一个位置
reallocateMapForTail();
dataAlloc::construct(_end._cur, value);
++_end;
void push_front(const T& value)
if (isFirstPageHead())
reallocateMapForHead();
--_begin;
dataAlloc::construct(_begin._cur, value);
删除元素
void Deque<T>::pop_back()
if (empty())
throw std::out_of_range("pop_back() on empty Deque");
--_end;
dataAlloc::destroy(_end._cur);
void pop_front()
if (empty())
throw std::out_of_range("pop_front() on empty Deque");
dataAlloc::destroy(_begin._cur);
++_begin;
