往期《C++初階》回顧：

/------------ 入門基礎 ------------/
【C++的前世今生】
【命名空間 + 輸入&輸出 + 缺省參數 + 函數重載】
【普通引用 + 常量引用 + 內聯函數 + nullptr】
/------------ 類和對象 ------------/
【類 + 類域 + 訪問限定符 + 對象的大小 + this指針】
【類的六大默認成員函數】
【初始化列表 + 自定義類型轉換 + static成員】
【友元 + 內部類 + 匿名對象】
【經典案例：日期類】
/------------ 內存管理 ------------/
【內存分布 + operator new/delete + 定位new】
/------------ STL ------------/
【泛型編程 + STL簡介】
【auto關鍵字 + 范圍for循環 + 迭代器】
【string類：詳解 + 實現】
【vector容器：詳解 + 實現】
【list容器：詳解 + 實現】

前言：

嗨～(★ω★)/小伙伴們大家好呀！?今天是八月一日，在滿懷熱情迎接八月到來的同時，也讓我們一同慶祝建軍節！🎉🎊

今天要給大家分享的內容是 【stack/queue/priority_queue 容器適配器：詳解 + 實現】（附加：deque 容器介紹） 🎯。哈哈，可能有小伙伴會好奇(⊙o⊙)，這次怎么一下子介紹四個新東西呢？不過大家別擔心(｡???-)?，
因為 stack、queue、priority_queue 雖然名字里帶有 “容器” 二字，但它們其實并不是容器～(?ˉ?ˉ?)，重點要放在后三個字 ——“適配器” 上（這可是 STL 六大組件之一哦）。

---

當然，本篇也會介紹一個新容器 deque，但我們只分析它的原理，不會涉及實現部分。所以這么看來，今天的內容對大家來說，其實比之前的要簡單一些～那我們就一起加油，開始學習吧！?(???｡)?
（💡小提示💡：適配器就像是我們生活中的"轉換插頭"🔌，它們基于已有的容器進行封裝，提供特定的接口，這個概念理解起來會很有趣哦~）

------------標準接口介紹------------

一、棧：stack

標準模板庫中的stack容器適配器是什么樣的呢？

cplusplus網站上關于C++的容器適配器stack的介紹：stack - C++ Reference

C++ 標準模板庫（STL）中關于 stack容器適配器相關知識，主要可以分為以下三個部分：

• 成員函數：stack自身定義的操作接口。
  • 如：構造、判空、獲取大小、訪問 / 操作棧頂等，是直接操作棧的基礎。
• 非成員函數重載：為stack適配的外部函數重載，拓展交互場景。
  • 如：比較、IO 等運算符
• 非成員類特化：針對stack特性，對通用模板類做特化，適配泛型體系 。
  • 如：哈希、仿函數適配等

函數名	接口說明	注意事項
stack()	構造一個空的棧對象	默認使用 deque 作為底層容器
top()	返回棧頂元素的引用	1. 棧為空時調用是未定義行為 2. 有 const 和 非 const 兩個重載版本
push(val)	將元素 val 壓入棧頂	1. 通過拷貝或移動構造元素 2. 可能觸發底層容器擴容
pop()	移除棧頂元素	1. 棧為空時調用是未定義行為 2. 不返回被移除的元素
size()	返回棧中當前元素的數量	返回類型為 size_type（通常為 size_t）
empty()	檢查棧是否為空	返回 bool 類型，空棧時返回 true

1. 棧的基本操作

std::stack::top

// stack::top
#include <iostream>      
#include <stack>          int main()
{std::stack<int> mystack;mystack.push(10);mystack.push(20);mystack.top() -= 5;std::cout << "現在棧頂的元素是：" << mystack.top() << '\n';return 0;
}

std::stack::push

// stack::push/pop
#include <iostream>     
#include <stack>      int main()
{std::stack<int> mystack;for (int i = 0; i < 5; ++i){mystack.push(i);}std::cout << "從棧中彈出元素..." << std::endl;while (!mystack.empty()){std::cout << mystack.top() << ' ';mystack.pop();}std::cout << '\n';return 0;
}

std::stack::pop

2. 查詢棧的狀態

std::stack::size

// stack::size
#include <iostream>      
#include <stack>          int main()
{std::stack<int> myints;std::cout << "初始狀態下的size: " << myints.size() << '\n';for (int i = 0; i < 5; i++){myints.push(i);}std::cout << "入棧元素后的size: " << myints.size() << '\n';myints.pop();std::cout << "出棧元素后的size: " << myints.size() << '\n';return 0;
}

std::stack::empty

// stack::empty
#include <iostream>       // std::cout
#include <stack>          // std::stackint main ()
{std::stack<int> mystack;int sum (0);for (int i=1;i<=10;i++) mystack.push(i);while (!mystack.empty()){sum += mystack.top();mystack.pop();}std::cout << "total: " << sum << '\n';return 0;
}

二、隊列：queue

標準模板庫中的queue容器適配器是什么樣的呢？

cplusplus網站上關于C++的容器適配器queue的介紹：queue - C++ 參考

C++ 標準模板庫（STL）中關于 queue容器適配器相關知識，主要可以分為以下三個部分：

• 成員函數：queue自身定義的操作接口。
  • 如：構造、判空、訪問及操作隊頭 / 隊尾元素等基礎函數。
• 非成員函數重載：為queue適配的外部函數，拓展交互場景。
  • 如：比較、IO 運算符等
• 非成員類特化：針對queue特性，對通用模板類做特化，適配泛型體系 。
  • 如：哈希、仿函數適配等

函數聲明	接口說明	注意事項
queue()	構造一個空的隊列	默認使用 deque 作為底層容器
T& front()	返回隊頭元素的引用 （可修改）	1. 隊列為空時調用是未定義行為 2. 有 const 和 非 const 兩個重載版本
T& back()	返回隊尾元素的引用 （可修改）	同上
void push(const T& val)	在隊尾插入元素 val （拷貝構造）	可能觸發底層容器擴容
void pop()	移除隊頭元素	1. 隊列為空時調用是未定義行為 2. 不返回被移除的元素
size_type size() const	返回隊列中有效元素的數量	返回類型為 size_type（通常為 size_t）
bool empty() const	檢查隊列是否為空	返回 true 表示空隊列 返回 false 表示非空隊列

1. 隊列基本操作

std::queue::front

// queue::front
#include <iostream>     
#include <queue>          int main()
{std::queue<int> myqueue;myqueue.push(77);myqueue.push(16);myqueue.front() -= myqueue.back();    // 77-16=61std::cout << "現在的隊頭元素是：" << myqueue.front() << '\n';return 0;
}

std::queue::back

// queue::back
#include <iostream>       
#include <queue>          int main()
{std::queue<int> myqueue;myqueue.push(12);myqueue.push(75);  myqueue.back() -= myqueue.front();std::cout << "現在的隊尾元素是：" << myqueue.back() << '\n';return 0;
}

std::queue::push

// queue::push/pop
#include <iostream>       
#include <queue>         int main()
{std::queue<int> myqueue;int myint;std::cout << "請輸入一些整數（輸入 0 以結束）：\n";do {std::cin >> myint;myqueue.push(myint);} while (myint);std::cout << "myqueue隊列中的內容是： ";while (!myqueue.empty()){std::cout << ' ' << myqueue.front();myqueue.pop();}std::cout << '\n';return 0;
}

std::queue::pop

2. 查詢隊列狀態

std::queue::size

// queue::size
#include <iostream>       
#include <queue>          int main()
{std::queue<int> myints;std::cout << "初始狀態下的size: " << myints.size() << '\n';for (int i = 0; i < 5; i++){myints.push(i);}std::cout << "入隊元素后的size: " << myints.size() << '\n';myints.pop();std::cout << "出隊元素后的size: " << myints.size() << '\n';return 0;
}

