容器適配器

容器適配器（Container Adapter）是C++標(biāo)準(zhǔn)模板庫(kù)（STL）中的一種設(shè)計(jì)模式，專門用于提供一種經(jīng)過簡(jiǎn)化和限制的接口，使得不同的容器類型可以表現(xiàn)出類似的行為。容器適配器不會(huì)創(chuàng)建新的容器，而是基于已有的容器（如 deque、vector 等）進(jìn)行包裝，以改變或限制其接口，從而提供不同的行為和使用方式。

STL 中常見的容器適配器有以下三種：

1. 棧（Stack）

• 使用 std::stack 類實(shí)現(xiàn)。

• 默認(rèn)底層容器為 std::deque，也可以用 std::vector 或 std::list 替換。

• 棧是“后進(jìn)先出” (LIFO) 數(shù)據(jù)結(jié)構(gòu)，適配器屏蔽了底層容器的大部分接口，提供 push、pop 和 top 操作。

2. 隊(duì)列（Queue）

• 使用 std::queue 類實(shí)現(xiàn)。

• 默認(rèn)底層容器為 std::deque，也可以使用其他序列容器（如 std::list）。

• 隊(duì)列是“先進(jìn)先出” (FIFO) 數(shù)據(jù)結(jié)構(gòu)，適配器僅保留 push、pop 和 front、back 等接口。

3. 優(yōu)先級(jí)隊(duì)列（Priority Queue）

• 使用 std::priority_queue 類實(shí)現(xiàn)。

• 默認(rèn)底層容器為 std::vector，底層使用堆結(jié)構(gòu)進(jìn)行元素排序。

• 優(yōu)先級(jí)隊(duì)列允許快速訪問和移除最高優(yōu)先級(jí)的元素。適配器提供 push、pop 和 top 操作，自動(dòng)按照優(yōu)先級(jí)排序。

容器適配器的特點(diǎn)

• 簡(jiǎn)化接口：容器適配器通過隱藏底層容器的復(fù)雜接口，使用戶能夠更專注于特定的數(shù)據(jù)結(jié)構(gòu)（如?；蜿?duì)列）的特性。

• 靈活底層容器：容器適配器可以基于不同的底層容器構(gòu)建，但需滿足特定的要求。例如，?？梢杂?deque 或 vector 作為底層容器。

• 與容器解耦：通過使用適配器，用戶不需要關(guān)心底層容器的實(shí)現(xiàn)細(xì)節(jié)，只需專注于適配器提供的接口。

總體而言，容器適配器是一種設(shè)計(jì)模式，通過包裝現(xiàn)有容器來提供定制化的數(shù)據(jù)結(jié)構(gòu)接口，使程序設(shè)計(jì)更加簡(jiǎn)單和靈活。

---

棧和隊(duì)列的模擬實(shí)現(xiàn)

我們通過適配器就能將棧和隊(duì)列進(jìn)行模擬實(shí)現(xiàn)了

stack.h

