?目錄

容器適配器

deque的原理介紹

stack模擬實現

queue模擬實現

priority_queue模擬實現

仿函數

---

容器適配器

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

可以這樣理解：通過適配器模式，可以將不兼容的接口正常運作。

---

?STL標準庫中stack和queue的底層結構

雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配 器，這是因為stack和隊列只是對其他容器的接口進行了包裝，STL中stack和queue默認使用deque，比如：

---

那么這里的deque是什么東西呢？

deque的原理介紹

deque(雙端隊列)：是一種雙開口的"連續"空間的數據結構，雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。

?deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似于一個動態的二維數組。

?我們假設一個buff是10個int大小的空間數組，map中存放了每個buff數組的地址，buff數組用來存放數據，可以理解他從中間開始利用空間，向左右擴容。

?我們可以理解為他在map中間進行插入刪除操作：

1. 與vector比較，deque的優勢是：頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是必vector高的。
2. 與list比較，其底層是連續空間，空間利用率比較高，不需要存儲額外字段。

但是，deque有一個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經常遍歷，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層數據結構。?

為什么選擇deque作為stack和queue的底層默認容器？我們給出了以下兩點原因：

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

---

stack模擬實現

目前為止，我們已經了解了兩種模式：

1. 適配器模式 -- 封裝轉換
2. 迭代器模式 -- 封裝統一訪問方式（數據結構訪問都可以用）

接下來試著通過運用適配器來模擬實現stack和queue：

//Stack.h
#pragma oncenamespace bit
{template<class T, class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){_con.size();}private:Container _con;};
}

?我們只需要定義一個適配器類型的成員變量_con，他默認可以使用push_back，pop_back等常規接口，直接利用接口實現操作即可。stack用vector和list都可以實現，測試代碼如下：

void test_stack()
{//bit::stack<int, vector<int>> s;//bit::stack<int, list<int>> s; bit::stack<int, deque<int>> s;  //bit::stack<int> s; //不傳第二個參數默認使用deques.push(1);s.push(2);s.push(3);s.push(4);while (!s.empty()){cout << s.top() << " ";s.pop();}cout << endl;
}

---

queue模擬實現

//Queue.h
#pragma oncenamespace bit
{// deque list// 不支持vectortemplate<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();// 這樣就可以支持vector了，但是效率就很低了//_con.erase(_con.begin());}T& back(){return _con.back();}T& front(){return _con.front();}bool empty(){return _con.empty();}size_t size(){_con.size();}private:Container _con;};
}

注意：queue不支持vector適配器，原因是vector沒有pop_front的接口，如果要實現要用erase接口，但是頭刪完后面所有數據要往前挪，消耗時間太大，不建議這樣做。測試代碼如下：

void test_queue()
{bit::queue<int> q;//bit::queue<int,list<int>> q;// 不支持//bit::queue<int, vector<int>> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;
}

---

priority_queue模擬實現

仿函數

在實現之前先了解仿函數的概念：重載了operator（）的類

特點：參數個數和返回值根據需求確定，不固定，很靈活

?通過這個概念可以實現STL庫里的greater和less同等效果的仿函數。

//priority_queue.h
#pragma oncenamespace bit
{template<class T>class myless{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class mygreater{public:bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = vector<T>, class Comapre = myless<T>>class priority_queue{public:priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}}void adjust_up(int child){Comapre comfunc;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (comfunc(_con[parent], _con[child]))//if (comfunc.operator()(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){Comapre comfunc;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child+1 < _con.size() && _con[child] < _con[child+1] )if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1])){++child;}//if (_con[parent] < _con[child])if (comfunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

我們可以通過顯式調用greater仿函數來實現小堆，測試代碼如下：

void test_priority_queue()
{//vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };//priority_queue<int> q1(v.begin(), v.end());int a[] = { 3,2,7,6,0,4,1,9,8,5 };// 默認是大堆//bit::priority_queue<int> q1(a, a+sizeof(a)/sizeof(int));// 小堆bit::priority_queue<int, vector<int>, bit::mygreater<int>> q1(a, a + sizeof(a) / sizeof(int));while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;
}