std::queue::empty

// queue::empty
#include <iostream>      
#include <queue>          int main()
{std::queue<int> myqueue;int sum(0);for (int i = 1; i <= 10; i++){myqueue.push(i);}while (!myqueue.empty()){sum += myqueue.front();myqueue.pop();}std::cout << "隊列中的元素之和是: " << sum << '\n';return 0;
}

三、優先隊列：priority_queue

標準模板庫中的priority_queue容器適配器是什么樣的呢？

cplusplus網站上關于C++的容器適配器priority_queue的介紹：priority_queue - C++ Reference

C++ 標準模板庫（STL）中關于 priority_queue容器適配器相關知識，主要可以分為以下三個部分：

• 成員函數：構造 / 查詢 / 元素操作（top/push/pop等）
• 非成員函數重載：適配關系運算、輸入輸出等外部交互
• 非成員類特化：定制比較器（大 / 小頂堆）、選擇底層容器（默認vector）

函數聲明	接口說明	關鍵注意事項
構造函數
priority_queue()	構造空優先隊列	默認大頂堆（less<T>） 底層容器為vector
priority_queue(first, last)	通過迭代器范圍構造優先隊列	自動調用 make_heap 構建初始堆結構
元素訪問
const T& top() const	返回堆頂元素 （優先級最高的元素）	1. 必須保證隊列非空 2. 返回常量引用禁止修改
修改操作
void push(const T& x)	在隊列尾部插入元素 x	觸發 push_heap 調整堆結構 維持優先級規則（保證堆性質）
void pop()	移除堆頂元素 （優先級最高的元素）	1. 必須先檢查 empty() 2. 實際執行 pop_heap + 容器pop_back
容量操作
size_type size() const	返回優先級隊列中有效元素的個數	返回類型為 size_t
bool empty() const	檢查優先隊列是否為空	空隊列返回 true

1. 優先隊列的基本操作

std::priority_queue::top

// priority_queue::top
#include <iostream>       
#include <queue>       //std::priority_queue 注意：“優先隊列”存在于“頭文件queue”中int main()
{std::priority_queue<int> mypq;mypq.push(10);mypq.push(20);mypq.push(15);std::cout << "現在優先隊列中的隊頭的元素是：" << mypq.top() << '\n';return 0;
}

std::priority_queue::push

// priority_queue::push/pop
#include <iostream>       
#include <queue>          int main()
{std::priority_queue<int> mypq;mypq.push(30);mypq.push(100);mypq.push(25);mypq.push(40);std::cout << "從優先隊列中出隊元素..." << std::endl;while (!mypq.empty()){std::cout << mypq.top() << " ";mypq.pop();}std::cout << '\n';return 0;
}

std::priority_queue::pop

2. 查詢優先隊列的狀態

std::priority_queue::size

// priority_queue::size
#include <iostream>       
#include <queue>        int main()
{std::priority_queue<int> myints;std::cout << "初始狀態下的size: " << myints.size() << '\n';for (int i = 0; i < 5; i++){myints.push(i);}std::cout << "入隊元素后的size: " << myints.size() << '\n';myints.pop();std::cout << "出隊元素后的size: " << myints.size() << '\n';return 0;
}

std::priority_queue::empty

// priority_queue::empty
#include <iostream>       
#include <queue>          int main()
{std::priority_queue<int> mypq;int sum(0);for (int i = 1; i <= 10; i++){mypq.push(i);}while (!mypq.empty()){sum += mypq.top();mypq.pop();}std::cout << "隊列中的元素之和是:" << sum << '\n';return 0;
}

------------------------

優先隊列怎么顯示定義為“小頂堆”？

1. 元素類型是“內置類型”

現在請大家回想一下，前面這些接口函數的使用案例：

1. top函數：我們依次向優先隊列中添加了元素：10，20，15，最后通過 top 獲取到的隊頭元素是 20
2. push/pop函數：我們依次向優先隊列中添加了元素：30，100，25，40，最后執行 pop 函數依次出隊，得到的元素順序是 100、40、30、25

看到這些案例，我相信你已經明白了：

代碼std::priority_queue<int> mypq;定義的優先隊列，遵循的優先級規則是：元素值越大，優先級越高，這樣的優先隊列本質上就是一個 大頂堆

---

溫馨提示：這里有一個很大的誤區！！！

有一些小伙伴此時應該會有一點困惑，就是：

使用默認方式定義優先隊列是大頂堆 —> 構造大頂堆時堆排序是升序 —> 咦但是上面出隊的元素分明是降序的啊！！！

哈哈😄，這位小伙伴說的每句話的都是對的，但是得出的結論確實錯的。

原因是：

• 上面的降序是依次出隊的元素的順序

• 構造大頂堆時堆排序是升序，指的是待排序數組中的元素從非升序變為了升序，兩者并不是一件事情。

---

回歸正題，優先隊列可以定義為“小頂堆”嗎？那我們要怎么將優先隊列定義為“小頂堆”呢？

• 在 C++ 中，若要顯式將 priority_queue 定義為小頂堆（元素值越小，優先級越高），需通過模板參數指定底層容器和比較器

具體點說就是顯式指定：

• 使用默認的 vector底層容器
• 使用標準庫<functional>提供的 greater<T> 比較器

---

注：上面博主沒有寫錯哦，就是要顯示指定上面的兩種的東西，可能你會有疑問底層容器使用的就是默認的vector啦，我還顯示指定個蛋啊！

哈哈O(∩_∩)O，這是因為 priority_queue 的模板參數列表要求：

當你指定第三個參數（比較器）時，必須同時指定第二個參數（底層容器）

• 若不指定比較器：可省略所有模板參數，默認使用 vector 和 less
• 若指定比較器：必須顯式指定底層容器，否則會導致編譯錯誤

---

總結：如果你想讓優先隊列定義為“小頂堆”，可以使用下面的定義方法：

• std::priority_queue<T, std::vector<T>, std::greater<T>>
• std::priority_queue<T, std::deque<T>, std::greater<T>>

---

代碼案例：使用優先隊列定義“小頂堆”（存儲內置類型）

#include <iostream>
#include <vector>
#include <queue>
#include <functional>   // 提供greater比較器，用于構建小頂堆
using namespace std;int main()
{/*------------------測試1：優先隊列創建的“大頂堆”------------------*/cout << "---------測試1：優先隊列創建的“大頂堆”---------" << endl;/*-------------第一步：創建“大頂堆”的一個優先隊列-------------*///1.先創建一個vector容器（目的：為優先隊列進行賦值）vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };//2.使用默認的方式創建一個優先隊列（不指定：“底層容器”+“比較器”）priority_queue<int> q1;//3.為優先隊列進行賦值for (auto& it : v) //注：使用最原始逐個元素的賦值{q1.push(it);}/*-------------第二步：輸出優先隊列的隊頭元素驗證“大頂堆”-------------*/cout << "優先的隊列的隊頭元素是：" << q1.top() << endl;/* 注意事項：*   默認情況下，priority_queue使用vector作為底層容器，less<int>作為比較器*   這會構建一個"大頂堆"（即：堆頂元素為最大值）*   創建大頂堆：優先級最高的元素是最大值***//*------------------測試2：優先隊列創建的“小頂堆”------------------*/cout << "---------測試1：優先隊列創建的“小頂堆”---------" << endl;/*-------------第一步：創建“小頂堆”的一個優先隊列-------------*//*---------方式一：迭代器范圍初始化---------*///priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());  //內部會自動構建小頂堆/*---------方式一：逐個插入方式初始化---------*/priority_queue<int, vector<int>, greater<int>> q2;for (auto& it : v){q2.push(it);}/*-------------第二步：輸出優先隊列的隊頭元素驗證“小頂堆”-------------*/cout << "優先的隊列的隊頭元素是：" << q2.top() << endl;/* 注意事項：*   通過顯式指定模板參數：*               元素類型：int*               底層容器：vector<int>*               比較器：greater<int>（表示"較小的元素優先級更高"）*   這會構建一個"小頂堆"（即：堆頂元素為最小值）*   創建大頂堆：優先級最高的元素是最小值***/return 0;
}