#pragma once
#include<vector>
#include<list>
#include<deque>
//template<class T>
//class stack
//{
//private:
//	T* a;
//	size_t _top;
//	size_t _capacity;
//};//  T（棧中存儲(chǔ)的數(shù)據(jù)類型）和 Container（底層容器類型）
/*
當(dāng)你在實(shí)例化這個(gè)模板類時(shí)，例如 stack<int, std::vector<int>> myStack;，編譯器就會(huì)根據(jù)傳入的模板參數(shù) int 和 std::vector<int> 來推導(dǎo)出具體的 T 和 Container 類型。
模板實(shí)例化：在編譯階段，編譯器會(huì)用傳遞的模板參數(shù)類型 T 和 Container 來實(shí)例化這個(gè)模板類 stack，并生成相應(yīng)的類定義。例如，如果你傳入的是 stack<int, std::vector<int>>，
編譯器會(huì)生成一個(gè) stack<int, std::vector<int>> 的具體實(shí)例，并將代碼中所有的 T 替換為 int，Container 替換為 std::vector<int>。
模板函數(shù)的調(diào)用：在使用這個(gè)棧的成員函數(shù)時(shí)，編譯器也會(huì)根據(jù)實(shí)例化后的具體類型來判斷類型。例如 _con.push_back(x); 調(diào)用時(shí)，
編譯器會(huì)檢查 _con 是什么容器類型（在這種情況下是 std::vector<int>），從而驗(yàn)證 push_back 是否可以接受 int 類型的參數(shù) x。
*///T是元素的類型，這個(gè)Container是容器的類型，我們通過容器進(jìn)行函數(shù)的調(diào)用操作
namespace kai
{//函數(shù)參數(shù)能加缺省值，那么我們的模版參數(shù)也是可以加缺省值的//如果我們沒傳的話就用的是缺省值，傳了的話那么就用我們傳的值//我們這里默認(rèn)用的是一個(gè)deque的容器template<class T, class Container=deque<T>>//Container就是容器的意思,存的是底層的數(shù)據(jù)類型class stack{public:void push(const T& x){_con.push_back(x);}void pop()//不需要加參數(shù) {_con.pop_back();//將尾部的數(shù)據(jù)pop掉}const T& top() const//返回棧頂位置數(shù)據(jù){return _con.back();//直接返回尾部的數(shù)據(jù)，通用接口}size_t size() const{return  _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

queue.h

#pragma once
#include<vector>
#include<list>
#include<deque>namespace kai
{//deque既可以做棧也可以做隊(duì)列的適配容器template<class T, class Container = deque<T>>//Container就是容器的意思,存的是底層的數(shù)據(jù)類型class queue//隊(duì)尾入數(shù)據(jù)，隊(duì)頭出數(shù)據(jù){//vector不能適配隊(duì)列，這里不能頭刪public:void push(const T& x)//入隊(duì)列--尾{_con.push_back(x);}void pop()//   出隊(duì)列---頭刪{_con.pop_front();//將頭部的數(shù)據(jù)pop掉}const T&front() const{return _con.front(); //直接返回頭部的數(shù)據(jù)，通用接口}const T& back() const//返回棧頂位置數(shù)據(jù){return _con.back();//直接返回尾部的數(shù)據(jù)，通用接口}size_t size() const{return  _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}

test.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<queue>#include"stack.h"
#include"Queue.h"
using namespace std;
int main()
{kai::stack<int,list<int>>st;//前面是數(shù)據(jù)的類型。后面是容器的類型st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty())//不斷取值直到棧為空{(diào)cout << st.top() << " ";st.pop();//頭刪替換下個(gè)數(shù)據(jù)}cout << endl;//這里的vector是會(huì)報(bào)錯(cuò)的，因?yàn)関ector是不支持這里的pop的kai::queue<int, list<int>>q;//前面是數(shù)據(jù)的類型。后面是容器的類型q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty())//不斷取值直到棧為空{(diào)cout << q.front() << " ";q.pop();//頭刪替換下個(gè)數(shù)據(jù)}cout << endl;return 0;
}

當(dāng)你在實(shí)例化這個(gè)模板類時(shí)，例如 stack<int, std::vector> myStack;，編譯器就會(huì)根據(jù)傳入的模板參數(shù) int 和 std::vector 來推導(dǎo)出具體的 T 和 Container 類型。
模板實(shí)例化：在編譯階段，編譯器會(huì)用傳遞的模板參數(shù)類型 T 和 Container 來實(shí)例化這個(gè)模板類 stack，并生成相應(yīng)的類定義。例如，如果你傳入的是 stack<int, std::vector>，
編譯器會(huì)生成一個(gè) stack<int, std::vector> 的具體實(shí)例，并將代碼中所有的 T 替換為 int，Container 替換為 std::vector。
模板函數(shù)的調(diào)用：在使用這個(gè)棧的成員函數(shù)時(shí)，編譯器也會(huì)根據(jù)實(shí)例化后的具體類型來判斷類型。例如 _con.push_back(x); 調(diào)用時(shí)，
編譯器會(huì)檢查 _con 是什么容器類型（在這種情況下是 std::vector），從而驗(yàn)證 push_back 是否可以接受 int 類型的參數(shù) x。

---

deque的介紹

deque叫做雙端隊(duì)列，兩端都可以進(jìn)行插入刪除的操作

頭尾都可以支持插入刪除數(shù)據(jù)的

deque的技能樹點(diǎn)的比較滿，啥都會(huì)

那么就說明deque就可以將list和vector的技能都帶上

vector是一塊連續(xù)的空間，list是一個(gè)個(gè)小塊的空間通過指針進(jìn)行連接起來的

deque的缺陷在哪里呢？

insert和erase

1.挪動(dòng)后面所有數(shù)據(jù)，效率低

2.只挪動(dòng)當(dāng)前buffer的數(shù)據(jù)，每個(gè)buffer大小就不一樣了，insert 、 erase的效率不錯(cuò)，但是[]的效率直線下降

deque的頭尾插入刪除的效率還是不錯(cuò)的

適當(dāng)?shù)南聵?biāo)訪問可以使用deque

但是得大量的下標(biāo)訪問就不適合用deque了

所以棧和隊(duì)列的適配容器是deque

deque的核心結(jié)構(gòu)是迭代器進(jìn)行支撐的

deque里面只有兩個(gè)迭代器，start和finish

在 C++ 中，deque 是一種雙端隊(duì)列容器，允許在兩端高效地插入和刪除元素。盡管 deque 在某些方面具有優(yōu)勢(shì)，但在特定使用場(chǎng)景下仍然存在一些缺陷或限制：

1. 內(nèi)存開銷較高

• deque 的內(nèi)存布局并不像 vector 一樣是連續(xù)的內(nèi)存塊，而是分段的。這使得 deque 會(huì)有額外的內(nèi)存管理開銷，因此其內(nèi)存利用率通常比 vector 低。

• 對(duì)于需要大量小型數(shù)據(jù)結(jié)構(gòu)的應(yīng)用，deque 的內(nèi)存分塊可能帶來一定的開銷。

2.隨機(jī)訪問性能略低于 vector

