目錄

1.容器適配器

4.1 什么是適配器

4.2 STL標(biāo)準(zhǔn)庫(kù)中的容器適配器

?2.stack的使用

2.1 STL庫(kù)中對(duì)stack的實(shí)現(xiàn)?

?3.queue的使用

3.1 STL庫(kù)中對(duì)queue的實(shí)現(xiàn)

?4.priority_queue使用

4.1模擬實(shí)現(xiàn)?priority_queue

5.deque 的簡(jiǎn)介

---

1.容器適配器

4.1 什么是適配器

• 適配器是一種設(shè)計(jì)模式
• 該種模式是將一個(gè)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口
• 這個(gè)有點(diǎn)像我們的手機(jī)充電器，我們手機(jī)充電是要USB接口，我們的充電頭就相當(dāng)于適配器

4.2 STL標(biāo)準(zhǔn)庫(kù)中的容器適配器

• 雖然stack和queue以及priority_queue中也可以存放元素，但在STL中并沒(méi)有將其劃分在容器的行列，而是將其稱為容器適配器
• 這是因?yàn)閟tack和隊(duì)列只是對(duì)其他容器的接口進(jìn)行了包裝，STL中stackqueue以及priority_queue默認(rèn)使用deque

?2.stack的使用

1. stack是一種容器適配器，專門用在具有后進(jìn)先出操作的上下文環(huán)境中，其刪除只能從容器的一端進(jìn)行元素的插入與提取操作。
2. stack是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對(duì)特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
3. stack的底層容器可以是任何標(biāo)準(zhǔn)的容器類模板或者一些其他特定的容器類，這些容器類應(yīng)該支持以下操作：

• empty?
• size
• push_back
• pop_back

標(biāo)準(zhǔn)容器vector、deque、list均符合這些需求，默認(rèn)情況下，如果沒(méi)有為stack指定特定的底層容器，默認(rèn)情況下使用deque?

? ? ?stack的各個(gè)接口? ? ? ? ? ? ? ? ? ? ? ? ?頭文件為：#include<stack>

• stack()????????????????????????構(gòu)造空的棧
• empty() ? ? ? ? ? ? ? ? ? ? ? 檢測(cè)stack是否為空
• size()? ? ? ? ? ? ? ? ? ? ? ? ??返回stack中元素的個(gè)數(shù)
• top()???????????????????????????返回棧頂元素的引用
• push() ???????????????????????將元素val壓入stack中
• pop()??????????????????????????將stack中尾部的元素彈出

手撕：棧的實(shí)現(xiàn)（使用數(shù)組）-CSDN博客?

2.1 STL庫(kù)中對(duì)stack的實(shí)現(xiàn)?

#include<vector>
#include<list>
#include<deque>namespace wh
{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(){return _con.size();}private:Container _con;};
}

?3.queue的使用

1. 隊(duì)列是一種容器適配器，專門用于在FIFO上下文(先進(jìn)先出)中操作，其中從容器一端插入元素，另一端提取元素。
2. 隊(duì)列作為容器適配器實(shí)現(xiàn)，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素。元素從隊(duì)尾入隊(duì)列，從隊(duì)頭出隊(duì)列。
3. 底層容器可以是標(biāo)準(zhǔn)容器類模板之一，也可以是其他專門設(shè)計(jì)的容器類。該底層容器應(yīng)至少支持以下操作:

• empty：檢測(cè)隊(duì)列是否為空
• size：返回隊(duì)列中有效元素的個(gè)數(shù)
• front：返回隊(duì)頭元素的引用
• back：返回隊(duì)尾元素的引用
• push_back：在隊(duì)列尾部入隊(duì)列
• pop_front：在隊(duì)列頭部出隊(duì)列

標(biāo)準(zhǔn)容器類deque和list滿足了這些要求。默認(rèn)情況下，如果沒(méi)有為queue實(shí)例化指定容器類，則使用標(biāo)準(zhǔn)容器deque

??? ? ?queue的各個(gè)接口??????????????????????????頭文件為：#include<queue>

• queue() ????????????????????????構(gòu)造空的隊(duì)列
• empty() ????????????????????????檢測(cè)隊(duì)列是否為空，是返回true，否則返回false
• size() ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回隊(duì)列中有效元素的個(gè)數(shù)
• front() ? ? ? ? ? ? ? ? ? ? ? ? ? 返回隊(duì)頭元素的引用
• back() ? ? ? ? ? ? ? ? ? ? ? ? ? 返回隊(duì)尾元素的引用
• push() ? ? ? ? ? ? ? ? ? ? ? ? ?在隊(duì)尾將元素val入隊(duì)列
• pop()? ? ? ? ? ? ? ? ? ? ? ? ? ??將隊(duì)頭元素出隊(duì)列