2. 元素類型是“自定義類型”

在 priority_queue 中存儲自定義類型的數據時，用戶需要在自定義類型中重載 < 或 > 運算符，以明確元素的優先級規則。

---

核心邏輯：

priority_queue（優先級隊列）本質是堆結構，需要根據元素的優先級來調整堆的順序。

• 對于自定義類型，編譯器無法默認判斷元素的大小關系
• 因此必須通過 運算符重載 或 自定義比較器 告訴編譯器如何比較元素的優先級

---

常見場景：

1. 使用默認比較器（大頂堆）

• 需求：希望自定義類型的對象形成大頂堆（優先級高的元素為 “較大” 的對象）
• 實現：重載 < 運算符，定義 “當前對象小于另一個對象” 的邏輯

2. 顯式指定小頂堆（或自定義比較邏輯）

• 需求：希望自定義類型的對象形成小頂堆（優先級高的元素為 “較小” 的對象），或使用其他比較規則（如：按屬性倒序）
• 實現：重載 > 運算符，并搭配 std::greater<自定義類型> 比較器

---

代碼案例：使用優先隊列定義“小頂堆”（存儲內置類型）

#include <iostream>
#include <vector>
#include <queue>
#include <functional>   // 提供greater比較器，用于構建小頂堆
using namespace std;/*-------------------------定義日期類-------------------------*/
class Date
{
public:/*-------------第一部分：定義友元函數-------------*///1.實現：“<<運算符重載函數”friend ostream& operator<<(ostream& out, const Date& d) //重載輸出流運算符，支持直接 cout << Date 對象{out << d._year << "-" << d._month << "-" << d._day;return out;}/*-------------第二部分：定義成員函數-------------*///1.實現：“全缺省構造函數”// 構造函數：初始化日期對象，默認值為1900-01-01Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}//2.實現：“<運算符重載函數”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); //返回 true 表示當前對象優先級低于參數對象}//3.實現：“>運算符重載函數”bool operator>(const Date& d) const  //重載 > 運算符：定義"大于"邏輯，用于小頂堆的 greater<Date> 比較器{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day); //返回 true 表示當前對象優先級高于參數對象}private:int _year;int _month;int _day;
};/*-------------------------測試 priority_queue 對自定義類型的使用-------------------------*/
int main()
{/*------------------第一部分：大頂堆示例------------------*//* 注意事項：*     默認使用 vector<Date> 作為底層容器，less<Date> 作為比較器*     依賴 Date::operator< 實現大頂堆（日期大的優先級高）***///1.使用默認的方式定義優先隊列 ---> 大頂堆priority_queue<Date> q1;//2.為優先隊列賦值 ---> 插入三個日期，按 operator< 排序后，最大的日期在堆頂q1.push(Date(2025, 5, 29));q1.push(Date(2025, 5, 28));q1.push(Date(2025, 5, 30));//3.輸出優先隊列的隊頭的元素 ---> 輸出堆頂元素（最大日期）cout << q1.top() << endl;  /*------------------第二部分：小頂堆示例------------------*//* 注意事項：*     顯式指定底層容器為 vector<Date>，比較器為 greater<Date>*     依賴 Date::operator> 實現小頂堆（日期小的優先級高）***///2.顯示指定“底層容器 + 比較器”定義優先隊列 ---> 小頂堆priority_queue<Date, vector<Date>, greater<Date>> q2;//3.為優先隊列賦值 ---> 插入相同的三個日期，按 operator> 排序后，最小的日期在堆頂q2.push(Date(2025, 5, 29));q2.push(Date(2025, 5, 28));q2.push(Date(2025, 5, 30));//3.輸出優先隊列的隊頭的元素 ---> 輸出堆頂元素（最小日期）cout << q2.top() << endl;  return 0;
}

------------模擬實現展示------------

頭文件：Stack.h

#pragma once//任務1：包含需要使用的頭文件
#include <deque>  // 包含雙端隊列容器，用于作為stack的底層實現//任務2：定義自定義命名空間mySpace //任務2.1：實現：“stack類模板”namespace mySpace
{/** 模板類stack：實現適配器模式的棧容器** 特點：默認使用deque作為底層容器，支持自定義容器類型* 模板參數：*		T - 棧中存儲的元素類型*		Container - 底層容器類型，默認為std::deque<T>*/template<class T, class Container = std::deque<T>>  //注意：這里的也傳vector<T>class stack{private:Container _con;  //支持自定義容器類型，需滿足容器適配器的接口要求public:/*---------------------------成員函數---------------------------*//*------------核心接口：棧的基本操作------------*///1.實現：“入棧操作”void push(const T& x){_con.push_back(x); //調用底層容器的push_back()方法}//2.實現：“出棧操作”void pop(){_con.pop_back();  //調用底層容器的pop_back()方法}//3.實現：“獲取棧頂元素的操作”const T& top()const{return _con.back(); //調用底層容器的back()方法}/*------------輔助接口：------------*///4.實現：“獲取棧中的元素的個數的操作”size_t size()const{return _con.size(); //調用底層容器的size()方法}//5.實現：“判斷棧是否為空的操作”bool empty()const{return _con.empty(); //調用底層容器的empty()方法}};// ====================================================查詢棧狀態=============// 設計說明：// 1. 適配器模式：stack 不直接實現數據結構，而是通過封裝其他容器（如：deque、vector）實現功能// 2. 容器選擇：默認使用 deque 的原因：//    - deque 在尾部操作（push_back/pop_back）均為 O(1) 時間復雜度//    - deque 無需預分配額外空間（相比 vector 的擴容機制），內存使用更靈活// 3. 自定義容器：用戶可通過模板參數指定其他容器，例如：//    stack<int, vector<int>> st;  // 使用 vector 作為底層容器（需確保容器支持 back() 和 pop_back()）// 4. 容器要求：底層容器必須提供以下接口：//    - push_back(const T&)：尾部插入元素//    - pop_back()：尾部刪除元素//    - back() const：獲取尾部元素（棧頂）//    - size() const：獲取元素個數//    - empty() const：判斷是否為空// =================================================================
}

頭文件：Queue.h

