STL deque的实现

参考自 侯捷, STL源码剖析

• class deque definition
  deque采用一块所谓的map作为主控，这里的map是一块连续空间，其中每个元素都是一个指针，指向一段（较大的）连续线性空间，称为缓冲区，SGI STL允许我们指定缓冲区大小，默认值0表示将使用512bytes缓冲区。

template<class T, class Alloc=alloc, size_t BufSiz = 0>
class deqeue{
public:
	typedef T value_type;
	typedef value_type* pointer;
	...
protected:
	typedef pointer* map_poiner;
	map_pointer map;  // 指向map，map是块连续空间，其内额每个元素都是一个指针，指向一块缓冲区
	size_type map_size; // map可容纳多少指针
}

• deque结构图：
  
• deque的迭代器
  deque迭代器要能够判断自己是否已经处于其所在缓冲区的边缘，而且为了能够正确跳跃至上一个或下一个缓冲区，deque必须随时掌握管控中心(map)

template<class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator{
	T* cur;    // 此迭代器所指的缓冲区的现行(current)元素
	T* first;  // 此迭代器所指的缓冲区的头
	T* last;   // 此迭代器所指的缓冲区的尾（含备用空间）
	map_pointer map;  // 指向此迭代器对应的管控中心
};

• 迭代器结构图如下：