deque 是双端队列，在其头部和尾部插入元素的代价很小。deque 的元素存储在一块一块的内存中，每一块内存是连续的，不同块的内存大小一样的但彼此没有关联，deque 中有一个指针数组 _M_map 。_M_map 中的每一个元素存储的是一块连续内存的首地址，查找 deque 中的元素首先通过 _M_map 定位到该元素所在的内存块(该内存块存储在 _M_map 的某个元素中)，然后根据它在该内存块中的位置检索到元素。
对于 deque 中两个分属不同内存块中的元素 a 和 b。如果 a 所在内存块的首地址存储在 _M_map[i] 中，b 所在内存块的首地址存储在 _M_map[j] 中，如果 i < j，则 deque 中 a 在 b 的前面，否则 a 在 deque 的后面。如果 a 和 b 同属一个内存块。则地址在前的元素处在前面。
stl_deque.h 中定义了一个内联函数 __deque_buf_size ，主要用来计算对于大小为 __size 的元素，deque 中 _M_map 元素指示的一个内存块能放进多少个这样的元素。前面已经说过通过 deque 中 _M_map 的某个元素可以索引到一块连续的内存。如果 deque 中存储的元素所占空间为 __size，那么一个内存块的大小应该为 __size * __deque_buf_size(__size)。如果 deque 中的元素大小小于 512 字节。则每一个内存块存放的元素个数为 512 / __size 。每一个内存块实际占有空间为 512 / __size * __size 。而如果 deque 中的元素大小不低于 512 ，则每一个内存块只存放一个元素，每一个内存块实际占用的空间大小为 __size 。
inline size_t __deque_buf_size(size_t __size) {
return __size < 512 ? size_t(512 / __size) : size_t(1);
}
####类模板 _Deque_iterator#### 结构体 _Deque_iterator 作为 deque 内部的迭代器，_Deque_iterator 内部定义了迭代器约定俗成应有的五种成员类型。
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Ptr pointer;
typedef _Ref reference;
其内部有四个公有的成员变量。 其中 _Map_pointer 是一个内部定义的成员类型。 typedef _Tp** _Map_pointer。
_M_node 指向 _M_map 中的某一个元素，通过 *_M_node 可以获得 _M_map 中的某个元素。迭代器指向的元素在以 *_M_node 为首地址的内存块中。更改 _M_node 的值能够使得迭代器索引不同内存块中的元素。 _M_first 指向在 *_M_node 为首地址的内存块中的起始地址(即 *_M_node)。 _M_last 作为以*_M_node 为首地址的内存块的结束地址。 _M_last 标记也不指向具体的元素。只是被用来作一个结束标记。 _M_cur 表示以 *_M_node 为首地址的内存块中迭代器索引元素的位置。
_Tp* _M_cur;
_Tp* _M_first;
_Tp* _M_last;
_Map_pointer _M_node;
构造函数中初始化列表中用 __x 来初始化当前的迭代器指向的元素位置 _M_cur，构造函数没有对 __x 的正确性进行判断，__x 指向的元素应该是要在以 *__y 为首地址的内存块中。用 __y 来初始化 _M_node ，用 *__y 初始化 _M_first。而对于每一个内存块，其中一共有 _S_buf_size 个元素， *__y + _S_buffer_size() 应为该内存块的结束标记，用 *__y + _S_buf_size() 来初始化 _M_last， *__y + _S_buffer_size() - 1 应该是该内存块中存储的最后一个元素。
_Deque_iterator(_Tp* __x, _Map_pointer __y)
: _M_cur(__x), _M_first(*__y),
_M_last(*__y + _S_buffer_size()), _M_node(__y) {}
_S_buffer_size() 用来计算一个以 _M_map 中某个元素为首地址的内存块中能存储多少个类型为 _Tp 的元素。函数直接调用全局函数 __deque_buf_size() 进行计算。
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
构造函数是 _Deque_iterator 的默认构造函数，该函数将四个成员变量表示的指针都初始化为 NULL 。
_Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
拷贝构造函数直接用形参 __x 的成员变量值来对当前类的成员变量进行赋值。
_Deque_iterator(const iterator& __x)
: _M_cur(__x._M_cur), _M_first(__x._M_first),
_M_last(__x._M_last), _M_node(__x._M_node) {}
operator *函数用于获取当前迭代器指向的元素，也即 _M_cur 指向的元素。
reference operator*() const { return *_M_cur; }
operator-> 用于返回 指向 operator * 中返回的元素的指针。
pointer operator->() const { return _M_cur; }
对于 operator- 根据其形参不同有两个不同的定义，当前函数的形参为一个 _Self 类型的变量，_Self 是在 _Deque_iterator 中定义的成员类型，是当前类的一个类型别名。 函数实现的功能是计算出两个 _Deque_iterator 的差值。即这两个迭代器所表示的范围之间一共有多少个元素，如果把 _Deque_iterator 看成是一个指针会好理解一点。如果是当前迭代器指向的元素在前，而 迭代器 __x 指向的元素在后，则返回的是一个负值，否则返回的是正值。 difference_type 是一个有符号长整型。
迭代器的 _M_node 指向的是 _M_map 中的某元素，通过比较当前迭代器的 _M_node 和给定迭代器 __x 的 _M_node 的差值，可以知道两个迭代器之间有多少个完整内存块的元素。举例说明，假设当前迭代器指向 _M_map[j] ，而 __x 的 _M_node 指向 _M_map[i] (设 i < j)，则以 _M_map[i + 1…j - 1] 为首地址的内存块中的元素都应该在这两个迭代器之间。
根据当前迭代器的 _M_node 和指定迭代器 __x 的 _M_node 的相对位置，可以分两种情况进行讨论。第一种，如果当前迭代器的 _M_node 指向的 _M_map 元素在 __x 的 _M_node 指向的 _M_map 元素之后，则当前迭代器的 _M_node 指向的 _M_map 元素的位置到 __x 的 _M_node 指向的 _M_map 元素的位置之间一共有 _M_node - __x.M_node - 1 个元素(不包括前后的两个边界)。即一共有 _M_node - x.M_node - 1 个内存块，每个内存块中有 _S_buffer_size() 个元素，然后查看当前迭代器的 _M_cur 值 和迭代器 __x 指示的 _M_cur 值来计算出两个迭代器之间一共有多少个元素。
如果当前迭代器 _M_node 指示的 _M_map 元素在 __x 的 _M_node 指示的 _M_map 元素之前时 _M_node - __x._M_node - 1 的值取反后为 __x 的 _M_node 指向的 _M_map 元素的位置到当前迭代器的 _M_node 指向的 _M_map 元素的位置之间的元素个数(这里包括了前后的边界) 。则用 (_M_node - __x._M_node - 1) * _S_buffer_size() 得到的值取反会比两个迭代器之间实际的元素个数要多。因此要减去当前迭代器 _M_cur 到 _M_first 之间的元素个数，同时减去 __x 中 _M_last 到 M_cur 的元素个数。然后整体取反就得到了函数中的表达式。对于当前迭代器的 _M_node 和 __x 指向 _M_map 中的同一个元素的情况，也可以应用第二种情况。
difference_type operator-(const _Self& __x) const {
return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}
operator++ 用来将当前迭代器的 _M_cur 向后移动一个位置，这里首先将 _M_cur 在当前列中向后移动一个位置，如果碰到结束标记，则表示移动之前迭代器所指示的元素的下一个元素应该在下一列，并且是下一列的第一个元素。因此将 _M_node 指向当前列的下一个列(调用 _M_set_node 函数进行设置)，然后更改 _M_first, _M_last, _M_cur 的值。最后返回向后移动一个位置之后的迭代器。
_Self& operator++() {
++_M_cur;
if (_M_cur == _M_last) {
_M_set_node(_M_node + 1);
_M_cur = _M_first;
}
return *this;
}
operator++ 中定义的自增运算是一个后置的自增运算。也是将当前迭代器的 _M_cur 向后移动一个位置，只是返回值是移动之前的迭代器。
_Self operator++(int) {
_Self __tmp = *this;
++*this;
return __tmp;
}
operator– 是将当前迭代器的 _M_cur 向前移动一个位置，实现的思想和 operator++ 比较相似，一个细微的差别是 operator++ 是先移动再检测是否碰到结束标记，而 operator– 是先检测当前是否是第一个元素，如果不是直接移动，否则要切换到新的列，再进行移动，如果是切换到新的内存块迭代器应该处在最后一个元素所在的位置，因为 deque 中向前插入元素时，在同一个内存块中地址是从高地址往低地址生长的，如果向后插入元素，同一个内存块中地址是从低地址向高地址生长的。函数最后的返回值也是移动之后的迭代器。
_Self& operator--() {
if (_M_cur == _M_first) {
_M_set_node(_M_node - 1);
_M_cur = _M_last;
}
--_M_cur;
return *this;
}
operator+= 将当前迭代器所指示的位置向后移动 __n 个位置 (这里如果 __n 是一个负数，则表示向前移动 -__n 个位置)。函数的第一步首先是判断移动之后迭代器是否还处在当前内存块中。如果是则直接修改 _M_cur 的值使得它指向当前元素之后的第 __n 个元素 (如果 __n 为负数，则指向当前元素之前的 -__n 个元素) 。
如果移动之后迭代器需要切换到另外的内存块，则需要首先修改 _M_node 的值。使得当前迭代器切换到指定的内存块。 函数开始计算了一个 __offset 值，使得将迭代器从 _M_cur 指示的位置移动 __n 个位置和从 _M_first 指示的位置移动这个 __offset 个位置是等价的。这一点从 else 语句块中就可以看出。
else 语句块中如果 offset < 0 则 __node_offset = -difference_type((-__offset - 1) / _S_buffer_size()) - 1 。这样是因为如果 offset < 0 ，且 -__offset % _S_buffer_size() 的余数不为 0 那么他应该在移动 -__offset / _S_buffer_size() 的基础上再向前移动一位置，当 __offset % _S_buffer_size() == 0 时，只需移动 __offset / _S_buffer_size() 个位置。根据 __node_offset 调用 _M_set_node 设置 _M_node 的值，同时在 _M_set_node 中会同时对 _M_first 和 _M_last 的值进行设置。
然后设置 _M_cur 的值，这里也要分两种情况进行讨论，当 __n > 0 时迭代器向后移动，此时在同一个内存块中迭代器是从低地址向高地址移动(即 _M_first 向 _M_last 的方向)。此时_M_cur = _M_first + __offset - __node_offset * difference_type(_S_buffer_size()) 。当 __n < 0 时迭代器向前进行移动，此时在同一个内存块中迭代器从高地址向低地址移动(即 _M_last 向 _M_first 的方向)。当 __offset == __node_offset * difference_type(_S_buffer_size()) 时 _M_cur 应刚好处在 _M_first 的位置，但如果__offset > __node_offset * difference_type(_S_buffer_size()) 时，_M_cur 应从 _M_first 的位置回退 __offset - __node_offset * difference_type(_S_buffer_size()) 。
_Self& operator+=(difference_type __n)
{
difference_type __offset = __n + (_M_cur - _M_first);
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
_M_cur += __n;
else {
difference_type __node_offset =
__offset > 0 ? __offset / difference_type(_S_buffer_size())
: -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
_M_set_node(_M_node + __node_offset);
_M_cur = _M_first +
(__offset - __node_offset * difference_type(_S_buffer_size()));
}
return *this;
}
operator+ 在不更改当前迭代器的情况下返回值当前迭代器移动 __n 个位置的结果。其中 __n 值可正可负。调用 operator+= 函数进行实现。
_Self operator+(difference_type __n) const
{
_Self __tmp = *this;
return __tmp += __n;
}
operator-= 将当前迭代器往前移动 __n 个位置。通过将形参 __n 取负值，然后将负值作为实参来调用 operator+=
_Self& operator-=(difference_type __n) { return *this += -__n; }
operator- 在不更改当前迭代器的情况下返回当前迭代器向前移动 __n 个位置的结果。__n 也可以为负数。
_Self operator-(difference_type __n) const {
_Self __tmp = *this;
return __tmp -= __n;
}
operator[] 是用来索引当前迭代器移动 __n 个位置之后指向的元素，函数内部直接调用 operator+ ,对 operator+ 的返回的迭代器进行解引用获取到该迭代器所指向的元素。所以这里 __n 是可以为负数的，这和我们一般的理解上有点不同。
reference operator[](difference_type __n) const { return *(*this + __n); }
同时在 _Deque_iterator 中还定义了一些关系运算符。
operator== 函数用来判断两个迭代器是否相同，直接判断他们的 _M_cur 是否指向同一个元素即可，因为对于一个合法的迭代器其 _M_cur 肯定是指向以其 *_M_node 为首地址的内存块中的一个位置，既然两个迭代器的 _M_cur 值相同那么说明他们都在同一个内存块，如果他们都在同一个内存块，且迭代器的类型相同，并且由迭代器类型相同可以知道他们的 _S_buffer_size 应该相同。则他们的 _M_first 和 _M_last 肯定也相同。所以直接比较他们的 _M_cur 可以判断两个迭代器是否相同。
bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
bool operator!=(const _Self& __x) const { return !(*this == __x); }
operator< 首先检测两个迭代器指向的元素是否在同一个内存块，如果在同一个内存块，那么判断他们的 _M_cur 的大小。如果不在同一个内存块，则比对两个内存块的首地址在 _M_map 中的位置(内存块的首地址存储在 _M_map 的某个元素中) 如果当前迭代器指向的元素所在的内存块中的首地址在 _M_map 中的位置比 __x 指向元素所在的内存块的首地址在 _M_map 中的位置靠前，则返回 true ，否则返回 false 。deque 中以 _M_map 的每个元素为首地址的地址空间是连续的，但以不同 _M_map 元素为首地址的地址空间之间是没有关联的，内存区域是随机分配的，以 _M_map 中靠前的元素为首地址的内存空间可能比以 _M_map 中靠后的元素为首地址的内存空间的实际地址还要大。
bool operator<(const _Self& __x) const {
return (_M_node == __x._M_node) ?
(_M_cur < __x._M_cur) : (_M_node < __x._M_node);
}
M_set_node 是为当前迭代器设定一个新的内存块。并在设置新的内存块之后，重新设定 _M_first, _M_last 的值，函数中没有设定 _M_cur 的值，一般 _M_set_node 不会单独使用，在调用它的函数中会对 _M_cur 值进行设定。
void _M_set_node(_Map_pointer __new_node) {
_M_node = __new_node;
_M_first = *__new_node;
_M_last = _M_first + difference_type(_S_buffer_size());
}
STL 的 deque 分析（一）</br> STL 的 deque 分析（二）</br> STL 的 deque 分析（三）</br> STL 的 deque 分析（四）</br> STL 的 deque 分析（五）</br> STL 的 deque 分析（六）</br>