• 雖然 deque 支持隨機(jī)訪問（允許使用 operator[] 和 at），但由于 deque 是分塊存儲(chǔ)的，因此在訪問元素時(shí)，尤其是訪問中間位置的元素時(shí)，性能會(huì)略低于 vector，因?yàn)樗枰ㄎ痪唧w的分塊位置。

3. 與指針或迭代器的兼容性r

• deque 的指針或迭代器在插入和刪除操作后可能會(huì)失效，尤其是在中間插入或刪除元素時(shí)。

• 雖然 deque 的頭尾插入操作不會(huì)像 vector 一樣導(dǎo)致整個(gè)容器重新分配，但在擴(kuò)展容量時(shí)，它可能會(huì)重新配置分塊，這會(huì)導(dǎo)致指針和迭代器失效。

4. 不適合用于需要頻繁中間插入和刪除的場(chǎng)景

• deque 在頭尾的插入和刪除操作效率很高，但在中間位置插入或刪除元素時(shí)會(huì)導(dǎo)致較多的數(shù)據(jù)移動(dòng)，從而影響性能。因此，如果需要頻繁在中間位置進(jìn)行插入或刪除操作，deque 不是最佳選擇，list 或 std::vector（如果可以接受一定的重新分配開銷）可能會(huì)更合適。

5. 在特定平臺(tái)上的實(shí)現(xiàn)不一致

• 不同的編譯器和標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)可能會(huì)對(duì) deque 采用不同的分塊策略。這可能導(dǎo)致在不同平臺(tái)上的性能和內(nèi)存使用情況有所不同，從而帶來一些不可預(yù)測(cè)的行為。

6. 缺乏shrink_to_fit支持

• C++ 標(biāo)準(zhǔn)中沒有要求 deque 支持 shrink_to_fit，即使進(jìn)行了刪除操作，deque 可能不會(huì)自動(dòng)釋放不再使用的內(nèi)存，導(dǎo)致可能的內(nèi)存浪費(fèi)。

總結(jié)

deque 在需要高效的雙端插入和刪除操作時(shí)非常有用，但在需要頻繁的中間操作或更高的隨機(jī)訪問性能時(shí)，它的效率可能不如 vector。選擇容器時(shí)應(yīng)根據(jù)具體需求進(jìn)行權(quán)衡，以最大限度地發(fā)揮各容器的優(yōu)勢(shì)。

題目

215. 數(shù)組中的第K個(gè)最大元素

class Solution {
public:int findKthLargest(vector<int>& nums, int k){//將數(shù)組中的元素先放入到優(yōu)先級(jí)隊(duì)列中,默認(rèn)是大堆priority_queue<int> p(nums.begin(),nums.end());//我們刪除k-1次，那么循環(huán)結(jié)束的時(shí)候的堆頂?shù)臄?shù)據(jù)就是當(dāng)前最大了的，我們直接返回堆頂數(shù)據(jù)就行了while(--k)//--k是走k-1次,k--是走k次{p.pop();}return p.top();}
};

---

priority_queue 優(yōu)先級(jí)隊(duì)列

默認(rèn)是大的優(yōu)先級(jí)最高

priority_queue 是一種基于優(yōu)先級(jí)的隊(duì)列數(shù)據(jù)結(jié)構(gòu)，通常實(shí)現(xiàn)為一個(gè)堆（heap），可以支持快速插入和刪除優(yōu)先級(jí)最高的元素。在 priority_queue 中，元素的順序不是按插入順序排列的，而是根據(jù)優(yōu)先級(jí)排序。通常有兩種類型的優(yōu)先隊(duì)列：

1. 最大優(yōu)先隊(duì)列：優(yōu)先級(jí)最高的元素位于隊(duì)列頂部（即最大值在最前面）。

2. 最小優(yōu)先隊(duì)列：優(yōu)先級(jí)最低的元素位于隊(duì)列頂部（即最小值在最前面）。

以下是一些關(guān)于 priority_queue 的關(guān)鍵操作：

• 插入元素：將新元素插入到隊(duì)列中，優(yōu)先級(jí)隊(duì)列會(huì)自動(dòng)調(diào)整元素的位置。

• 訪問隊(duì)首元素：訪問優(yōu)先級(jí)最高的元素（在最大優(yōu)先隊(duì)列中為最大值，在最小優(yōu)先隊(duì)列中為最小值）。

• 刪除隊(duì)首元素：刪除優(yōu)先級(jí)最高的元素。

• 判斷隊(duì)列是否為空：檢查隊(duì)列中是否有元素。

在 C++ 標(biāo)準(zhǔn)模板庫(kù)（STL）中，priority_queue 的使用非常常見，以下是一個(gè)簡(jiǎn)單的代碼示例：

#include <iostream>
#include <queue>int main() {std::priority_queue<int> maxQueue;  // 默認(rèn)是最大優(yōu)先隊(duì)列// 插入元素maxQueue.push(10);maxQueue.push(30);maxQueue.push(20);maxQueue.push(5);// 輸出并刪除最大元素while (!maxQueue.empty()) {std::cout << maxQueue.top() << " ";maxQueue.pop();}return 0;
}

使用最小優(yōu)先隊(duì)列

