C++中的stack和queue
前言
這一節的內容對于stack和queue的使用介紹會比較少，主要是因為stack和queue的使用十分簡單，而且他們的功能主要也是在做題的時候才會顯現。這一欄目暫時不會寫關于做題的內容，后續我會額外開一個做題日記的欄目的。
這節內容主要給大家講解一下stack和queue的特殊性，和相關實現。
使用
對stack和queue的簡單介紹
一、基本概念
-
Stack（棧）：
- 后進先出（LIFO）：最后插入的元素最先被移除。
- 類比：一摞盤子（只能從頂部取放）。
- 核心操作：
push（入棧）、pop（出棧）、top（訪問棧頂）。
-
Queue（隊列）：
- 先進先出（FIFO）：最先插入的元素最先被移除。
- 類比：排隊購票（隊尾進，隊頭出）。
- 核心操作：
push（入隊）、pop（出隊）、front/back（訪問隊頭/隊尾）。
二、底層實現原理//重點
-
容器適配器：
stack和queue不是獨立的容器，而是基于其他容器（如deque、list）的接口封裝。// 默認底層容器：deque（雙端隊列）//這個容器會在下一節講解 stack<int> s; // 等價于 stack<int, deque<int>> queue<int> q; // 等價于 queue<int, deque<int>>// 自定義底層容器（需滿足操作要求） stack<int, vector<int>> s_vec; // 使用 vector queue<int, list<int>> q_list; // 使用 list
-
底層容器要求：
操作 stack所需支持queue所需支持尾部插入 push_back()push_back()尾部刪除 pop_back()? 頭部刪除 ? pop_front()訪問尾部 back()back()訪問頭部 ? front()?? 注意：
vector不能直接用于queue（缺少pop_front()）。
三、核心操作與時間復雜度
| 操作 | stack | queue | 時間復雜度 |
|---|---|---|---|
| 插入元素 | push(val) | push(val) | O(1) |
| 刪除元素 | pop() | pop() | O(1) |
| 訪問頂部/頭部元素 | top() | front() | O(1) |
| 訪問尾部元素 | ? | back() | O(1) |
| 檢查是否為空 | empty() | empty() | O(1) |
| 獲取元素數量 | size() | size() | O(1) |
💡 為什么高效？
默認基于deque（動態數組分塊存儲），插入/刪除操作均攤常數時間。
四、使用示例
-
Stack 示例：括號匹配
#include <stack> bool isValid(string s) {stack<char> st;for (char c : s) {if (c == '(' || c == '[') st.push(c);else {if (st.empty()) return false;char top = st.top();if ((c == ')' && top != '(') || (c == ']' && top != '[')) return false;st.pop();}}return st.empty(); } -
Queue 示例：BFS 算法框架
#include <queue> void BFS(Node* start) {queue<Node*> q;q.push(start);while (!q.empty()) {Node* cur = q.front();q.pop();// 處理當前節點for (Node* neighbor : cur->neighbors) {q.push(neighbor);}} }
五、應用場景
| 數據結構 | 典型應用場景 |
|---|---|
stack | 函數調用棧、表達式求值、DFS 遍歷、撤銷操作（Ctrl+Z） |
queue | 消息隊列、BFS 遍歷、緩沖區管理（如打印機任務）、多線程任務調度 |
六、注意事項
-
空容器操作禁止：
stack<int> s; s.pop(); // 未定義行為（崩潰）！ if (!s.empty()) s.pop(); // 正確做法 -
不支持遍歷：
二者均沒有迭代器，無法用for (auto x : s)遍歷。 -
底層容器選擇：
stack優先選vector（內存局部性好）。queue只能選deque或list（避免用vector）。
-
線程安全：
STL 的stack/queue不是線程安全的，多線程需手動加鎖。
七、進階技巧
-
用
vector模擬棧（簡化內存管理）：vector<int> v_stack; v_stack.push_back(10); // push int top = v_stack.back(); // top v_stack.pop_back(); // pop -
雙棧實現隊列：
class Queue {stack<int> in, out;void push(int x) { in.push(x); }int pop() {if (out.empty()) {while (!in.empty()) {out.push(in.top()); in.pop();}}int val = out.top();out.pop();return val;} };
總結
| 特性 | stack | queue |
|---|---|---|
| 數據順序 | LIFO（后進先出） | FIFO（先進先出） |
| 核心接口 | push(), pop(), top() | push(), pop(), front() |
| 底層依賴 | deque/vector/list | deque/list |
| 遍歷 | 不支持 | 不支持 |
| 適用場景 | 逆序操作、遞歸 | 順序處理、緩沖 |
? 選擇原則：
- 需要回溯操作 →
stack（如 DFS、撤銷機制）- 需要公平調度 →
queue（如 BFS、消息隊列）
C++ priority_queue （優先隊列）詳解
一、本質與核心概念
優先隊列（priority_queue） 是一種特殊的隊列，元素按優先級順序出隊（而非插入順序）。它是基于堆數據結構（通常是二叉堆）實現的容器適配器。
也就是說，當我們需要使用到堆這個數據結構的時候，使用這個優先級隊列就ok了，它也是被包括在queue頭文件中的。
關鍵特性：
- 隊首元素總是當前隊列中優先級最高的元素
- 默認行為：最大元素優先（大頂堆//堆頂元素最大）
- 底層結構：默認使用
vector作為容器//這個優先級隊列也是一個容器適配器 - 時間復雜度：
- 訪問隊首：O(1)
- 插入元素：O(log n)
- 刪除隊首：O(log n)
二、底層實現原理
template<class T,class Container = std::vector<T>,class Compare = std::less<typename Container::value_type>
> class priority_queue;
-
堆結構維護：
- 插入時 (
push)：將元素添加到末尾，然后進行上浮操作（sift up）//也就是我們學習堆數據結構時候的向上調整。 - 刪除時 (
pop)：交換首尾元素，刪除尾部，然后進行下沉操作（sift down）//也就是我們學習堆數據結構時候的向下調整。
- 插入時 (
-
堆算法函數（底層實際調用）：
std::make_heap() // 建堆 std::push_heap() // 插入后調整 std::pop_heap() // 刪除前調整
三、模板參數詳解
| 參數 | 說明 | 默認值 |
|---|---|---|
T | 元素類型 | 必填 |
Container | 底層容器 | vector<T> |
Compare | 優先級比較函數 | less<T> |
底層容器要求：
- 必須支持隨機訪問迭代器（
vector/deque） - 必須支持
front(),push_back(),pop_back() - 不兼容
list（缺少隨機訪問）
四、核心操作與時間復雜度
| 操作 | 函數 | 時間復雜度 | 說明 |
|---|---|---|---|
| 插入元素 | push(const T& val) | O(log n) | 添加元素并調整堆 |
| 刪除隊首 | pop() | O(log n) | 移除最高優先級元素 |
| 訪問隊首 | top() | O(1) | 返回隊首元素（只讀） |
| 檢查空 | empty() | O(1) | 判斷是否為空 |
| 獲取大小 | size() | O(1) | 返回元素數量 |
五、創建與初始化
// 默認創建（大頂堆）
std::priority_queue<int> max_heap;// 預分配空間
std::vector<int> vec{3,1,4,1,5};
std::priority_queue<int> pre_heap(vec.begin(), vec.end());// 自定義比較函數（小頂堆）
auto cmp = [](int a, int b) { return a > b; };
std::priority_queue<int, std::vector<int>, decltype(cmp)> min_heap(cmp);// 使用函數對象（推薦）//這其實就是仿函數，等會后面會講
struct Compare {bool operator()(const Person& a, const Person& b) {return a.age < b.age; // 年齡大的優先}
};
std::priority_queue<Person, std::vector<Person>, Compare> age_heap;
六、自定義優先級規則（關鍵技巧）
// 方法1：重載 operator<
struct Task {int priority;std::string name;bool operator<(const Task& other) const {return priority < other.priority; // 大頂堆要求}
};// 方法2：自定義函數對象
struct TaskComparator {bool operator()(const Task& a, const Task& b) {return a.priority < b.priority; // 注意：返回true表示a優先級低于b}
};// 方法3：使用標準函數對象（創建小頂堆）
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
?? 比較函數重要規則：
- 當
comp(a, b) == true時，a的優先級將低于b- 對于大頂堆：
return a < b;- 對于小頂堆：
return a > b;
七、典型應用場景
-
任務調度系統：
struct Task {int priority;std::function<void()> job;bool operator<(const Task& t) const { return priority < t.priority; } }; std::priority_queue<Task> scheduler; -
Dijkstra 最短路徑算法：
std::priority_queue<std::pair<int, int>> pq; // { -distance, node } pq.push({0, start}); // 使用負值實現最小堆 -
合并K個有序鏈表：
auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; }; std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(cmp)> pq(cmp); -
實時獲取中位數（雙堆法）：
std::priority_queue<int> max_heap; // 存儲較小一半 std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap; // 存儲較大一半
八、底層容器選擇策略
| 容器 | 隨機訪問 | 內存連續性 | 適用性 | 推薦場景 |
|---|---|---|---|---|
vector | ? | ? | 推薦 | 通用場景 |
deque | ? | ?（分塊） | 可用 | 避免尾部擴容 |
list | ? | ? | 不兼容 | - |
為什么用
vector不用deque？
vector內存連續，緩存友好- 堆操作主要依賴隨機訪問，
vector性能更優
九、特殊操作與技巧
-
高效初始化：
std::vector<int> data{3,1,4,5,9,2,6}; // 直接通過迭代器建堆（O(n) 時間復雜度） std::priority_queue<int> pq(data.begin(), data.end()); -
清空隊列的陷阱：
// 錯誤方式（低效）： while (!pq.empty()) pq.pop(); // O(n log n)// 正確方式： std::priority_queue<int> empty; std::swap(pq, empty); // O(1) -
修改隊首元素（高級技巧）：
// 1. 取出隊首 auto top = pq.top(); pq.pop();// 2. 修改元素 top.value = new_value;// 3. 重新插入 pq.push(top);
十、與相似數據結構的對比
| 特性 | priority_queue | set/multiset | map/multimap |
|---|---|---|---|
| 排序方式 | 堆序 | 紅黑樹序 | 紅黑樹序 |
| 重復元素 | 允許 | multiset允許 | multimap允許 |
| 隨機訪問 | 僅隊首 | 不支持 | 不支持 |
| 插入刪除 | O(log n) | O(log n) | O(log n) |
| 查找元素 | 不支持 | O(log n) | O(log n) |
| 內存開銷 | 低 | 高（指針） | 高（指針） |
十一、性能優化指南
-
元素使用移動語義：
struct HeavyObject {std::vector<int> big_data;HeavyObject(HeavyObject&& other) noexcept = default; }; pq.push(std::move(obj)); // 避免大對象復制 -
預留空間（僅
vector底層）：// 直接訪問底層容器（不推薦但有效） std::priority_queue<int, std::vector<int>> pq; pq.c.reserve(1000); // 訪問底層容器的reserve -
自定義內存分配器：
template<typename T> class CustomAllocator { /* ... */ };using CustomPQ = std::priority_queue<int, std::vector<int, CustomAllocator<int>>;
十二、常見錯誤與陷阱
-
錯誤比較函數：
// 錯誤：返回true表示a優先級低于b auto cmp = [](int a, int b) { return a < b; }; // 正確的大頂堆 auto wrong_cmp = [](int a, int b) { return a > b; }; // 錯誤！實際創建了小頂堆 -
修改隊首破壞堆結構：
// 錯誤：直接修改隊首元素 pq.top().priority = 100; // 破壞堆性質！ -
遍歷隊列陷阱：
while (!pq.empty()) {process(pq.top()); // 錯誤：忘記pop()導致死循環pq.pop(); // 必須顯式pop }
十三、最佳實踐總結
| 場景 | 推薦方案 |
|---|---|
| 需要最高優先級元素 | priority_queue |
| 需要完整排序 | set 或 map |
| 需要遍歷元素 | vector + std::sort |
| 需要快速查找 | unordered_map |
| 內存敏感場景 | priority_queue + vector |
? 黃金法則：
- 優先使用
vector作為底層容器- 比較函數中明確優先級規則
- 避免直接修改隊列內部元素
- 批量初始化優于逐個插入
- 使用移動語義減少拷貝開銷
十四、C++20 新特性
-
范圍構造支持：
std::vector data{5, 3, 8, 1}; std::priority_queue pq(std::less{}, data); // C++20 類型推導 -
透明比較器優化：
std::priority_queue<std::string, std::vector<std::string>,std::less<>> pq; // 支持異構查找 pq.push("test"); auto it = find_if(begin(pq.c), end(pq.c), [](auto& s){ return s == "test"; }); // 直接比較
十五、綜合示例：醫院急診系統
struct Patient {std::string name;int severity; // 1-10, 10為最嚴重time_t arrival_time;bool operator<(const Patient& other) const {// 優先級規則：先按嚴重程度，再按到達時間return std::tie(severity, arrival_time) < std::tie(other.severity, other.arrival_time);}
};std::priority_queue<Patient> emergency_queue;void admit_patient(std::string name, int severity) {emergency_queue.push({name, severity, time(nullptr)});
}void treat_next_patient() {if (emergency_queue.empty()) return;Patient next = emergency_queue.top();emergency_queue.pop();std::cout << "Treating: " << next.name << " (Severity: " << next.severity << ")\n";
}
總結：優先隊列三要素
- 數據結構核心：二叉堆實現
- 優先級控制：通過比較函數定制
- 性能平衡：
- O(1) 訪問隊首
- O(log n) 插入/刪除
- O(n) 建堆
📌 使用決策樹：
需要不斷獲取 最大值/最小值 + 頻繁插入刪除 → 選擇priority_queue
需要完整排序/遍歷 → 選擇set或排序vector
需要鍵值關聯 → 選擇map
容器適配器
那么我們這一節的重點其實就是這個知識點：容器適配器。弄清楚容器適配器是啥？怎么使用。
一、什么是容器適配器？
容器適配器（Container Adapter）是 STL 中的特殊容器，它們不直接管理數據，而是通過"借用"已有容器（如 deque、vector、list）的功能，提供特定接口來實現特定數據結構行為。
類比解釋：
這里我結合stack和現實生活中的樣例給大家解釋一下：
stack（也就是棧）它的特點不就是后進先出嘛，那么要怎么實現后進先出呢？那其實也很簡單，首先棧的插入，也就是棧的push功能，其實就是尾部插入數據嘛。那么后進先出，這里其實涉及到的就是pop刪除元素的功能函數嘛，后進先出，也就是pop元素的時候默認調用一個尾部刪除pop_back函數。棧的一些其余功能，如取棧頂元素是返回數組末尾元素。之前在講棧的時候就說過棧其實是一個特殊的線性表，特殊在它的操作（如刪除操作就是指定尾部刪除數據）。但是這些特殊操作我們也可以調用普通數據結構中的某些函數來實現，就好比如vector就可以完美的轉換成stack。之前我們學習數據結構的時候，因為沒有模板，所以我們要額外寫一份棧的代碼，但是現在有了模板之后，我們就可以借助模板，將某些容器轉換成某些別的容器，就好比如vector轉換成stack。
用生活中的例子給大家解釋的話，我覺得大家可以這樣想：假設現在電腦上沒有網線接口或者有線耳機的線孔，只有一個Type-C接口，那么這個Type-C接口我們就可以把它當作vector。現在網上不是有很多擴展塢嘛，擴展塢上啥孔都有，我們把這個擴展塢想象成模板。假設我現在想給我的筆記本電腦插上網線，但是沒有網線接口。那么我們就可以使用擴展塢將原來的Type-C接口變成網線接口。在C++中，vector轉換成stack是容器轉容器，在現實里，Type-C接口轉網線接口是接口轉接口。大家可以這樣類比的理解，雖然這是一個不太嚴謹的例子，但是我個人覺得還是不錯的。
所以說這里的網線其實是借用Type-C接口進行與電腦的連接。
二、為什么需要容器適配器？
| 方式 | 直接實現數據結構 | 使用容器適配器 |
|---|---|---|
| 開發成本 | 需從頭實現所有操作 | 復用已有容器代碼 |
| 靈活性 | 固定實現 | 可自由切換底層容器 |
| 維護性 | 需單獨維護 | 依賴 STL 標準容器 |
| 性能優化 | 優化困難 | 輕松切換高效底層容器 |
三、三大容器適配器
stack：后進先出（LIFO）結構queue：先進先出（FIFO）結構priority_queue：優先級隊列（元素按優先級排序）
四、底層容器要求（核心知識）
每個適配器對底層容器有特定接口要求：
1. stack 的底層容器必須支持：
push_back() // 尾部插入
pop_back() // 尾部刪除
back() // 訪問尾部元素
? 兼容容器：deque（默認）、vector、list
2. queue 的底層容器必須支持：
push_back() // 尾部插入
pop_front() // 頭部刪除
front() // 訪問頭部元素
back() // 訪問尾部元素（非必須但常用）
? 兼容容器：deque（默認）、list
? 不兼容：vector（缺少 pop_front）
3. priority_queue 的額外要求：
// 需要隨機訪問迭代器
front() // 訪問首元素
push_back() // 尾部插入
pop_back() // 尾部刪除
// 內部使用堆算法（需支持隨機訪問）
? 兼容容器：vector（默認）、deque
五、底層容器性能對比
| 操作 | vector | deque | list |
|---|---|---|---|
| 尾部插入 | O(1) 均攤 | O(1) | O(1) |
| 頭部插入 | O(n) | O(1) | O(1) |
| 隨機訪問 | O(1) | O(1) | O(n) |
| 內存布局 | 連續內存 | 分塊連續 | 非連續 |
| 適配 stack | ? 推薦 | ? | ? |
| 適配 queue | ? 不兼容 | ? 默認 | ? |
💡 黃金搭配：
stack+vector：內存連續，緩存友好queue+deque：高效頭尾操作priority_queue+vector：堆算法需要隨機訪問
六、自定義底層容器（實戰示例）
#include <stack>
#include <vector>
#include <list>
#include <queue>// 自定義stack底層容器
std::stack<int, std::vector<int>> vec_stack; // 基于vector
std::stack<int, std::list<int>> list_stack; // 基于list// 自定義queue底層容器
std::queue<int, std::list<int>> list_queue; // 基于list// priority_queue使用vector
std::priority_queue<int, std::vector<int>> max_heap;
七、容器適配器 VS 普通容器
| 特性 | 普通容器（vector/list） | 容器適配器（stack/queue） |
|---|---|---|
| 迭代器 | ? 支持完整迭代器 | ? 無迭代器 |
| 遍歷 | ? 可隨機訪問任意元素 | ? 只能訪問特定端元素 |
| 底層數據 | ? 可直接訪問 | ? 隱藏底層實現 |
| 功能接口 | 提供完整容器操作 | 僅暴露特定數據結構接口 |
| 設計目的 | 通用數據存儲 | 特定數據行為抽象 |
八、實現原理揭秘
template<typename T, typename Container = std::deque<T>>
class stack //棧
{public:void push(const T& value) { c.push_back(value); // 調用底層容器的push_back}void pop() { c.pop_back(); // 調用底層容器的pop_back}T& top() { return c.back(); // 調用底層容器的back}size_t size(){return c.size();//調用底層容器的size}bool empty(){return c.empty();//調用底層容器的empty}private:Container c; // 底層容器對象
};
template<class T, class Container = std::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();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
#include <vector>
#include <functional> // 用于 std::less
#include <algorithm> // 用于 std::swaptemplate <typename T, typename Container = std::vector<T>,typename Compare = std::less<typename Container::value_type>>
class priority_queue //優先隊列
{
public:// 默認構造函數priority_queue() = default;// 使用自定義比較器的構造函數explicit priority_queue(const Compare& comp) : comp(comp) {}// 通過迭代器范圍構造template <typename InputIterator>priority_queue(InputIterator first, InputIterator last, const Compare& comp = Compare()): c(first, last), comp(comp) {build_heap(); // 構建堆}// 插入元素void push(const T& value) {c.push_back(value); // 添加到末尾sift_up(c.size() - 1); // 上浮新元素}// 刪除堆頂元素void pop() {if (c.empty()) return;std::swap(c[0], c.back()); // 交換首尾元素c.pop_back(); // 刪除原堆頂if (!c.empty()) {sift_down(0); // 下沉新堆頂}}// 訪問堆頂元素（只讀）const T& top() const {return c.front();}// 元素數量size_t size() const {return c.size();}// 檢查是否為空bool empty() const {return c.empty();}private:Container c; // 底層容器Compare comp; // 比較函數對象// 構建堆（Floyd算法）void build_heap() {// 從最后一個非葉子節點開始下沉for (int i = (c.size() / 2) - 1; i >= 0; --i) {sift_down(i);}}// 上浮操作void sift_up(size_t idx) {while (idx > 0) {size_t parent = (idx - 1) / 2;// 如果當前節點優先級高于父節點if (comp(c[parent], c[idx])) {std::swap(c[parent], c[idx]);idx = parent;} else {break; // 堆條件已滿足}}}// 下沉操作void sift_down(size_t idx) {size_t largest = idx;const size_t n = c.size();while (true) {size_t left = 2 * idx + 1;size_t right = 2 * idx + 2;// 檢查左子節點if (left < n && comp(c[largest], c[left])) {largest = left;}// 檢查右子節點if (right < n && comp(c[largest], c[right])) {largest = right;}// 如果當前節點不是最大，交換并繼續下沉if (largest != idx) {std::swap(c[idx], c[largest]);idx = largest;} else {break; // 堆條件已滿足}}}
};
關鍵點：所有操作轉發到底層容器的特定接口
九、特殊行為解析
-
為什么
stack不提供clear()？
因為標準委員會認為while(!s.empty()) s.pop()已足夠清晰 -
priority_queue的排序控制：// 創建小頂堆（默認是大頂堆） std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap; -
queue的back()不是必須的：
某些實現（如早期 STL）允許使用不支持back()的容器
十、設計思想與最佳實踐
-
適配器模式精髓：
- 不改變已有容器代碼
- 通過限制接口實現新功能
- 符合開閉原則（對擴展開放，對修改封閉）
-
使用建議：
// 需要后進先出 → 選擇 stack stack<int, vector<int>> s; // 推薦 vector 提高緩存命中率// 需要先進先出 → 選擇 queue queue<int> q; // 默認 deque 最均衡// 需要優先級處理 → priority_queue priority_queue<int> pq; // 默認 vector 大頂堆 -
避免的陷阱：
// 錯誤：vector 缺少 pop_front() std::queue<int, std::vector<int>> invalid_queue; // 錯誤：嘗試遍歷適配器 for(auto it = s.begin(); it != s.end(); ++it) // stack 無迭代器
十一、性能優化技巧
-
預分配內存（
vector底層時）：std::stack<int, std::vector<int>> s; s.c.reserve(1000); // 直接訪問底層容器預分配 -
選擇分塊存儲容器避免擴容：
// 處理超大數據時使用 deque std::stack<int, std::deque<int>> big_stack; -
自定義內存分配器：
std::stack<int, std::vector<int, MyAllocator<int>>> custom_stack;
十二、總結：容器適配器的本質
| 維度 | 說明 |
|---|---|
| 身份 | 底層容器的"接口轉換器" |
| 核心能力 | 通過限制/轉發底層容器接口實現特定數據結構 |
| 價值 | 代碼復用 + 接口統一 + 靈活切換 |
| 哲學思想 | “不要重復發明輪子”（Don’t Reinvent The Wheel） |
| 典型應用 | 算法中的臨時數據結構（DFS/BFS）、消息系統、撤銷操作棧 |
? 使用口訣：
棧用 vector，隊列用 deque
優先隊列 vector，底層切換要合規
迭代遍歷不可為，專用接口記心間！
仿函數
一、什么是仿函數？
仿函數（Function Object）是C++中行為類似函數的對象。它們通過重載函數調用運算符operator()實現，使得對象可以像函數一樣被調用。
基本特征：
- 是類對象，不是函數
- 重載了
operator()運算符 - 可以保存狀態（成員變量）
- 可以作為參數傳遞
- 可以像普通函數一樣調用
簡單示例：
#include <iostream>// 定義一個加法仿函數
struct Adder {int operator()(int a, int b) const {return a + b;}
};int main() {Adder add; // 創建仿函數對象std::cout << add(3, 4); // 像函數一樣調用：輸出7return 0;
}
二、為什么需要仿函數？
1. 相比普通函數的優勢：
| 特性 | 普通函數 | 仿函數 |
|---|---|---|
| 狀態保持 | ? 無狀態 | ? 可保存狀態 |
| 內聯優化 | ? 通常不能 | ? 可內聯 |
| 作為模板參數 | ? 不支持 | ? 支持 |
| 多態行為 | ? 不支持 | ? 支持 |
2. 實際應用場景：
- STL算法的自定義行為（如排序、查找）
- 回調機制
- 策略模式實現
- 函數組合
三、仿函數的類型分類
1. 按參數數量分類：
| 類型 | 參數數量 | 示例 |
|---|---|---|
| 生成器（Generator） | 0 | rand() |
| 一元仿函數（Unary） | 1 | negate<T>() |
| 二元仿函數（Binary） | 2 | plus<T>() |
2. 按行為分類：
| 類型 | 返回值 | 用途 | 示例 |
|---|---|---|---|
| 算術仿函數 | 數值 | 數學運算 | plus, minus |
| 關系仿函數 | bool | 比較操作 | less, greater |
| 邏輯仿函數 | bool | 邏輯運算 | logical_and, logical_or |
四、STL內置仿函數詳解
STL在<functional>頭文件中提供了常用仿函數：
1. 算術仿函數：
#include <functional>std::plus<int> add;
int result = add(5, 3); // 8std::minus<int> subtract;
result = subtract(10, 4); // 6std::multiplies<int> multiply;
result = multiply(3, 4); // 12std::divides<int> divide;
result = divide(10, 2); // 5std::modulus<int> mod;
result = mod(10, 3); // 1std::negate<int> neg;
result = neg(7); // -7
2. 關系仿函數：
std::equal_to<int> equal;
bool isEqual = equal(5, 5); // truestd::not_equal_to<int> notEqual;
isEqual = notEqual(5, 3); // truestd::greater<int> greater;
isEqual = greater(5, 3); // truestd::less<int> less;
isEqual = less(3, 5); // truestd::greater_equal<int> ge;
isEqual = ge(5, 5); // truestd::less_equal<int> le;
isEqual = le(4, 5); // true
3. 邏輯仿函數：
std::logical_and<bool> and_op;
bool res = and_op(true, false); // falsestd::logical_or<bool> or_op;
res = or_op(true, false); // truestd::logical_not<bool> not_op;
res = not_op(true); // false
五、自定義仿函數實現
1. 基本實現：
// 冪運算仿函數
class Power {
public:double operator()(double base, int exponent) const {double result = 1.0;for (int i = 0; i < exponent; ++i) {result *= base;}return result;}
};// 使用
Power power;
double eight = power(2, 3); // 8.0
2. 帶狀態的仿函數：
// 計數器仿函數
class Counter {int count = 0;
public:int operator()() { return ++count; }void reset() {count = 0;}
};// 使用
Counter c;
c(); // 1
c(); // 2
c.reset();
c(); // 1
3. 模板仿函數：
template <typename T>
class Clamp {T min_val;T max_val;
public:Clamp(T min, T max) : min_val(min), max_val(max) {}T operator()(T value) const {if (value < min_val) return min_val;if (value > max_val) return max_val;return value;}
};// 使用
Clamp<int> intClamp(0, 100);
int value = intClamp(150); // 100Clamp<double> doubleClamp(0.0, 1.0);
double dval = doubleClamp(-0.5); // 0.0
六、仿函數在STL算法中的應用
1. 排序算法：
#include <algorithm>
#include <vector>std::vector<int> numbers = {5, 3, 8, 1, 4};// 升序排序
std::sort(numbers.begin(), numbers.end(), std::less<int>());// 降序排序
std::sort(numbers.begin(), numbers.end(), std::greater<int>());
2. 查找算法：
// 查找第一個大于5的元素
auto it = std::find_if(numbers.begin(), numbers.end(), [](int x) { return x > 5; });// 使用仿函數替代lambda
struct GreaterThan {int threshold;GreaterThan(int t) : threshold(t) {}bool operator()(int x) const { return x > threshold; }
};it = std::find_if(numbers.begin(), numbers.end(), GreaterThan(5));
3. 轉換算法：
#include <vector>
#include <cmath>struct SquareRoot {double operator()(double x) const {return std::sqrt(x);}
};std::vector<double> values = {1.0, 4.0, 9.0, 16.0};
std::vector<double> roots;// 計算平方根
std::transform(values.begin(), values.end(), std::back_inserter(roots), SquareRoot());
七、仿函數適配器
1. 綁定器（Binder）：
#include <functional>
#include <algorithm>using namespace std::placeholders; // 用于 _1, _2 等占位符// 綁定第一個參數為10
auto greaterThan10 = std::bind(std::greater<int>(), _1, 10);std::vector<int> data = {5, 12, 8, 15, 3};
int count = std::count_if(data.begin(), data.end(), greaterThan10); // 2
2. 取反器（Negator）：
// 創建不等于5的謂詞
auto notEqual5 = std::not1(std::bind2nd(std::equal_to<int>(), 5));count = std::count_if(data.begin(), data.end(), notEqual5); // 4
八、仿函數 vs Lambda表達式
比較：
| 特性 | 仿函數 | Lambda表達式 |
|---|---|---|
| 語法簡潔性 | ? 需要完整類定義 | ? 簡潔 |
| 狀態管理 | ? 顯式成員變量 | ? 捕獲列表 |
| 復用性 | ? 可多次使用 | ? 通常一次性 |
| 模板支持 | ? 完全支持 | ?? C++20起支持 |
| 調試 | ? 更容易 | ? 匿名類型 |
轉換示例：
// Lambda表達式
auto lambda = [](int a, int b) { return a * b; };// 等效仿函數
class Multiplier {
public:int operator()(int a, int b) const {return a * b;}
};
九、高級技巧與最佳實踐
1. 函數組合：
template <typename F, typename G>
class Compose {F f;G g;
public:Compose(F f, G g) : f(f), g(g) {}template <typename T>auto operator()(T x) const -> decltype(f(g(x))) {return f(g(x));}
};// 使用：先平方再取負
Compose<std::negate<double>, std::multiplies<double>> squareAndNegate(std::negate<double>(), std::multiplies<double>());double result = squareAndNegate(4.0); // -16.0
2. 性能優化：
- 聲明
operator()為inline - 對于簡單操作，使用空仿函數（無狀態）
- 優先傳遞仿函數對象而非函數指針
3. 現代C++改進（C++11/14/17/20）：
- 自動類型推導：
auto關鍵字簡化聲明 - 泛型Lambda（C++14）：
auto genericAdder = [](auto a, auto b) { return a + b; }; - 模板Lambda（C++20）：
auto templated = []<typename T>(T a, T b) { return a + b; };
十、實際應用案例
1. 自定義排序：
struct Person {std::string name;int age;double salary;
};// 多級排序仿函數
class PersonSorter {
public:bool operator()(const Person& a, const Person& b) const {// 先按年齡升序if (a.age != b.age) return a.age < b.age;// 年齡相同按薪資降序if (a.salary != b.salary)return a.salary > b.salary;// 最后按名字升序return a.name < b.name;}
};std::vector<Person> people;
std::sort(people.begin(), people.end(), PersonSorter());
2. 策略模式實現：
// 支付策略接口
class PaymentStrategy {
public:virtual double calculate(double amount) const = 0;virtual ~PaymentStrategy() = default;
};// 信用卡支付策略
class CreditCardStrategy : public PaymentStrategy {double feeRate;
public:CreditCardStrategy(double rate) : feeRate(rate) {}double calculate(double amount) const override {return amount * (1 + feeRate);}
};// 支付處理器
class PaymentProcessor {PaymentStrategy* strategy;
public:void setStrategy(PaymentStrategy* s) { strategy = s; }double processPayment(double amount) {return strategy->calculate(amount);}
};
總結：仿函數的優勢與選擇
何時使用仿函數：
- 需要保持狀態或多次復用
- 作為模板參數傳遞
- 需要復雜的行為或策略
- 需要多態行為
- 性能敏感場景（內聯優化）
何時使用Lambda：
- 簡單、一次性操作
- 需要捕獲局部變量
- 代碼簡潔性優先
- C++11及以上環境
仿函數設計原則：
- 保持
operator()為const（除非需要修改狀態） - 提供清晰的命名
- 確保無副作用（或明確文檔說明）
- 對于模板仿函數，提供類型約束（C++20概念）
：一款從編輯器腳本發展起來的編程語言)