#pragma once//任務1：包含需要使用的頭文件
#include <deque>  //包含雙端隊列容器，用于作為queue的底層實現//任務2：定義自定義命名空間mySpace //任務2.1：實現：“quue類模板”namespace mySpace
{template<class T,class Container = std::deque<T>>class queue{private:Container _con;  //存儲隊列元素的底層容器，默認為 deque<T>public:/*---------------------------成員函數---------------------------*//*------------核心接口：隊列的基本操作------------*///1.實現：“入隊操作”void push(const T& x){_con.push_back(x);}//2.實現：“出隊操作”void pop(){_con.pop_back();}//3.實現：“獲取隊頭元素的操作”const T& front()const{return _con.front();}//4.實現：“獲取隊尾元素的操作”const T& back()const{return _con.back();}/*------------輔助接口：查詢隊列狀態------------*///5.實現：“獲取隊列中元素的數量的操作”size_t size()const{return _con.size();}//6.實現：“判斷隊列是否為空的操作”bool empty()const{return _con.empty();}};// =================================================================// 設計說明：// 1. 適配器模式：queue 不直接實現數據結構，而是通過封裝其他容器（如：deque、list）實現功能// 2. 容器選擇：默認使用 deque 的原因：//    - deque 在頭部和尾部操作均為 O(1) 時間復雜度//    - deque 相比 list 內存更緊湊，訪問效率更高// 3. 自定義容器：用戶可通過模板參數指定其他容器，例如：//    queue<int, list<int>> q;  // 使用 list 作為底層容器（需確保容器支持 front() 和 pop_front()）// =================================================================
}

頭文件：PriorityQueue.h

#pragma once//任務1：包含需要使用的頭文件
#include <vector>  //包含vector容器，作為優先隊列的默認底層存儲結構 //任務2：實現比較仿函數
//1.實現：“小于”（用于大堆構建，默認情況）
template<class T>
class Less
{
public://重載()運算符：判斷x是否小于y（用于大堆的向上/向下調整）bool operator()(const T& x, const T& y){return x < y; //大堆中，若父節點小于子節點則需要調整}
};//2.實現：“大于”（用于小堆構建）
template<class T>
class Greater
{
public://重載()運算符：判斷x是否大于y（用于小堆的向上/向下調整）bool operator()(const T& x, const T& y){return x > y; //小堆中，若父節點大于子節點則需要調整}
};//任務3：定義自定義命名空間mySpace //任務2.1：實現：“priority_queue類模板”namespace mySpace
{//class T：堆中存儲的元素類型//class Container：底層容器類型（需支持隨機訪問和尾部操作）//class Compare：比較仿函數（默認大堆：Less<T>）template<class T, class Container = std::vector<T>, class Compare = Greater<T> >class priority_queue{private:Container _con;  //底層容器：存儲堆元素，需支持隨機訪問和尾部操作public:/*------------核心算法：向上/相下 調整算法------------*/////1.實現：“向上調整算法”工具函數//void AdjustUp(HPSortType* a, int child)//{//	//1.計算出父節點在數組中的下標（我們有孩子 ---> 得到雙親）//	int parent = child - 1 >> 1;//	//2.接下來不斷的進行向上調整，何時調整結束？ ---> 回答：1.當孩子已經調整成根節點時 2.當孩子不滿小堆的性質時（這里我們模擬小根堆）//	while (child > 0)//	{//		//3.使用if-else語句進行小根堆的條件檢查（小根堆：誰小誰當爹）//		if (a[child] >= a[parent]) return;//		else//		{//			//4.1：交換孩子節點和雙親節點的值//			Swap(&a[child], &a[parent]);//			//4.2：更新孩子的索引 ---> 因為我們要為孩子找到一個合適的位置//			child = parent;//			//4.3：求出現在孩子的雙親節點的索引//			parent = child - 1 >> 1;//		}//	}//}////2.實現：“向下調整算法”工具函數//void AdjustDown(HPSortType* a, int parent, int n)//{//	//1.計算出孩子節點在數組中的下標（我們有雙親節點 --->  得到“值最小的”孩子）//	//這里和向上調整有點不一樣：找雙親節點就只有一個，但是找孩子節點有兩個，要找哪一個呢？---> 找值最小的孩子//	//注：這里使用假設法：假設雙親的左孩子是最小的孩子//	int minchild = (parent << 1) + 1;//	//2.接下來不斷地進行向下調整，何時調整結束 --->  1.當孩子節點的索引已經大于數組的容量，即：孩子不存在時 2.當孩子不滿足小根堆的條件檢查時//	while (minchild < n)//	{//		//3.調整出minchild代表是最小的孩子//		if (minchild + 1 < n && a[minchild + 1] < a[minchild])//		{//			minchild++; //切換到右孩子//		}//		//3.使用if-else語句進行小根堆的條件檢查//		if (a[minchild] >= a[parent]) return;//		else//		{//			//4.1：交換孩子節點和雙親節點的值//			Swap(&a[minchild], &a[parent]);//			//4.1：更新雙親節點的索引//			parent = minchild;//			//4.2：求出現在雙親節點的孩子節點的索引//			minchild = (parent << 1) + 1;//		}//	}//}//1.實現：“向上調整算法”工具函數void AdjustUp(int child)  //注意1：void AdjustUp(HPSortType* a, int child) ---> void AdjustUp(int child){//1.Compare com;  //注意2：創建仿函數對象  //2.int parent = (child - 1) / 2;//3.while (child > 0){//4.//if (com(_con[child], _con[parent])) return;  //非常注意3：if (a[child] >= a[parent]) ---> if (com(_con[parent], _con[child])))if (com(_con[parent], _con[child])) return; else{//5.1：std::swap(_con[child], _con[parent]); //注意4：Swap(&a[child], &a[parent]); ---> std::swap(_con[child], _con[parent]);//5.2：child = parent;//5.3：parent = (child - 1) / 2;}}}//2.實現：“向下調整算法”工具函數void AdjustDown(int parent) //注意1：void AdjustDown(HPSortType* a, int parent, int n) ---> void AdjustDown(int parent){//1.Compare com; //注意2：創建仿函數對象  //2.int minchild = parent * 2 + 1;//3.while (minchild < _con.size()) //注意3：while (minchild < n) ---> while (minchild < _con.size()){//4.if (minchild + 1 < _con.size() && com(_con[minchild + 1] , _con[minchild])) {//注意4：if (minchild + 1 < n && a[minchild + 1] < a[minchild]) ---> if (minchild + 1 < _con.size() && com(_con[minchild + 1] , _con[minchild])) minchild++; }//5.//if (com(_con[minchild] , _con[parent])) return; //非常注意5：if (a[minchild] >= a[parent]) return; ---> if (com(_con[parent], _con[minchild]))if (com(_con[parent], _con[minchild])) return;else{//5.1：std::swap(_con[minchild], _con[parent]); //注意6：Swap(&a[minchild], &a[parent]); ---> std::swap(_con[minchild], _con[parent]);//5.1：parent = minchild;//5.2：minchild = parent * 2 + 1;}}}/*------------核心接口：優先隊列的基本操作------------*///1.實現“優先隊列的入隊操作”void push(const T& x){//1.先將元素添加到容器的尾部_con.push_back(x);//2.再從新元素位置開始向上調整堆AdjustUp(_con.size() - 1);}//2.實現：“優先隊列的出隊操作”void pop(){//1.先判斷優先隊列是否為空if (empty()) return;//2.然后讓堆頂元素和最后一個元素進行交換std::swap(_con[0], _con[_con.size() - 1]);//3.接著刪除尾部元素_con.pop_back();//4.最后從堆頂開始向下調整堆AdjustDown(0);}//3.實現：“獲取堆頂元素的操作”const T& top(){return _con[0];}/*------------輔助接口：查詢優先隊列狀態------------*///1.實現：“獲取優先隊列中的元素的數量的操作”size_t size()const{return _con.size();}//2.實現：“判斷優先隊列是否為空的操作”bool empty()const{return _con.empty();}};// =================================================================// 設計說明：// 1. 適配器模式：priority_queue 不直接實現堆結構，而是通過封裝容器（如：vector）實現功能// 2. 容器選擇：默認使用 vector 的原因：//    - vector 支持隨機訪問（通過下標快速定位父子節點）//    - push_back()/pop_back() 效率高（均攤 O(1)，配合堆調整實現整體高效）// 3. 比較策略：通過仿函數 Compare 靈活切換大堆/小堆：//    - 默認 Compare=Less<T> 實現大堆（堆頂為最大值）//    - 若需小堆，傳入 Compare=Greater<T>（堆頂為最小值）// 4. 自定義容器：用戶可指定其他支持隨機訪問的容器，例如：//    priority_queue<int, deque<int>, Greater<int>> pq;  // 使用 deque 作為底層容器// 5. 容器要求：底層容器必須提供以下接口：//    - operator[]：隨機訪問元素（用于堆節點定位）//    - push_back(const T&)：尾部插入元素//    - pop_back()：尾部刪除元素//    - size() const：獲取元素個數// =================================================================
}

測試文件：Test.cpp

#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>#include"Stack.h"         //自定義棧容器（適配器模式）
#include"Queue.h"         //自定義隊列容器（適配器模式）
#include"PriorityQueue.h" //自定義優先隊列（堆結構）using namespace std;/*===================== 測試棧和隊列的基本使用 =====================*/
void test01()
{/*------------------------第一部分：測試棧的功能------------------------*/cout << "------------測試棧的功能------------" << endl;/*------------第一步：創建棧------------*///1.使用vector作為底層容器（默認容器為deque，但顯式指定vector測試）//mySpace::stack<int, vector<int>> stk;//使用list作為底層容器mySpace::stack<int, list<int>> stk; //注意：也可使用list作為底層容器（需確保容器支持push_back/pop_back/back）/*------------第二步：測試“入棧操作”------------*/stk.push(1);stk.push(2);stk.push(3);stk.push(4);/*------------第三步：測試“獲取棧頂元素的操作”------------*/cout << "入棧之后,此時棧頂的元素是：" << stk.top() << endl;/*------------第四步：測試“出棧操作”------------*/stk.pop();cout << "出棧之后,此時棧頂的元素是：" << stk.top() << endl;/*------------------------第一部分：測試隊列的功能------------------------*/cout << "------------測試隊列的功能------------" << endl;/*------------第一步：創建隊列------------*///1.使用deque作為底層的容器（默認使用deque作為底層容器）mySpace::queue<int> que;//2.顯式指定list作為底層的容器（需支持push_back/pop_front/front/back）//mySpace::queue<int, list<int>> que;/*------------第二步：測試“入隊操作”------------*/que.push(1);que.push(2);que.push(3);que.push(4);cout << "入隊之后,此時隊頭的元素是："<< que.front() << endl;cout << "入隊之后,此時隊尾的元素是："<< que.back() << endl;// 出隊：移除隊頭元素1que.pop();cout << "出隊之后,此時隊頭的元素是：" << que.front() << endl;cout << "出隊之后,此時隊尾的元素是：" << que.back() << endl;
}/*===================== 測試優先隊列（堆）的功能 =====================*/void test02()
{cout << "------------測試優先隊列（堆）的功能------------" << endl;/*------------第一步：創建優先隊列------------*///1.不指定仿函數，使用默認的仿函數Less<int>（大堆，堆頂為最大值）//mySpace::priority_queue<int> pqu;//2.指定仿函數Greater<int>（小堆，堆頂為最小值）mySpace::priority_queue<int, vector<int>, Greater<int>> pqu;  //實例化小堆：通過Greater仿函數指定“x > y”為真時交換（堆頂為最小值）/*------------第二步：測試“入堆操作”------------*/pqu.push(4);pqu.push(1);pqu.push(5);pqu.push(7);pqu.push(9);/*------------第四步：測試“出堆操作”------------*/while (!pqu.empty()) //按優先級順序輸出元素（小堆順序：1 4 5 7 9）{cout << pqu.top() << " "; //輸出堆頂元素pqu.pop();                //移除堆頂元素并調整堆}cout << endl; 
}int main()
{test01();test02();return 0;
}

運行結果：

------------代碼片段剖析------------

上面的代碼邏輯相對之前容器的邏輯較為簡單，但容器適配器 priority_queue 的實現相對會復雜一點，原因在于它結合了 比較器和堆結構

• 堆結構引入了向上調整算法和向下調整算法，而由于需要適配仿函數（靈活切換大堆 / 小堆的比較規則），這兩種算法的邏輯需要與仿函數聯動。

因此：下面的代碼片段都是講解這兩個調整算法為什么要進行那樣的修改的

（注：關于 if 語句中如何通過仿函數調整比較邏輯，可參考下面關于仿函數的專門講解）

片段一：AdjustUp和AdjustDown方法的參數為什么進行了簡化？

//1.實現：“向上調整算法”工具函數
void AdjustUp(int child)  //注意1：void AdjustUp(HPSortType* a, int child) ---> void AdjustUp(int child)//2.實現：“向下調整算法”工具函數
void AdjustDown(int parent) //注意1：void AdjustDown(HPSortType* a, int parent, int n) ---> void AdjustDown(int parent)

在自定義的 priority_queue 類模板中，AdjustUp 和 AdjustDown 方法的參數之所以從原始的數組指針和長度簡化為 child 或 parent 下標

是因為：類模板內部已經封裝了底層容器（如：vector），無需再通過外部傳入數據數組和長度

---

一、原始參數設計的問題（注釋中的舊版本）

主要問題：

• 這種設計需要用戶手動傳入數組和長度，耦合性高且不通用。
• 當 priority_queue 封裝了底層容器（如：vector）后，這些數據應屬于類的內部狀態，無需外部暴露。

---

二、修改后參數簡化的原因（當前版本）

核心改進：

• 封裝底層容器：
  • 類模板中定義了成員變量 Container _con（如：vector<T>），用于存儲堆元素。
  • AdjustUp 和 AdjustDown 直接通過 _con 訪問元素，無需外部傳入數組指針。
• 自動獲取容器長度：
  • 通過 _con.size() 獲取當前元素個數，替代舊版本的 n 參數，避免手動傳遞長度可能導致的越界問題。
• 依賴類模板參數：
  • 比較邏輯通過類模板參數 Compare 實現（仿函數 com），而非硬編碼比較規則，提升了代碼的靈活性（可適配大堆 / 小堆）。

片段二：Swap(&a[child], &a[parent])的傳參為什么發生了改變？

//5.1：
std::swap(_con[child], _con[parent]); //注意4：Swap(&a[child], &a[parent]); ---> std::swap(_con[child], _con[parent]);//5.1：
std::swap(_con[minchild], _con[parent]); //注意6：Swap(&a[minchild], &a[parent]); ---> std::swap(_con[minchild], _con[parent]);

在代碼中使用 std::swap(_con[child], _con[parent]) 替換原始的 Swap(&a[child], &a[parent])

主要是因為：底層容器的封裝方式改變 和 C++ 標準庫的易用性。

---

一、原始代碼的問題（注釋中的舊版本）

• a 是外部傳入的數組指針（如：HPSortType* a），需要通過 &a[child] 獲取元素地址，再傳遞給自定義的 Swap 函數進行交換。
• 這種方式依賴原始數組的內存布局，且 Swap 函數可能需要手動實現（如：通過指針交換值），耦合性高且不通用。

---

二、修改后使用 std::swap 的原因（當前版本）

• 自定義的 priority_queue 類模板中，元素存儲在成員變量 _con（底層容器，如：vector<T>）中。
• _con[child] 和 _con[parent] 直接通過容器的 operator[] 接口訪問元素（類似數組下標訪問），無需通過指針操作原始內存。

------------核心問題深究------------

一、仿函數

1. 什么是仿函數？

仿函數（Functor）：也稱為函數對象（Function Object），是一種在 C++ 中通過類或結構體實現的可調用實體

• 仿函數的核心特點是 重載了 operator() 運算符，使得類的對象可以像普通函數一樣被調用。
• 仿函數是 C++ 中 “以類模擬函數” 的重要機制，這種機制結合了面向對象的封裝性和函數的靈活性，在 STL和算法中有著廣泛應用。

---

仿函數的核心特點：

1. 重載 operator()

• 通過在類中定義 operator() 運算符，使得該類的對象可以像函數一樣被調用：

  class Add 
  {
  public:int operator()(int a, int b) // 重載()運算符{  return a + b;}
  };
  

• 使用時：

  Add add;  				 //創建仿函數對象
  int result = add(3, 5);  //像函數一樣調用，結果為8
  

---

2. 可攜帶狀態

• 仿函數可以像普通類一樣擁有成員變量，用于存儲狀態或參數，這使得它比普通函數更靈活。

class Multiply 
{
private:int factor;     // 成員變量存儲狀態
public:Multiply(int f) // 構造函數初始化狀態:factor(f) {}  int operator()(int x) {return x * factor;}
};Multiply mul(3); // 創建一個乘以3的仿函數對象
cout << mul(4);  // 輸出12（攜帶狀態factor=3）

2. 仿函數有什么用途？

1. STL算法中的比較器和謂詞

• 比較器：通過仿函數指定排序規則（如：升序 / 降序）

  #include <algorithm>
  #include <vector>
  using namespace std;class Greater 
  {
  public:bool operator()(int a, int b) const  // 降序比較{return a > b;  }
  };int main() 
  {vector<int> nums = {3, 1, 4, 2};sort(nums.begin(), nums.end(), Greater());  // 使用仿函數指定降序// 排序結果：4 3 2 1return 0;
  }
  

• 謂詞：用于篩選元素（如：find_if、remove_if）

  class IsEven 
  {
  public:bool operator()(int x) const {return x % 2 == 0;  // 判斷是否為偶數}
  };vector<int>::iterator it = find_if(nums.begin(), nums.end(), IsEven());
  

---

2. 自定義算法邏輯

• 在自定義算法中，通過仿函數將邏輯抽象出來，提高代碼復用性。

  template<class Compare>
  void BubbleSort(int* a, int n, Compare com) 
  {// 使用com(a[j], a[j - 1])進行比較，實現通用排序if (com(a[j], a[j - 1])) // 根據仿函數的邏輯決定是否交換{  swap(a[j-1], a[j]);}
  }
  

---

3. 替代函數指針

• 相比函數指針，仿函數更安全（類型檢查嚴格）、更靈活（可攜帶狀態），且性能接近函數調用（編譯器易優化）

3. 仿函數與普通函數的區別有哪些？

特性	普通函數	仿函數
調用方式	直接調用（如：func(a, b)）	通過對象調用（如：obj(a, b)）
狀態存儲	無法存儲狀態	可通過成員變量存儲狀態
類型安全	弱（依賴函數指針類型匹配）	強（編譯期模板類型檢查）
可復用性	低（邏輯固定）	高（通過模板和繼承擴展）
重載	通過不同參數列表	通過多個operator()實現
性能	取決于編譯器	容易

4. 怎么讓冒泡排序既可以升序又可以降序排序？

想必大家對冒泡排序已經相當了解了。

假如我們想要對一批數據使用冒泡排序同時實現升序和降序排序，該怎么做呢？
可能有些小伙伴會說：“這很簡單的啦 ~，把原來的冒泡排序代碼復制一份，修改其中的比較邏輯就行啦 ~！”

---

哈哈，小伙伴的回答簡單粗暴沒毛病，但是呢會導致重復代碼冗余，違背了DRY（Don’t Repeat Yourself）原則

為解決這個問題，我們可以引入 仿函數（Functor） 來實現比較邏輯的抽象，避免硬編碼比較規則，從而提升代碼的靈活性和可維護性。

代碼案例：使用仿函數使冒泡排序同時實現升序和降序排序

#include <iostream>
using namespace std;/*===================== 仿函數（函數對象）的原理與使用 =====================*/
//說明：仿函數是重載了operator()的類，其對象可像函數一樣調用
//應用場景：STL算法（如：sort、priority_queue）中的比較器、謂詞等/*---------------------------第一部分：實現比較仿函數（類模板）---------------------------*/
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y) const  //注意：加const提高通用性{return x < y; //返回true時表示x應排在y前面（升序）}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y) const{return x > y; //返回true時表示x應排在y后面（降序）}
};/*---------------------------第二部分：實現冒泡排序（函數模板）---------------------------*/
template<class Compare>
void BubbleSort(int* a, int n, Compare com)
{//1.外層的循環控制 ---> 記錄需要進行交換的數字的個數[“也可理解為冒泡的總的趟數”]（解釋：n個數字只需要對n-1個數字進行排序即可實現n個數字的有序）for (int i = 1; i <= n - 1; i++){//2.內層的循環控制 ---> 記錄對每個數字進行排序需要交換的次數[“也可以理解為每趟冒泡需要交換的次數”]（注意：每趟冒泡需要交換的次數是不同的）//對冒泡排序進行優化：int flag = 1;for (int j = 1; j <= n - i; j++){//核心：前面的元素的值大進行交換//if (a[j - 1] > a[j])//if (com(a[j - 1], a[j]))if (com(a[j], a[j - 1])){swap(a[j - 1], a[j]);flag = 0;}/*下面的注釋的內容很重要！！！注意：大家很明顯可以看出來這個“冒泡排序”是我直接復制在數據結構初階中講解“八大排序”時冒泡排序的代碼哈哈，如果你也是像我一樣直接進行的復制后，僅僅將“if (a[j - 1] > a[j])”修改成“if (com(a[j - 1], a[j]))”的話，你運行出來的結果是：使用“仿函數Less<int> lessFunc”進行升序排序：9 8 7 6 5 4 3 2 1使用“仿函數Greater<int>”進行降序排序：1 2 3 4 5 6 7 8 9使用“匿名對象Less<int>()”進行升序排序：9 8 7 6 5 4 3 2 1使用“匿名對象Greater<int>()”進行降序排序：1 2 3 4 5 6 7 8 9我們發現我們期望的“升序/降序”和實際的“升序/降序”正好相反也就是說：為了適應仿函數，使用Less<int>排升序，使用Greater<int>排降序BubbleSort中涉及比較的的部分，如：“if (a[j - 1] > a[j])”除了要將其修改為“if (com(a[j - 1], a[j]))”還要注意：com(參數1,參數2)需要滿足“參數1<參數2” 舉個例子：就是上面的if條件判斷是：“if (a[j - 1] > a[j])”，為了使用仿函數，也就是說所有的條件判斷我只能使用“<”所以我就將上面的if條件判斷等價的修改成了“if (a[j] < a[j - 1])”接著就可以直接將“if語句”轉換為“仿函數對象的調用”“if (a[j] < a[j - 1])”----> “com (a[j] , a[j - 1])”*/}if (flag) break; //如果某一趟的冒沒有進行交換，說明當前數組中的元素已經有序了，則直接退出}
}int main()
{/*------------第一部分：創建仿函數對象------------*/Less<int> lessFunc;  //實例化仿函數對象Greater<int> greaterFunc;/*------------第二部分：展示兩種調用仿函數的方式------------*///第一種：對象()cout << lessFunc(1, 2) << endl; //輸出1（true的整數表示為1）//第二種：operator()cout << lessFunc.operator()(1, 2) << endl; //等價調用/*------------第三部分：冒泡排序結合仿函數進行排序------------*/int a[] = { 9,1,2,8,5,7,4,6,3 };int n = sizeof(a) / sizeof(a[0]);//1.使用仿函數進行冒泡排序（升序/降序）cout << "使用“仿函數Less<int> lessFunc”進行升序排序：" << endl;BubbleSort(a, n, lessFunc);    //升序排序for (int i = 0; i < n; i++){cout << a[i] << " ";}cout << endl;cout << "使用“仿函數Greater<int>”進行降序排序：" << endl;BubbleSort(a, n, greaterFunc); //降序排序for (int i = 0; i < n; i++){cout << a[i] << " ";}cout << endl;//2.也可直接傳遞匿名對象（臨時對象）cout << "使用“匿名對象Less<int>()”進行升序排序：" << endl;BubbleSort(a, n, Less<int>());for (int i = 0; i < n; i++){cout << a[i] << " ";}cout << endl;cout << "使用“匿名對象Greater<int>()”進行降序排序：" << endl;BubbleSort(a, n, Greater<int>());for (int i = 0; i < n; i++){cout << a[i] << " ";}cout << endl;return 0;
}