在 C++ 中，要?jiǎng)?chuàng)建最小優(yōu)先隊(duì)列，可以使用以下方式：

std::priority_queue<int, std::vector<int>, std::greater<int>> minQueue;

使用場(chǎng)景

• 任務(wù)調(diào)度：例如操作系統(tǒng)中的任務(wù)調(diào)度器，根據(jù)任務(wù)的優(yōu)先級(jí)調(diào)度執(zhí)行任務(wù)。

• 路徑查找：如 Dijkstra 算法使用優(yōu)先隊(duì)列來找到最短路徑。

• 事件驅(qū)動(dòng)模擬：在模擬系統(tǒng)中用來根據(jù)事件的優(yōu)先級(jí)處理事件。

priority_queue 是一種非常高效的數(shù)據(jù)結(jié)構(gòu)，適合需要頻繁處理優(yōu)先級(jí)數(shù)據(jù)的場(chǎng)景。

int main()
{//優(yōu)先級(jí)隊(duì)列//優(yōu)先級(jí)默認(rèn)是大的優(yōu)先級(jí)高//priority_queue<int> pq;//下面的就是小的優(yōu)先級(jí)高了priority_queue<int,vector<int>,greater<int>> pq;//前面是數(shù)據(jù)的類型。后面是容器的類型pq.push(3);pq.push(2);pq.push(1);pq.push(4);while (!pq.empty())//不斷取值直到棧為空{(diào)cout << pq.top() << " ";pq.pop();//頭刪替換下個(gè)數(shù)據(jù)}return 0;
} 

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