手撕：隊(duì)列的實(shí)現(xiàn)_元清加油的博客-CSDN博客?

3.1 STL庫(kù)中對(duì)queue的實(shí)現(xiàn)

#include<vector>
#include<list>
#include<deque>namespace wh
{template<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front(){return _con.front();}const T& back(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
};

?4.priority_queue使用

1. 優(yōu)先隊(duì)列是一種容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個(gè)元素總是它所包含的元素中最大的(默認(rèn)情況下priority_queue是大堆,也可以是小堆)
2. 此上下文類似于堆，在堆中可以隨時(shí)插入元素，并且只能檢索最大堆元素(優(yōu)先隊(duì)列中位于頂部的元素)。
3. 優(yōu)先隊(duì)列被實(shí)現(xiàn)為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素。元素從特定容器的“尾部”彈出，其稱為優(yōu)先隊(duì)列的頂部。
4. 底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計(jì)的容器類。容器應(yīng)該可以通過(guò)隨機(jī)訪問(wèn)迭代器訪問(wèn)，并支持以下操作：

• empty()：檢測(cè)容器是否為空
• size()：返回容器中有效元素個(gè)數(shù)
• front()：返回容器中第一個(gè)元素的引用
• push_back()：在容器尾部插入元素
• pop_back()：刪除容器尾部元素

• priority_queue()????????????????????????構(gòu)造一個(gè)空的優(yōu)先級(jí)隊(duì)列
• empty( ) ????????????????????????????????????檢測(cè)優(yōu)先級(jí)隊(duì)列是否為空，是返回true，否則返回false
• top( ) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?返回優(yōu)先級(jí)隊(duì)列中最大(最小元素)，即堆頂元素
• push(x) ?????????????????????????????????????在優(yōu)先級(jí)隊(duì)列中插入元素x
• pop()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 刪除優(yōu)先級(jí)隊(duì)列中最大(最小)元素，即堆頂元素

1. 默認(rèn)情況下，priority_queue是大堆?

#include <vector>
#include <queue>
#include <functional> // greater算法的頭文件void test()
{vector<int> v{3,2,7,6,0,4,1,9,8,5};  // 默認(rèn)情況下，創(chuàng)建的是大堆，其底層按照小于號(hào)比較priority_queue<int> q1;for (auto& e : v)
{q1.push(e);
}cout << q1.top() << endl;// 如果要?jiǎng)?chuàng)建小堆，將第三個(gè)模板參數(shù)換成greater比較方式priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl;
}

?2. 如果在priority_queue中放自定義類型的數(shù)據(jù)，用戶需要在自定義類型中提供 > 或者< 的重載

4.1模擬實(shí)現(xiàn)?priority_queue

#include<vector>namespace wh
{template<class T, class Container = std::vector<T>, class Compare = std::less<T>>class priority_queue{public://構(gòu)造函數(shù)priority_queue(){}//迭代器構(gòu)造函數(shù)template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i = (_con.size() - 2) / 2; i >= 0; --i){adjust_down(i);}}void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size()&& com(_con[child], _con[child + 1])){++child;}if (_con[parent] < _con[child]){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

5.deque 的簡(jiǎn)介

deque(雙端隊(duì)列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開口的含義是：可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)

deque的缺陷

• 與vector比較，deque的優(yōu)勢(shì)是：頭部插入和刪除時(shí)，不需要搬移元素，效率特別高，而且在擴(kuò)容時(shí)，也不需要搬移大量的元素，因此其效率是必vector高的。
• 與list比較，其底層是連續(xù)空間，空間利用率比較高，不需要存儲(chǔ)額外字段。
• 但是，deque有一個(gè)致命缺陷：不適合遍歷，因?yàn)樵诒闅v時(shí)，deque的迭代器要頻繁的去檢測(cè)其是否移動(dòng)到某段小空間的邊界，導(dǎo)致效率低下，而序列式場(chǎng)景中，可能需要經(jīng)常遍歷，因此在實(shí)際中，需要線性結(jié)構(gòu)時(shí)，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應(yīng)用并不多，而目前能看到的一個(gè)應(yīng)用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)。

• stack和queue不需要遍歷(因此stack和queue沒(méi)有迭代器)，只需要在固定的一端或者兩端進(jìn)行操作?
• 在stack中元素增長(zhǎng)時(shí)，deque比vector的效率高(擴(kuò)容時(shí)不需要搬移大量數(shù)據(jù))；queue中的元素增長(zhǎng)時(shí)，deque不僅效率高，而且內(nèi)存使用率高
• 結(jié)合了deque的優(yōu)點(diǎn)，而完美的避開了其缺陷