二、容器適配器

1. 什么是容器適配器？

容器適配器（Container Adapter）：是 C++ 標準庫中的一種特殊容器，它不直接提供完整的數據存儲功能，而是通過封裝其他底層容器（如：vector、deque、list）并限制其接口，來實現特定的數據結構。

• 這種設計遵循適配器模式，將已有容器的功能轉換為用戶期望的接口。
• 它們基于現有的序列容器（如：vector、list、deque）提供特定的接口和行為，實現了不同的數據結構抽象。

---

核心特點：

1. 封裝底層容器：適配器內部維護一個底層容器對象（如：deque），所有操作都委托給該容器執行
2. 限制接口：適配器僅暴露特定的接口（如：棧的 push/pop/top），隱藏底層容器的其他功能，確保數據結構的語義正確性
3. 可配置底層容器：用戶可通過模板參數指定底層容器類型，默認使用 deque（兼顧效率與靈活性）

2. C++中的三種標準容器適配器的對比差別？

適配器	默認底層容器	可選底層容器	數據結構	主要操作	典型用途
stack	deque	vector list	棧 (LIFO)	push, pop top	函數調用棧 撤銷操作
queue	deque	list	隊列 (FIFO)	push, pop front, back	任務調度 消息隊列
priority_queue	vector	deque	優先隊列	push, pop top	任務優先級調度 Dijkstra算法