#pragma once
#include<vector>//默認(rèn)是vector進(jìn)行適配的
//堆是將數(shù)組看成完全二叉樹的
//假設(shè)p是父親，那么2*p+1是左孩子，2*p+2是右孩子
//所以對(duì)于子節(jié)點(diǎn)的話，-1然后/2就能算到父親節(jié)點(diǎn)的下標(biāo)了
namespace kai
{//仿函數(shù)
//對(duì)象可以像函數(shù)一樣進(jìn)行使用，因?yàn)樗剌d了operator()template <class T>struct less{bool operator() (const T& x, const T& y)const{return x < y;}};template <class T>struct greater//大堆，大于的比較{bool operator() (const T& x, const T& y)const{return x > y;}};//Compare是類型，我們這里默認(rèn)值是小堆template<class T ,class Container=vector<T>,class Compare=less<T>>//優(yōu)先級(jí)隊(duì)列class priority_queue{public:priority_queue() = default;//default是強(qiáng)制生成//我們不寫默認(rèn)構(gòu)造的話那么就會(huì)調(diào)用對(duì)應(yīng)類型的默認(rèn)構(gòu)造函數(shù)了template<class InputIterator>//構(gòu)造函數(shù)priority_queue(InputIterator first, InputIterator last)//這里傳的是迭代區(qū)間:_con(first,last)//直接用這個(gè)迭代區(qū)間進(jìn)行初始化的操作{//進(jìn)行建堆的操作/*在構(gòu)建堆（特別是最大堆或最小堆）的過程中，我們之所以從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)開始，是因?yàn)槿~子節(jié)點(diǎn)本身已經(jīng)是一個(gè)有效的堆。下面是具體原因和背后的邏輯：1. **葉子節(jié)點(diǎn)天然滿足堆性質(zhì)**：堆的性質(zhì)要求每個(gè)節(jié)點(diǎn)的值滿足特定條件，比如最大堆要求每個(gè)節(jié)點(diǎn)的值大于或等于其子節(jié)點(diǎn)的值，最小堆要求每個(gè)節(jié)點(diǎn)的值小于或等于其子節(jié)點(diǎn)的值。葉子節(jié)點(diǎn)沒有子節(jié)點(diǎn)，自然滿足堆的定義。所以我們無需對(duì)葉子節(jié)點(diǎn)進(jìn)行任何調(diào)整。2. **從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)開始可以逐層調(diào)整堆**：如果我們從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)開始進(jìn)行“下沉”操作（即調(diào)整該節(jié)點(diǎn)與其子節(jié)點(diǎn)的關(guān)系以滿足堆的性質(zhì)），則可以逐步調(diào)整每一層節(jié)點(diǎn)，從而最終得到一個(gè)完整的堆結(jié)構(gòu)。這個(gè)過程叫做“自底向上”建堆，從倒數(shù)的非葉子節(jié)點(diǎn)開始，避免重復(fù)調(diào)整上層節(jié)點(diǎn)，提高了構(gòu)建效率。3. **提高構(gòu)建效率**：構(gòu)建堆的時(shí)間復(fù)雜度是 \(O(n)\)，而不是 \(O(n \log n)\)，因?yàn)閺牡箶?shù)第一個(gè)非葉子節(jié)點(diǎn)開始向上調(diào)整，比從根節(jié)點(diǎn)開始構(gòu)建效率高得多。倒數(shù)的非葉子節(jié)點(diǎn)數(shù)量較少，而且每個(gè)節(jié)點(diǎn)的調(diào)整次數(shù)隨深度的增加而減少，這種方式在平均情況下只需執(zhí)行有限的調(diào)整操作。4. **構(gòu)建過程的穩(wěn)定性**：自底向上從非葉子節(jié)點(diǎn)開始構(gòu)建可以保證堆的結(jié)構(gòu)穩(wěn)定，不會(huì)因?yàn)樯蠈庸?jié)點(diǎn)的調(diào)整而打亂下層已經(jīng)滿足堆性質(zhì)的節(jié)點(diǎn)。這保證了最終得到的是一個(gè)合法的堆。因此，從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)開始建堆是一種高效、合理的方式。*/for (int i = (_con.size()-1-1)/2; i >=0; i--){//這里的第一個(gè)-1是最后一個(gè)數(shù)的下標(biāo)，第二個(gè)-1配合外面的/2可以找到我們的父親節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)就是倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)了，我們從這個(gè)開始進(jìn)行建堆的操作//我們從這個(gè)位置開始進(jìn)行調(diào)整，不斷的調(diào)整到根節(jié)點(diǎn)//向下調(diào)整算法要求左右子樹都是大堆的，不然是無效的AdjustDown(i);}//我們從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)進(jìn)行建堆的操作可以保證堆的結(jié)構(gòu)正確}//向上調(diào)整算法void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;//算出父親節(jié)點(diǎn)的下標(biāo)位置while (child > 0){//if (_con[parent]<_con[child]  )//父親小于孩子，實(shí)現(xiàn)大堆if (com(  _con[parent],_con[child]))//利用com對(duì)象進(jìn)行比較大小，我們這里的默認(rèn)傳的是greater{//直接利用C++中的swap函數(shù)進(jìn)行交換就行了swap(_con[child], _con[parent]);//將父親節(jié)點(diǎn)和子節(jié)點(diǎn)的值進(jìn)行交換的操作child = parent;//然后我們的孩子節(jié)點(diǎn)就跑到了父親節(jié)點(diǎn)的位置了parent = (parent - 1) / 2;//然后父親節(jié)點(diǎn)的位置就跑到了當(dāng)前父親節(jié)點(diǎn)的父親節(jié)點(diǎn)那里了}else{//如果調(diào)整的過程中孩子節(jié)點(diǎn)的值比父親節(jié)點(diǎn)的值大了，我們就直接跳出循環(huán)就行了，不進(jìn)行操作了break;}    }}void push(const T& x)//在堆中繼續(xù)數(shù)據(jù)的插入的操作{//先插入x_con.push_back(x);//進(jìn)行向上調(diào)整（小堆）AdjustUp(_con.size() - 1);//size-1就是最后一個(gè)數(shù)據(jù)的位置的下標(biāo)，然后我們利用向上調(diào)整算法進(jìn)行調(diào)整的操作}void AdjustDown(int parent){Compare com;size_t child = parent * 2 + 1;//通過給的父親的位置算出左孩子的位置while (child<_con.size()){//我們這里是小堆//假設(shè)，選出左右孩子中小的那個(gè)孩子//if (child + 1 < _con.size() && _con[child]<_con[child + 1]  )//如果右孩子存在的話，并且右孩子大于左孩子的話if (child + 1 < _con.size() && com(_con[child],_con[child + 1]  ))//如果右孩子存在的話，并且右孩子大于左孩子的話{++child;//那么我們就將我們的孩子節(jié)點(diǎn)定位到右孩子的位置那里}if (com(_con[parent],_con[child]  ))//如果當(dāng)前孩子節(jié)點(diǎn)小于父親節(jié)點(diǎn)的話{//我們就將小的節(jié)點(diǎn)往上面進(jìn)行交換swap(_con[child], _con[parent]);parent = child;//然后我們父親節(jié)點(diǎn)就定位到當(dāng)前的孩子節(jié)點(diǎn)了child = parent * 2 + 1;//算出當(dāng)前孩子節(jié)點(diǎn)的孩子節(jié)點(diǎn)}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);//交換堆頂數(shù)據(jù)和最后一個(gè)數(shù)據(jù)_con.pop_back();//然后將最后一個(gè)數(shù)據(jù)進(jìn)行時(shí)刪除的操作就行了//進(jìn)行向下調(diào)整的操作，從根位置開始向下進(jìn)行調(diào)整的操作AdjustDown(0);}bool empty()//判空函數(shù){return _con.empty();}const T& top()//返回堆頂?shù)臄?shù)據(jù){return _con[0];//就是返回根位置的數(shù)據(jù)就行了}size_t size(){return _con.size();}private:Container _con;//存放數(shù)據(jù)的容器};
}

仿函數(shù)的介紹

//仿函數(shù)
//對(duì)象可以像函數(shù)一樣進(jìn)行使用，因?yàn)樗剌d了operator()
template <class T>
struct Less
{bool operator() (const T& x, const T& y)const{return x < y;}
};template <class T>
struct Greater
{bool operator() (const T& x, const T& y)const{return x > y;}
};int main()
{Less<int> lessFunc;cout << lessFunc(1, 2) << endl;cout << lessFunc.operator()(1, 2) << endl;return 0;
}

