- deque
deque和vector的最大差异，一在于deque允许于常数时间对头端进行插入和删除操作，二在于deque没有所谓容量（capacity）观念，换句话说，像vector那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放空间”这样的事情在deque是不会发生的。除非必要，我们尽可能的使用vector而非deque，对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，将vector排序后，再复制回deque。
前面已经讲过，deque是由一段一段的定量连续空间构成，一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头部或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口，避开了“重新配置，复制，释放”的轮回，代价是更复杂的迭代器架构。
deque的迭代器:
deque的迭代器，首先必须能够指出分段连续空间（缓冲区）在哪里，其次它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或者后退时就必须跳跃至下一个或上一个缓冲区，为了能进行跳跃，deque必须随时掌握管控中心。
template <typename T, typename Ref, typename Ptr, size_t BufSiz>
struct __deque_iterator{//没有继承std::iterator
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
static size_t buffer_size(){return __deque_buf_size(BufSiz, sizeof(T));}
//未继承std::iterator,所以必须写5个必要的迭代器相应类型
typedef random_access_iterator_tag iterator_category;//(1)
typedef T value_type;//(2)
typedef Ptr pointer;//(3)
typedef Ref reference;//(4)
typedef size_t size_type;
typedef ptrdiff_t difference_type;//(5)
typedef T** map_pointer;
typedef __deque_iterator self;
//保持与容器的联结
T* cur;//此迭代器所指之缓冲区的现行元素
T* first;//此迭代器所指之缓冲区的头
T* last;//此迭代器所指之缓冲区的尾
map_pointer node;//指向管控中心
}其中用来决定缓冲区大小的函数buffer_size()，调用__deque_buf_size()。下面是deque迭代器的几个关键行为，由于迭代器内对各种指针运算都进行了重载操作，所以各种指针运算如加，减，前进，后退都不能直观的看。其中关键的就是：一旦行进时遇到缓冲区边缘，要特别当心，视前进或后退而定，可能需要调用set_node()跳一个缓冲区：
void set_node(map_pointer new_node){
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
reference operator*() const {return *cur;}
pointer operator->() const {return &(operator*());}
difference_type operator-(const self& x) const{//计算两个迭代器的距离
return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur);
}
self& operator++(){
++cur;// 切换到下一个元素
if(cur == last){//如果已达到缓冲区的尾端
set_node(node + 1);//切换到下一缓冲区
cur = first;
}
return *this;
}
self& operator+=(difference_type 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;
}deque的数据结构：
deque除了维护一个指向map（这里的map不是stl中的map，而是一段存放缓冲区指针的连续空间）,也维护start，finish两个迭代器，分别指向第一个缓冲区的第一个元素和最后缓冲区的最后一个元素（的下一个位置）。此外，它当然还必须要记住目前map的大小，因为map所提供的结点一旦不足，就必须重新配置一块更大的map
template <typename T, typename Alloc = alloc, size_t BufSize = 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:
//元素的指针的指针，指向map
typedef pointer* map_pointer;
protected:
iterator start; //表示第一个节点
iterator finish;//表示最后个节点
map_pointer map; //指向map，map是块连续空间，其中每个元素都是指针，指向一个缓冲区
size_type map_size;//map内有多少指针
...
}
reference operator[](size_type n){//deque提供这种操作
return start[difference_type(n)]; //调用__deque_iterator<>::operator[]
}Deque提供的操作：
void push_back(const T& data);
void pop_back()
void push_front(const T& data)
void pop_front()
iterator erase(iterator pos)//清除给定位置的元素
iterator erase(iterator first, iterator last)//清除给定区间[first， last)位置的元素
iterator insert(iterator pos, const T& data)//在给定的位置插入元素data
void clear()//清除整个deque（下面是clear的源码）
clear函数是用来清除整个deque，请注意，deque的最初状态（没有任何元素时）保有一个缓冲区，因此，clear函数完成之后要回到初始状态，也一样要保留缓冲区：
template <typename T, typename Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::clear(){
//以下针对头尾以外的每一个缓冲区(他们一定是饱满的)
for(map_pointer node = struct.node + 1; node < finish.node; ++node){
//将缓冲区内的所有元素析构
destory(*node, *node + buffer_size());
//释放缓冲区内存
data_allocator::deallocate(*node, buffer_size());
}
if(start.node != finish.node){//至少有头尾两个缓冲区
destroy(start.cur, start.last);//将头缓冲区的目前所有元素析构
destroy(finish.cur, finish.last);//将尾缓冲区的目前所有元素析构
//以下释放尾缓冲区。注意，头缓冲区保留
data_allocator::deallocate(finish.first, buffer_size());
}else{// 只有一个缓冲区,这里不在释放 缓冲区
destroy(finish.cur, finish.cur);
}
finish = start;//调整状态
}- stack
stack和queue都是以某种既有容器作为底部结构，将其接口改变。往往把stack和queue归为适配器而不把他们归为容器。
queue的定义和stack的定义非常类似，这里不在进行复写，需要注意的是queue和stack都没有迭代器，不支持遍历操作。默认情况下stack使用deque作为底层容器，当然也是可以指定其他的容器作为底层容器的。
例如：stack<int, list<int>> istack;这条语句就可以创建以list作为底层容器的stack。
template <typename T, typename Sequence = deque<T>>
class stack{
//以下的__STL_NULL_TMPL_ARGS会开展为<>
friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;//底层容器
public:
//以下完全利用Sequence c的操作，完成stack的操作
bool empty() const {return c.empty();}
size_type size() const {return c.size();}
reference top() {return c.back();}
const_reference top() const {return c.back();}
void push(const value_type& x) {return c.push_back(x);}
void pop() {c.pop_back();}
};
template <typename T, typename Sequence>
bool operator==(const stack<T, Sequence>&x, const stack<T, Sequence>&y){
return x.c == y.c;
}
template <typename T, typename Sequence>
bool operator<(const stack<T, Sequence>&x, const stack<T, Sequence>&y){
return x.c < y.c;
}- queue
queue的定义和stack的定义非常类似，这里不在进行复写，需要注意的是queue和stack都没有迭代器，不支持遍历操作。