deque
deque容器為一個給定類型的元素進行線性處理，像向量一樣，它能夠快速地随機通路任一個元素，并且能夠高效地插入和删除容器的尾部元素。但它又與vector不同，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;
}