為什么queue的底層容器不可以是：vector？

適配器queue：底層容器既可以是標準容器類模板（如：deque、list 等），也能是其他專門設計的容器類。但這類底層容器至少需支持以下操作：

• front：返回隊頭元素的引用（對應容器頭部元素訪問）
• back：返回隊尾元素的引用（對應容器尾部元素訪問）
• pop_front：在容器頭部執行操作，實現隊列 “頭部出隊” 邏輯
• push_back：在容器尾部執行操作，實現隊列 “尾部入隊” 邏輯
• size：返回容器中有效元素的個數（即隊列有效元素數量）
• empty：檢測容器（對應隊列邏輯）是否為空

---

在 C++ 標準庫中，deque 和 list 這兩種標準容器類滿足上述全部要求，而容器vector卻不滿足上面的要求

• 因此，默認情況下，若創建 queue 時未手動指定底層容器，STL 會自動使用 deque 作為其底層容器。
• 也可以顯示指定使用list作為底層容器。
• 但是不能使用vector作為底層容器。

為什么priority_queue的底層容器不可以是：list？

適配器priority_queue：底層容器既可以是標準容器類模板（如：vector、deque 等），也可以是其他專門設計的容器類。但該容器至少需支持以下操作：

• 支持隨機訪問迭代器，以便內部能通過迭代器操作維持堆結構
• 需實現以下基礎操作：
  • front()：返回容器中第一個元素的引用（對應堆頂邏輯）
  • push_back()：在容器尾部插入元素（用于新元素入堆）
  • pop_back()：刪除容器尾部元素（用于堆頂元素出堆后調整結構 ）
  • size()：返回容器中有效元素的個數
  • empty()：檢測容器是否為空