仿函數(shù)（Functor）是一種在C++和其他編程語(yǔ)言中使用的技術(shù)，它使得對(duì)象可以像函數(shù)一樣被調(diào)用。仿函數(shù)通常通過重載 operator() 操作符來實(shí)現(xiàn)，使得一個(gè)對(duì)象可以像函數(shù)那樣接受參數(shù)并返回結(jié)果。仿函數(shù)的主要優(yōu)勢(shì)在于它將函數(shù)的功能和狀態(tài)封裝到對(duì)象中，使得函數(shù)調(diào)用更加靈活、模塊化和可擴(kuò)展。

仿函數(shù)的基本概念

在C++中，可以通過重載 operator() 操作符來定義一個(gè)仿函數(shù)，使得一個(gè)對(duì)象可以像普通函數(shù)一樣被調(diào)用。仿函數(shù)通常定義為一個(gè)類的成員函數(shù)，允許該類的對(duì)象具備類似函數(shù)的行為。

仿函數(shù)的基本用法

下面是一個(gè)簡(jiǎn)單的仿函數(shù)示例，通過重載 operator() 來實(shí)現(xiàn)一個(gè)加法仿函數(shù)：

#include <iostream>class Adder {
public:int operator()(int a, int b) const {return a + b;}
};int main() {Adder add;int result = add(3, 4); // 對(duì)象像函數(shù)一樣被調(diào)用std::cout << "Result: " << result << std::endl; // 輸出 Result: 7return 0;
}

在這個(gè)例子中，Adder 類重載了 operator() 操作符，使得其對(duì)象 add 可以像一個(gè)函數(shù)一樣通過 add(3, 4) 的形式來調(diào)用，返回結(jié)果 7。

仿函數(shù)的優(yōu)點(diǎn)

1. 靈活性：仿函數(shù)可以攜帶狀態(tài)，可以存儲(chǔ)數(shù)據(jù)和維護(hù)狀態(tài)，適合需要保存計(jì)算狀態(tài)的場(chǎng)景。

2. 性能優(yōu)化：由于仿函數(shù)是類的一部分，它們可以通過內(nèi)聯(lián)函數(shù)進(jìn)行優(yōu)化，從而獲得比普通函數(shù)指針更好的性能。

3. 可定制性：可以根據(jù)需求重載多個(gè) operator()，使得對(duì)象可以接收不同類型和數(shù)量的參數(shù)。

4. 更符合面向?qū)ο笤O(shè)計(jì)：仿函數(shù)可以使用類的其他成員和方法，因此可以實(shí)現(xiàn)更復(fù)雜的操作和邏輯。

常見的仿函數(shù)應(yīng)用

5. STL 算法配合使用：標(biāo)準(zhǔn)庫(kù)中的許多算法，如 std::sort、std::for_each 等都可以接受仿函數(shù)作為參數(shù)。

6. Lambda表達(dá)式的替代：在沒有Lambda表達(dá)式的C++版本中，仿函數(shù)被廣泛用于類似的場(chǎng)景。

7. 策略模式：在設(shè)計(jì)模式中，仿函數(shù)常用于實(shí)現(xiàn)策略模式，用于傳遞可定制的算法。

示例：在STL中使用仿函數(shù)

#include <iostream>
#include <vector>
#include <algorithm>class MultiplyBy {int factor;
public:MultiplyBy(int f) : factor(f) {}int operator()(int value) const {return value * factor;}
};int main() {std::vector<int> values = {1, 2, 3, 4, 5};std::transform(values.begin(), values.end(), values.begin(), MultiplyBy(3));for (int value : values) {std::cout << value << " "; // 輸出 3 6 9 12 15}return 0;
}

在這個(gè)例子中，我們定義了一個(gè) MultiplyBy 仿函數(shù)類，用于將每個(gè)元素乘以一個(gè)特定因子。然后使用 std::transform 將 MultiplyBy(3) 仿函數(shù)應(yīng)用于容器中的每個(gè)元素。

總結(jié)

仿函數(shù)通過重載 operator() 來賦予對(duì)象函數(shù)的能力，使得它們能夠和函數(shù)指針、Lambda表達(dá)式等互相替代并發(fā)揮作用。在C++編程中，仿函數(shù)廣泛應(yīng)用于STL算法和其他需要靈活函數(shù)調(diào)用的場(chǎng)景。

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d);private:int _year;int _month;int _day;
};
//聲明和定義分離
ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}struct DateLess
{bool operator() (const Date* d1, const Date* d2)//傳過來的是兩個(gè)指針，我們希望的是兩個(gè)指針指向的值進(jìn)行比較{//我們直接進(jìn)行解引用進(jìn)行比較的操作return *d1 < *d2;}
};int main()
{// 大堆，需要用戶在自定義類型中提供<的重載kai::priority_queue<Date*,vector<Date*>,DateLess> q1;//優(yōu)先級(jí)隊(duì)列q1.push(new Date{2024,10,23});q1.push(new Date{2024,5,27});q1.push(new Date{2024,11,7});while (!q1.empty())//不斷取值直到棧為空{(diào)cout << *q1.top() << " ";q1.pop();//頭刪替換下個(gè)數(shù)據(jù)}cout << endl;return 0;return 0;
}

