什么是容器適配器

適配器是一種設計模式(設計模式是一套被反復使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總
結)，該種模式是將一個類的接口轉換成客戶希望的另外一個接口。

底層邏輯

stack和queue都是容器適配器,底層都是通過去適配雙端隊列deque去實現的,STL中沒有把stack和queue劃分在容器中,而是放在容器適配器,stack和queue默認使用deque.


那可不可以用vector去適配呢?
這也是可以的,只要是他們的所有接口,在這個容器中包含就可以進行適配,那么為什么底層默認會選擇使用deque去進行適配呢?
deque(雙端隊列)：是一種雙開口的"連續"空間的數據結構，雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。
deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似于一個動態的二維數組。
與vector比較，deque的優勢是：頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是必vector高的。
與list比較，其底層是連續空間，空間利用率比較高，不需要存儲額外字段。但是，deque有一個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到
某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經常遍歷，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層數據結構

為什么選擇deque作為stack和queue的底層默認容器

stack是一種后進先出的特殊線性數據結構，因此只要具有push_back()和pop_back()操作的線性結構，都可以作為stack的底層容器，比如vector和list都可以；queue是先進先出的特殊線性數據結構，只要具有push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如list。但是STL中對stack和queue默認選擇deque作為其底層容器，主要是因為：

1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。
2. 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數據)；queue中的元素增長時，deque不僅效率高，而且內存使用率高。結合了deque的優點，而完美的避開了其缺陷。

優先隊列

優先隊列本質上就是topk問題,那么優先隊列是怎么實現的呢？
優先隊列的底層物理結構是數組,其中模板參數Compare是控制優先隊列是大堆還是小堆,
優先隊列默認是大堆–缺省參數就是less,如果要給大堆就是greater
這兩個模板參數的底層實現:

//仿函數/函數對象
//重載了括號,讓類可以向函數一樣被調用
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};

優先隊列的模擬實現

//優先隊列,其實就是topk問題,底層結構就是堆,所以我們用數組---vector來存取數據template<class T, class Container = vector<T>, class Compare = less<T>>//默認是大堆,less對應的就是大堆//greater<T>對應的是小堆 通過傳Compare來控制大堆還是小堆,默認不傳是大堆//仿函數控制實現大小堆class priority_queue{private:void AdjustDown(size_t parent){Compare com;size_t chidren = parent * 2 + 1;while (chidren < _con.size()){if (chidren + 1 < _con.size() && com( _con[chidren], _con[chidren + 1])){chidren += 1;}//if (_con[parent] < _con[chidren])if (com(_con[parent], _con[chidren])){swap(_con[parent], _con[chidren]);parent = chidren;chidren = parent * 2 + 1;}else{break;}}}void AdjustUp(int chidren){Compare com;int parent = (chidren - 1) / 2;while (parent >= 0){if (com(_con[parent], _con[chidren])){swap(_con[chidren], _con[parent]);chidren = parent;parent = (chidren - 1) / 2;}else{break;}}}public:priority_queue(){}template<class InputInterator>priority_queue(InputInterator first, InputInterator last){//插入數據while (first != last){_con.push_back(*first);++first;}//建堆//從最后一個非葉子節點開始建堆-----關鍵for (int i = (_con.size()-1-1) / 2; i >= 0; i--){AdjustDown(i);}}void pop()//刪除的是第一個元素{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}void push(const T& x){//_con[_con.size()] = x;_con.push_back(x);AdjustUp(_con.size() - 1);}T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};

stack和queue的模擬實現

#pragma once//適配器模擬實現
namespace sw
{	//數組棧與鏈式棧之間秒切換---------適配器template<class T, class Container = deque<T>>//模板參數不僅可以是int,double等內置類型也可以是容器,同時也可以給缺省值class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();//取最后一個元素,}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_stack(){cout << "stack" << endl;stack<int, vector<int>> st1;st1.push(1);st1.push(2);st1.push(3);st1.push(4);while (!st1.empty()){cout << st1.top() << " ";st1.pop();}cout << endl;stack<int, list<int>> st2;st2.push(1);st2.push(2);st2.push(3);st2.push(4);while (!st2.empty()){cout << st2.top() << " ";st2.pop();}cout << endl;stack<int> st3;st3.push(1);st3.push(2);st3.push(3);st3.push(4);while (!st3.empty()){cout << st3.top() << " ";st3.pop();}cout << endl;}
}

#pragma oncenamespace sw
{//適配器template<class T, class Container = deque<T>>//模板參數不僅可以是int,double等內置類型也可以是容器,同時也可以給缺省值class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& front(){return _con.front();}T& back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_queue(){cout << "queue" << endl;queue<int, deque<int>> q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);while (!q1.empty()){cout << q1.front() << " ";q1.pop();}cout << endl;queue<int, list<int>> q2;q2.push(1);q2.push(2);q2.push(3);q2.push(4);while (!q2.empty()){cout << q2.front() << " ";q2.pop();}cout << endl;}
}