---

在 C++ 標準庫中，vector 和 deque 這兩種標準容器類滿足上述全部要求，而容器list 卻不滿足上面的要求

• 因此，默認情況下，若創建 priority_queue 時未手動指定底層容器，STL 會自動使用 vector 作為其底層容器。
• 也可以顯示指定使用deque 作為底層容器。
• 但是不能使用list作為底層容器。

為什么priority_queue的默認的底層容器是：vector？

看了上面的分析，相信大家已經知道為什么容器適配器priority_queue的底層容器為什么不能是list了

但是我相信一定還有小伙伴會疑惑：“既然 vector和deque都可以作為priority_queue的底層容器，那為什么默認選擇vector而不是deque呢？”

---

這主要與 priority_queue 的核心操作特性和兩種容器的性能差異有關
具體原因如下：

priority_queue 的核心操作（如：push、pop）依賴 隨機訪問迭代器 和 下標操作 來調整堆結構（調用 std::push_heap、std::pop_heap 等算法）

• vector的優勢：

  • 支持連續內存存儲和隨機訪問迭代器

  • 通過下標 operator[] 訪問元素的時間復雜度為$O(1)$

• deque的劣勢：

  • 雖然也支持隨機訪問迭代器，但內部采用分段連續存儲（緩沖區鏈表），迭代器的底層實現更復雜

  • 下標訪問的性能略低于 vector

---

口說無憑，接下來我們通過一個測試案例來直觀對比 vector 與 deque 兩個容器的隨機訪問性能差異。

代碼案例：性能測試vector與deque的排序效率對比

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;/*===================== 性能測試：vector與deque的排序效率對比 =====================*/
//測試目的：比較vector和deque在排序操作中的性能差異
//結論：vector排序效率更高，因內存連續，CPU緩存利用率更好void test_op1()
{cout << "===========性能測試：vector與deque的排序效率對比===========" << endl;/*----------------第一階段：設置隨機環境----------------*///1.種隨機數種子srand(unsigned int(time(0)));//2.設隨機數據量const int N = 1'000'000; //測試數據量：100萬/*----------------第二階段：定義vector和deque容器----------------*/vector<int> vec; //動態數組（連續內存）deque<int> deq; //雙端隊列（非連續內存）/*----------------第三階段：賦值vector和deque容器相同的隨機數----------------*/for (int i = 0; i < N; ++i) {auto e = rand() + i; vec.push_back(e);deq.push_back(e);}/*----------------第四階段：測試vector和deque容器排序時間----------------*///1.測試vector排序時間int begin1 = clock(); sort(vec.begin(), vec.end());   //使用STL排序算法（基于快速排序/歸并排序）int end1 = clock(); //2.測試deque排序時間int begin2 = clock();sort(deq.begin(), deq.end()); //deque迭代器為雙向迭代器，排序效率低于vectorint end2 = clock();/*----------------第五階段：輸出vector和deque容器排序時間----------------*/// 輸出耗時（單位：毫秒，clock()/CLOCKS_PER_SEC=秒）printf("vector排序耗時:%d ms\n", end1 - begin1);printf("deque排序耗時:%d ms\n", end2 - begin2);
}/*===================== 性能優化測試：deque排序的優化方案 =====================*/
//測試目的：驗證將deque數據拷貝到vector后排序是否更高效
//結論：拷貝后排序+拷貝回deque的總耗時 低于 直接排序dequevoid test_op2()
{cout << "===========性能優化測試：deque排序的優化方案===========" << endl;/*----------------第一階段：設置隨機環境----------------*/srand(unsigned int(time(0)));const int N = 1000000;/*----------------第二階段：定義兩個deque容器----------------*/deque<int> deq1; //原始dequedeque<int> deq2; //用于測試優化方案的deque/*----------------第三階段：賦值兩個deque容器相同的隨機數----------------*/for (int i = 0; i < N; ++i) {auto e = rand() + i;deq1.push_back(e);deq2.push_back(e);}/*----------------第四階段：測試兩個deque容器排序時間----------------*///1.測試直接排序deque的耗時int begin1 = clock();sort(deq1.begin(), deq1.end()); //直接排序deque（雙向迭代器，非連續內存）int end1 = clock();//2.測試優化方案：拷貝到vector排序后再拷貝回dequeint begin2 = clock();vector<int> v(deq2.begin(), deq2.end()); // 拷貝deque數據到vector（連續內存）sort(v.begin(), v.end());                // 高效排序vectordeq2.assign(v.begin(), v.end());         // 拷貝回dequeint end2 = clock();/*----------------第五階段：輸出兩個deque容器的排序時間----------------*/printf("deque直接排序耗時:%d ms\n", end1 - begin1);printf("deque拷貝到vector排序后拷貝回耗時:%d ms\n", end2 - begin2);
}int main()
{test_op1();test_op2(); return 0;
}

3. 使用容器適配器需要注意那些事情？

使用容器適配器時我們需要注意以下兩點的內容：

