deque
deque容器为一个给定类型的元素进行线性处理，像向量一样，它能够快速地随机访问任一个元素，并且能够高效地插入和删除容器的尾部元素。但它又与vector不同，deque支持高效插入和删除容器的头部元素，因此也叫做双端队列。
deque的中控器: deque是由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器结构。
deque采用一块所谓的map（不是STL的map容器）作为主控。
map是一小块连续空间，其中每个元素(此处称为一个节点，node)都是指针，指向另一段(较大的)连续线性空间，称为缓冲区。
缓冲区才是deque的储存空间主体。
template<class T, class Alloc = alloc, size_t BufSiz = 0> class deque{ public : typedef T value_type ; typedef value_type* pointer ; ... protected : //元素的指针的指针(pointer of pointer of T) // 其实就是T**，一个二级指针，维护一个二维数组 typedef pointer* map_pointer ; protected : map_pointer map ; //指向map,map是块连续空间，其内的每个元素 //都是一个指针(称为节点)，指向一块缓冲区 size_type map_size ;//map内可容纳多少指针 ... };
map其实是一个T**，也就是说它是一个指针，所指之物也是一个指针，指向型别为T的一块空间。
方法 说明
deque 构造函数
push_back 在当前的最后一个元素之后 ，在 deque 容器的末尾添加一个新元素
push_front 在 deque 容器的开始位置插入一个新的元素，位于当前的第一个元素之前
pop_back 删除 deque 容器中的最后一个元素，有效地将容器大小减少一个
pop_front 删除 deque 容器中的第一个元素，有效地减小其大小
emplace_front 在 deque 的开头插入一个新的元素，就在其当前的第一个元素之前
emplace_back 在 deque 的末尾插入一个新的元素，紧跟在当前的最后一个元素之后
测试代码
#include "stdafx.h" #include<iostream> #include<deque> using namespace std; int main() { deque<int> d; d.push_back( 11 );//在 deque 容器的末尾添加一个新元素 d.push_back(20); d.push_back(35); cout<<"初始化双端队列d："<<endl; for(int i = 0; i < d.size(); i++) { cout<<d.at(i)<<"\t"; } cout<<endl; d.push_front(10);//容器的开始位置插入一个新的元素，位于当前的第一个元素之前 d.push_front(7); d.push_front(1); cout<<"队列d向前陆续插入10、7、1:"<<endl; for(int i = 0;i < d.size();i++) { cout<<d.at(i)<<"\t"; } cout<<endl; d.pop_back(); //删除 deque 容器中的最后一个元素，有效地将容器大小减少一个 d.pop_front(); //删除 deque 容器中的第一个元素，有效地减小其大小 cout<<"删除deque最后一个和第一个元素后:"<<endl; for(int i = 0;i < d.size();i++) { cout<<d.at(i)<<"\t"; } cout<<endl; return 0; }
forward_list
在头文件中，与list类似，区别就是list时双链表，forward_list是单链表，forward_list（单向链表）是序列容器，允许在序列中的任何地方进行恒定的时间插入和擦除操作。在链表的任何位置进行插入/删除操作都非常快。
forward_list的特点：
forward_list只提供钱箱迭代器，因此不支持反向迭代器，比如rbegin()等成员函数。
forward_list不提供size（）成员函数。
forward_list没有指向最末元素的锚点，因此不提供back（）、push_back（）和pop_back（）。
forward_list不提供随机访问，这一点跟list相同。
插入和删除元素不会造成“指向至其他元素”的指针，引用和迭代器失效。
容器成员函数总结就不写了,太多影响阅读,感兴趣小伙伴戳http://www.cplusplus.com/reference/stl/
list
list双向链表，是序列容器，允许在序列中的任何地方进行常数时间插入和擦除操作，并在两个方向上进行迭代,可以高效地进行插入删除元素。
使用list容器之前必须加上头文件：#include;
list容器的底层实现:
和 array、vector 这些容器迭代器的实现方式不同，由于 list 容器的元素并不是连续存储的，所以该容器迭代器中，必须包含一个可以指向 list 容器的指针，并且该指针还可以借助重载的 *、++、--、==、!= 等运算符，实现迭代器正确的递增、递减、取值等操作。
template<tyepname T,...> struct __list_iterator{ __list_node<T>* node; //... //重载 == 运算符 bool operator==(const __list_iterator& x){return node == x.node;} //重载 != 运算符 bool operator!=(const __list_iterator& x){return node != x.node;} //重载 * 运算符，返回引用类型 T* operator *() const {return *(node).myval;} //重载前置 ++ 运算符 __list_iterator<T>& operator ++(){ node = (*node).next; return *this; } //重载后置 ++ 运算符 __list_iterator<T>& operator ++(int){ __list_iterator<T> tmp = *this; ++(*this); return tmp; } //重载前置 -- 运算符 __list_iterator<T>& operator--(){ node = (*node).prev; return *this; } //重载后置 -- 运算符 __list_iterator<T> operator--(int){ __list_iterator<T> tmp = *this; --(*this); return tmp; } //... }
stack
stack底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
底层用deque实现：
//deque<T> >中间有个空格是为了兼容较老的版本 template <class T, class 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(); } // deque 是两头可进出，stack 是末端进，末端出（所以后进者先出）。 void push(const value_type& x) { c.push_back(x); } void pop() { c.pop_back(); } }; template <class T, class Sequence> bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) { return x.c == y.c; } template <class T, class Sequence> bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) { return x.c < y.c; }
底层用list实现
#include<stack> #include<list> #include<algorithm> #include <iostream> using namespace std; int main(){ stack<int, list<int>> istack; istack.push(1); istack.push(3); istack.push(5); cout << istack.size() << endl; //3 cout << istack.top() << endl;//5 istack.pop(); cout << istack.top() << endl;//3 cout << istack.size() << endl;//2 system("pause"); return 0; }
queue
queue 是一种容器适配器，用于在FIFO（先入先出）的操作，其中元素插入到容器的一端并从另一端提取。
队列不提供迭代器，不实现遍历操作。
template <class T, class Sequence = deque<T> > class queue { friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y); friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y); 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: bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference front() { return c.front(); } const_reference front() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } void push(const value_type& x) { c.push_back(x); } void pop() { c.pop_front(); } }; template <class T, class Sequence> bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) { return x.c == y.c; } template <class T, class Sequence> bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) { return x.c < y.c; }
