deque是一种双向开口的连续线性空间，可以在头尾两端分别做元素插入和删除操作。deque没有“容量”（capacity）的观念，是动态地以分段连续空间组合而成，随时可以增加一段新空间如何连接起来。
deque是由一段段的定量连续空间组成。一旦需要在deque的前端或者尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或者尾端。
deque采用一块所谓的map（不是stl的map容器）作为主控。这里的map是一块连续空间，其中每个元素都是一个指针，指向另一段较大的线性连续空间，这段空间称为缓冲区。缓冲区是deque存储空间的主体。sgi stl允许指定缓冲区的大小，默认值0表示使用512bytes缓冲区。
template <class T,class Alloc=alloc,size_t BufSiz=0> class deque{ public: typedef T value_type; typedef value_type* pointer; ... protected: typedef pointer* map_pointer; protected: map_pointer map; //指向map，map是连续空间，其内的每个元素都是一个指针，指向一块缓冲区 size_type map_size; //map可容纳多少指针 ... };
map是一个指向指针的指针，指向型别为T的一块空间
deque是分段的连续空间，维持其整体连续假象的任务，落在了迭代器身上。它应该具有以下结构：
1、指出缓冲区的位置。
2、判断是否处于缓冲区边缘，如果是，一旦前进或者后退必须能够跳跃到下一个或上一个缓冲区。
template <class T, class Ref, class Ptr, size_t BufSiz> struct __deque_iterator { // 基本型别的定义 typedef __deque_iterator<T, T&, T*, BufSiz> iterator; typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef T** map_pointer; typedef __deque_iterator self; // 缓冲区的大小 tatic size_t buffer_size() { ... } // 保持与容器的连接 T* cur; // 指向当前缓冲区的现行元素 T* first; // 指向当前缓冲区的头 T* last; // 指向当前缓冲区的尾 map_pointer node; // 指向管控重心map // ... };
下面是map对几个关键行为的操作步骤。
//用于跳转缓冲区 void set_node(map_pointer new_node) { node = new_node; first = *new_node; last = first + difference_type(buffer_size()); } // 迭代器之间的距离(相隔多少个元素) difference_type operator-(const self& x) const { return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur); } reference operator*() const { return *cur; } pointer operator->() const { return &(operator*()); } self& operator++() { ++cur; if (cur == last) { // 到达缓冲区尾端 set_node(node + 1); cur = first; } return *this; } self& operator++(int){ self tmp = *this; ++*this; return tmp; } self& operator--() { if (cur == first) { // 已到达缓冲区头端 set_node(node - 1); cur = last; } --cur; return *this; } self& operator--(int){ self tmp = *this; --*this; return tmp; } self& operator+=(difference_type n) {//支持ite+=n difference_type offset = n + (cur - first); if (offset >= 0 && offset < difference_type(buffer_size())) cur += n;//如果还在当前节点，直接加 else {//否则跳到下个节点 difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size()) : -difference_type((-offset - 1) / buffer_size()) - 1; set_node(node + node_offset); cur = first + (offset - node_offset * difference_type(buffer_size())); } return *this;//返回当前对象引用 } self operator+(difference_type n) const {//重载const重载+号。 self tmp = *this; return tmp += n; } self& operator-=(difference_type n) { return *this += -n; }//ite -=n通过+ -n实现。 self operator-(difference_type n) const {//重载- self tmp = *this; return tmp -= n; } //实现随机存储，迭代器调用operator* 和 operator+ reference operator[](difference_type n) const { return *(*this + n); }//重载ite[]操作，通过+实现 bool operator==(const self& x) const { return cur == x.cur; }//重载ite1 == ite2 bool operator!=(const self& x) const { return !(*this == x); }//重载ite1 != ite2 bool operator<(const self& x) const { return (node == x.node) ? (cur < x.cur) : (node < x.node); }
deque除了维护一个指向map的指针，也维护start和finish两个迭代器，分别指向第一缓冲区的第一个元素和最后一个缓冲区最后一个元素的下一个位置。此外它也需要记住map的大小，一旦map提供的节点不足，急需要重新配置一块更大的map
template<class T, class Alloc = alloc, size_t BufSiz = 0> class deque{ public : typedef T value_type ; typedef value_type* pointer ; typedef size_t size_type ; public : typedef __deque_iterator<T,T&,T*,BufSiz> iterator ; protected : //元素的指针的指针(pointer of pointer of T) typedef pointer* map_pointer ; protected: iterator start ; //表现第一节点 iterator finish ; //表现最后一个节点 map_pointer map ; //指向map,map是块连续空间，其每个元素都是个指针，指向一个节点(缓冲区) size_type map_size ; //map内有多少指针 ... } ;
关于deque的内存构造与管理的篇幅过于长，细节也较多，博客篇幅过小是在不宜细写。建议阅读原书籍章节理解
原文：https://www.cnblogs.com/LEEYATWAH/p/11788983.html