題目

155.最小棧

題目

class MinStack
{
public:MinStack(){}void push(int val){_st.push(val);//我們的st這個(gè)棧正常插入數(shù)據(jù)if(_minst.empty()||val<=_minst.top())//如果_minst這個(gè)棧為空的話或者傳過來的val小于等于_minst棧頂?shù)脑氐脑?#xff0c;我們就將數(shù)據(jù)插入到minst中{//如果這個(gè)minst這個(gè)棧是空的話，我們就進(jìn)行數(shù)據(jù)的同步插入，如果這個(gè)插入數(shù)據(jù)小于我們的minst棧頂?shù)臄?shù)據(jù)的話我們就進(jìn)行最小元素的更新操作，如果我們插入的元素等于我們的minst棧頂?shù)脑氐脑?#xff0c;就是等于我們當(dāng)前minst這個(gè)棧棧頂?shù)淖钚≡氐脑?#xff0c;我們也是需要進(jìn)行插入，_minst.push(val);}}void pop(){if(_st.top()==_minst.top()){//如果st這個(gè)棧和minst這個(gè)棧的棧頂元素都相等的話，那么我們都需要進(jìn)行刪除操作的_minst.pop();}_st.pop();//st這個(gè)棧正常進(jìn)行刪除操作，我們需要對(duì)minst這個(gè)棧進(jìn)行一個(gè)判斷操作，如果當(dāng)前兩個(gè)棧的棧頂元素相同的話，那么我們就進(jìn)行minst這個(gè)棧的棧頂元素的刪除操作}int top(){return _st.top();//返回我們的st這個(gè)棧的棧頂元素就行了}int getMin(){//獲取最小值的話我們就將minst這個(gè)棧的棧頂元素進(jìn)行返回就行了，因?yàn)檫@個(gè)棧是進(jìn)行插入元素中最小的元素的更新的return _minst.top();}
private:
//通過兩個(gè)棧我們實(shí)現(xiàn)了找到最小元素的功能了
/*
如果我們的st存入5的話，然后我們的minst記錄當(dāng)前的最小值存放棧中，就是存放5
然后存入4，那么st存入4，minst也存入4，更新最小值
然后我們st存放6，那么我們的minst更新最小值還是4
然后我們放入1的話，minst更新最小值，那么就存入1了
如果我們要pop我們的st棧頂元素的話，那么我們的minst同樣更新最小值，那么最小值就變成上一個(gè)最小值4了這個(gè)MinStack這個(gè)類我們是不需要寫默認(rèn)構(gòu)造的，編譯器默認(rèn)生成一個(gè)無參的構(gòu)造
這里我們的自定義類型st和minst會(huì)自動(dòng)調(diào)用自己的構(gòu)造函數(shù)的，我們是不需要顯示寫的
*/stack<int> _st;stack<int> _minst;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

通過兩個(gè)棧我們實(shí)現(xiàn)了找到最小元素的功能了

如果我們的st存入5的話，然后我們的minst記錄當(dāng)前的最小值存放棧中，就是存放5

然后存入4，那么st存入4，minst也存入4，更新最小值

然后我們st存放6，那么我們的minst更新最小值還是4

然后我們放入1的話，minst更新最小值，那么就存入1了

如果我們要pop我們的st棧頂元素的話，那么我們的minst同樣更新最小值，那么最小值就變成上一個(gè)最小值4了

在我們的st這個(gè)棧在插入的時(shí)候我們的minst不斷進(jìn)行最小元素的更新操作

但是如果我們想：如果在st中插入的好幾個(gè)數(shù)據(jù)都是重復(fù)的話那么我們的minst這個(gè)棧就顯得很麻煩了

那么我們就可以將我們的minst這個(gè)棧改造下

我們可以在minst中對(duì)存入的數(shù)據(jù)進(jìn)行最小值更新的同時(shí)并且進(jìn)行計(jì)數(shù)的操作

JZ31 棧的壓入、彈出序列

題目

• 1.先入棧pushi位置的數(shù)據(jù)

• 2.棧頂數(shù)據(jù)跟出棧popi序列位置數(shù)據(jù)比較，如果匹配則出棧，那么popi++，如果不匹配的話，那么我們繼續(xù)重復(fù)第一個(gè)操作

結(jié)束條件就是直到我們的棧是空的，匹配完了

class Solution {
public:/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布爾型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV){size_t pushi=0,popi=0;stack<int>st;while(pushi<pushV.size()){//我們先往st這個(gè)棧中插入pushv中pushi指向的元素，然后pushi進(jìn)行加加操作st.push(pushV[pushi++]);//這個(gè)是我們?nèi)氲臄?shù)據(jù)//入完數(shù)據(jù)之后我們進(jìn)行一個(gè)比較的操作while(!st.empty()&&popV[popi]==st.top()){//如果這個(gè)st這個(gè)棧不是空的并且我們的popv這個(gè)數(shù)組中i指向的元素和st中的元素是相等的話，那么我們就進(jìn)行出棧操作，進(jìn)了st之后又出就是這個(gè)意思popi++;//換下一個(gè)數(shù)據(jù)進(jìn)行比較st.pop();//刪除當(dāng)前棧的棧頂數(shù)據(jù)}}return st.empty();}
};
/*
兩個(gè)數(shù)組
1 2 3 4 5   pushi
4 3 5 1 2   popi
我們先將1進(jìn)行入棧，然后與popi指向的元素進(jìn)行比較，不匹配，我們繼續(xù)進(jìn)行入棧
入棧了2 3 4
到了4這里，我們的pushi和篇popi指向的數(shù)據(jù)進(jìn)行了匹配了
然后我們刪除了當(dāng)前的這個(gè)4這個(gè)元素，我們將popi++，那么就指向了3
然后我們還是處于循環(huán)中，我們判斷的pushi和popi指向的數(shù)據(jù)是否匹配，然后此時(shí)的棧頂元素是3，匹配上了，到了然后將3刪除了
然后我們此時(shí)的棧頂元素是2，但是我們的popi指向了5，那么我們就出了循環(huán)，繼續(xù)進(jìn)行入棧的操作了，將最后的5入棧了。然后我們匹配上了，將5進(jìn)行刪除了
然后我們?cè)谘h(huán)之中繼續(xù)進(jìn)行判斷是否匹配，我們的此時(shí)棧頂元素是2，但是我們的popi指向的元素是1，然后我們又出循環(huán)了，然后我們進(jìn)行入棧操作，但是我們的pushi已經(jīng)越界了，那么就出了外循環(huán)了，然后我們的循環(huán)就終止了，然后我們判斷我們的棧是不是空的，如果是空的話那么我們就返回了true,如果不是空的話那么就返回false
*/

如果是匹配的話，那么最后棧的空間里面肯定是空的，如果不匹配的話那么肯定是不匹配的

150. 逆波蘭表達(dá)式求值

題目

class Solution {
public:int evalRPN(vector<string>& tokens){stack <int>s;for(auto &str:tokens){//如果是操作符的話if("+"==str||"-"==str||"*"==str||"/"==str){//如果遇到操作符的話我們就從棧里面拿出兩個(gè)數(shù)字進(jìn)行操作符的運(yùn)算操作//我們先拿出來的是右操作符，然后是左操作符int right=s.top();//拿完一個(gè)元素之后我們刪除這個(gè)棧頂元素?fù)Q新的元素當(dāng)棧頂元素s.pop();int left=s.top();s.pop();switch(str[0]){case '+':s.push(left+right);break;case '-':s.push(left-right);break;case '*':s.push(left*right);break;case '/':s.push(left/right);break;}}else//如果是操作數(shù)的話{s.push(stoi(str));//stoi的作用是將字符串轉(zhuǎn)換為整型，然后放到棧里面去}}return s.top();//最后保存的就是我們的結(jié)果}
};

232. 用棧實(shí)現(xiàn)隊(duì)列

題目

class MyQueue
{
private:stack<int> stackIn;stack<int> stackOut;//輔助函數(shù)，將所有元素從stackIn移動(dòng)到stackOutvoid move(){while(!stackIn.empty())//In這個(gè)棧不是空的那么就進(jìn)行循環(huán)操作{stackOut.push(stackIn.top());stackIn.pop();}}public:MyQueue()//構(gòu)造函數(shù)不寫{}//將元素x推入隊(duì)列的末尾 ,這里我們的新元素入棧到in棧里面void push(int x){stackIn.push(x);}//移除隊(duì)列的開頭元素并返回隊(duì)列開頭元素int pop(){if(stackOut.empty())//如果out這個(gè)棧為看空的話，那么我們就將in棧的元素全部移動(dòng)到out的棧里面{move();//直接利用我們上面寫的輔助函數(shù)進(jìn)行操作就行了}int result=stackOut.top();stackOut.pop();return result;//返回out棧的棧頂元素}//返回隊(duì)列開頭的元素int peek(){if(stackOut.empty())//如果out棧是空的話，那么我們將in的元素全部移動(dòng)到out的棧{move();}return stackOut.top();}//如果隊(duì)列是空的，返回true；否則返回falsebool empty()//兩個(gè)棧都是空的話那么這個(gè)隊(duì)列就是空的{return stackIn.empty()&&stackOut.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

225. 用隊(duì)列實(shí)現(xiàn)棧

題目

class MyStack
{
private:queue<int> queue1;queue<int> queue2;public:MyStack(){}//壓入元素到棧頂，后入先出void push(int x){queue2.push(x);//先將元素插入到隊(duì)列2中while(!queue1.empty())//只要隊(duì)列1中有數(shù)據(jù)就進(jìn)行循環(huán)操作{queue2.push(queue1.front());queue1.pop();}//將兩個(gè)隊(duì)列進(jìn)行交換的操作swap(queue1,queue2);}// 移除棧頂元素,棧頂元素在 queue1 的隊(duì)首，因此直接 pop 并返回該元素。int pop(){int topment=queue1.front();queue1.pop();return topment;}int top(){return queue1.front();}bool empty(){return queue1.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/