• 迭代器限制：適配器不提供迭代器

  • 例如：begin()、end()，因為其設計目的是限制訪問方式（如：棧只能訪問棧頂）

• 底層容器選擇：根據操作頻率選擇容器

  • 例如：stack 頻繁 push/pop 時選 deque，需隨機訪問選 vector

三、序列容器：deque（雙端隊列）

相信大家看了上面的關于容器適配器的介紹，已經對于這個底層容器deque有了一定的了解

• 雖然我們之前解釋了為什么 priority_queue 的默認底層容器是 vector，但可能有些小伙伴還未完全理解其中的邏輯。

• 此外，或許還有小伙伴想知道另一個問題的答案：為什么 STL 選擇 deque 作為 stack 和 queue 的底層默認容器？

那下面，就讓我們深入探究這個容器的特性，解開這些疑惑吧！

1. 什么是deque？

deque（雙端隊列）：是 C++ 標準模板庫（STL）中的一種序列式容器，全稱是 double-ended queue

• 它允許在容器的頭部和尾部高效地執行元素的插入、刪除和訪問操作

• 同時支持隨機訪問（通過下標訪問元素）

---

總結：它結合了 vector 和 list 的部分優點。

deque的核心特點：

1. 雙端操作高效

• 可以在 $O(1)$ 時間復雜度內從頭部（front）或尾部（back）插入 / 刪除元素
  • 性能與 list 相當，但比 vector 更靈活（vector 僅尾部操作高效）

---

2. 隨機訪問支持

• 提供隨機訪問迭代器（operator[] 和 at() 方法），可以像數組一樣通過下標直接訪問元素，時間復雜度為 $O(1)$
  • 但與 vector 不同，deque 的內存并非連續存儲，因此迭代器的底層實現更復雜，隨機訪問的緩存效率略低于 vector

---

3. 動態擴容

• 無需預先指定容量，可根據元素數量動態擴展
  • 擴容時通常不會像 vector 一樣整體復制元素，而是通過增加分段連續的內存塊（緩沖區）來擴展，避免了大規模數據移動

2. deque的底層結構是什么樣的？

物理存儲結構

deque 的底層實現通常通過 分塊數組（分段連續存儲）實現：

• 由多個固定大小的數組塊（buffer）組成，每個塊存儲部分元素。
• 通過一個中央控制映射表（map）管理，記錄每個緩沖區的地址和邊界，保證邏輯上的連續性。

總結： 這種結構使得 deque 在頭部和尾部擴展時只需分配新的緩沖區，無需移動已有元素，適合需要頻繁雙端操作的場景。

迭代器的設計

deque（雙端隊列）的底層并非真正的連續內存空間，而是由多個分段連續的小內存塊（緩沖區）拼接而成。

• 從邏輯上看，它類似于一個動態的二維數組，通過巧妙的設計讓用戶感知到 “整體連續” 的訪問體驗，但實際上每個小段內存是連續的，段與段之間通過指針連接。

---

為了維護這種連續空間和隨機訪問的假象，deque 的迭代器承擔了關鍵角色。

由于其內存結構的特殊性，deque 的迭代器需要處理跨段訪問的邏輯，因此設計比 vector 的迭代器更復雜。

具體來說，迭代器需要記錄：

• 當前所在的緩沖區
• 緩沖區中的位置
• 以及指向下一個 / 上一個緩沖區的指針

從而在遍歷或隨機訪問時能夠正確跳轉至目標位置。

---

簡單來說：deque 通過 分段連續存儲 + 復雜迭代器 的組合，實現了雙端高效操作與隨機訪問的平衡，盡管底層物理空間不連續，但邏輯上呈現為一個連續的隊列

3. deque的優勢是什么？

當我們了解了上面 deque 的 物理存儲結構（分段連續內存塊）和迭代器的設計（跨段訪問邏輯） 后，下面關于 deque 與 vector 的對比就不難理解了。

特性	vector	deque
內存連續性	連續存儲	分段連續存儲（非連續）
隨機訪問性能	高（緩存利用率好）	稍低（跨緩沖區時需指針跳轉）
頭部操作效率	O (n)（需移動所有元素）	O(1)
擴容策略	按需翻倍（整體復制）	新增緩沖區（局部擴展）
適用場景	隨機訪問多、尾部操作多	雙端操作多、長度頻繁變化

deque的優勢在于：

與vector相比：

• 頭部操作高效：在頭部插入或刪除元素時，無需像 vector 那樣搬移后續所有元素，時間復雜度為 $O(1)$，效率顯著更高。
• 擴容代價低：擴容時，無需像 vector 那樣整體復制大量元素，只需新增或釋放分段連續的小內存塊（緩沖區），避免了大規模數據移動，尤其適合頻繁動態擴展的場景。

與list相比：deque 的底層采用分段連續空間（而非鏈表結構），空間利用率更高，且無需為每個元素存儲額外的指針字段。

4. deque的致命缺陷是什么？

在此之前，我們提到過 deque 這種序列容器是 vector 和 list “各取所長” 的結合體：它既有 vector 隨機訪問的特性，又有 list 雙端高效操作的優勢。

并且在多數場景的性能對比中表現不俗，僅在連續隨機訪問性能上略遜于 vector，那么請問：既然 deque 看起來如此優秀，為什么我們在之前的數據結構學習中沒有接觸過它呢？ 哈哈，我們就不得不談談它的致命缺陷了！！！

---

deque 存在一個致命缺陷：不適合頻繁遍歷

• 由于其底層是分段連續的內存塊，遍歷時迭代器需要頻繁檢測是否到達當前緩沖區的邊界，并跳轉至下一段緩沖區，這會導致額外的性能開銷，遍歷效率低于 vector 和 list

在需要線性遍歷的場景中，deque 的這一特性可能成為瓶頸，因此實際開發中，當需要線性數據結構時，開發者通常優先選擇

• vector（適合隨機訪問和尾部操作）
• list（適合雙向遍歷和中間插入/刪除）

---

而deque 的應用場景相對較少，目前，deque 的典型應用是作為 STL 中 stack（棧）和 queue（隊列）的底層數據結構，充分利用其雙端操作高效的特性，同時規避了頻繁遍歷的需求。

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

stack（棧）：是一種后進先出（LIFO）的線性數據結構。

• 因此只要具備 push_back() 和 pop_back() 操作的線性容器，都可以作為其底層容器。

• 例如：vector 和 list

+++++++++++++++++++++++++++++++++
queue（隊列）：是一種先進先出（FIFO）的線性數據結構。

• 只需支持 push_back() 和 pop_front() 操作的容器即可作為底層容器。

• 例如：list

---

但在 STL 中，stack 和 queue 默認選擇 deque 作為底層容器，主要原因如下：

1. 操作場景匹配：

• stack 和 queue 不需要遍歷元素（因此標準庫中它們不提供迭代器），僅需在固定一端或兩端進行操作

  • 如：棧的棧頂、隊列的隊頭和隊尾

• deque 的雙端操作效率為 $O(1)$，且無需遍歷，完美契合這種場景。

• deque 的主要缺陷是遍歷效率低（因迭代器需處理跨緩沖區跳轉），但 stack 和 queue 完全不涉及遍歷操作，因此能完美避開這一缺陷，充分發揮其雙端操作和動態擴容的優勢。

---

2. 性能與內存優勢：

• 對于stack：元素增長時，deque 的擴容無需像 vector 那樣整體搬移數據，只需新增分段連續的內存塊（緩沖區），效率更高
• 對于queue：元素增長時，deque 既能在尾部高效插入（push_back），又能在頭部高效刪除（pop_front），且分段存儲的內存利用率高于 list（無需為每個元素存儲指針）

綜上：deque 的特性與 stack、queue 的操作需求高度契合，成為 STL 選擇其作為默認底層容器的核心原因。