一、仿函数（Functor）详解

1. 什么是仿函数？

仿函数，本质上就是重载了 operator() 的类 / 结构体，它的对象可以像普通函数一样被调用，因此也叫 “函数对象”。

它比普通函数更灵活，可以保存状态、适配 STL 算法和容器的自定义规则。

// 1. 普通函数版比较
bool compare(int a, int b) {
    return a > b;
}

// 2. 仿函数版比较（核心：重载operator()）
struct CompareGreater {
    bool operator()(int a, int b) const {
        return a > b; // 实现"大于"比较逻辑
    }
};

2. 仿函数的核心作用：自定义规则

仿函数最常见的用途，就是为 STL 容器 / 算法提供自定义的比较规则，比如：

• 让 set/map 从默认升序改成降序
• 让 priority_queue 从默认大顶堆改成小顶堆
• 为 sort/find_if 提供复杂的判断逻辑

3. 练习：用仿函数实现 “大于” 比较

你课程里的 “练习中使用大于比较的仿函数”，核心就是为容器 / 算法提供降序规则，我们用 set 举个例子：

#include <iostream>
#include <set>
using namespace std;

// 自定义"大于"仿函数（降序比较）
struct CompareGreater {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

int main() {
    // 1. 默认升序的set（用less<int>，等价于默认）
    set<int, less<int>> s1{3,1,4,2};
    cout << "升序set：";
    for (int x : s1) cout << x << " "; // 输出：1 2 3 4
    cout << endl;

    // 2. 用自定义仿函数实现降序set
    set<int, CompareGreater> s2{3,1,4,2};
    cout << "降序set：";
    for (int x : s2) cout << x << " "; // 输出：4 3 2 1
    cout << endl;

    return 0;
}

这里的 CompareGreater 就是仿函数，它替代了默认的 less<int>，让 set 按照降序排列。

---

二、容器适配器（Container Adapter）详解

容器适配器，就是对已有 STL 容器的封装，提供特定接口，实现特定数据结构，它本身不是独立容器，而是基于其他容器的 “包装器”。

STL 提供了 3 种标准容器适配器：

1. stack：栈（后进先出 LIFO）
2. queue：队列（先进先出 FIFO）
3. priority_queue：优先级队列（按优先级排序，默认大顶堆）

---

1. stack 与 queue 适配器详解

（1）stack（栈）

• 底层默认容器：deque（也可以用 vector）
• 核心接口：push()（入栈）、pop()（出栈）、top()（取栈顶）、empty()/size()
• 特点：只能操作栈顶元素，不支持遍历、不支持随机访问

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;

    // 入栈
    s.push(1);
    s.push(2);
    s.push(3);

    // 出栈（后进先出，3先出）
    while (!s.empty()) {
        cout << s.top() << " "; // 输出：3 2 1
        s.pop();
    }
    return 0;
}

（2）queue（队列）

• 底层默认容器：deque（也可以用 list）
• 核心接口：push()（入队尾）、pop()（出队头）、front()（取队头）、back()（取队尾）
• 特点：只能操作队头和队尾，不支持遍历、不支持随机访问

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;

    // 入队
    q.push(1);
    q.push(2);
    q.push(3);

    // 出队（先进先出，1先出）
    while (!q.empty()) {
        cout << q.front() << " "; // 输出：1 2 3
        q.pop();
    }
    return 0;
}

---

2. priority_queue 优先级队列详解

（1）基础特性

• 底层默认容器：vector
• 默认规则：大顶堆（队头是最大元素），默认用 less<T> 作为比较规则
• 核心接口：push()（入队）、pop()（出队头）、top()（取队头）
• 关键：它的比较规则和 set/map 相反，需要结合仿函数理解

（2）仿函数与优先级队列的关系

priority_queue 的模板定义是：

template <class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue;

• 当使用默认 less<T> 时，队列是大顶堆（队头最大）
• 当使用 greater<T> 仿函数时，队列是小顶堆（队头最小）

（3）练习：自定义优先级队列

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // 1. 默认大顶堆（队头是最大元素）
    priority_queue<int> pq1;
    pq1.push(3); pq1.push(1); pq1.push(4);
    cout << "大顶堆出队顺序：";
    while (!pq1.empty()) {
        cout << pq1.top() << " "; // 输出：4 3 1
        pq1.pop();
    }
    cout << endl;

    // 2. 用greater仿函数实现小顶堆（队头是最小元素）
    priority_queue<int, vector<int>, greater<int>> pq2;
    pq2.push(3); pq2.push(1); pq2.push(4);
    cout << "小顶堆出队顺序：";
    while (!pq2.empty()) {
        cout << pq2.top() << " "; // 输出：1 3 4
        pq2.pop();
    }
    return 0;
}

这里的 greater<int> 就是一个标准仿函数，它改变了 priority_queue 的比较规则，实现了小顶堆。

3. 自定义容器适配器（拓展）

“自定义容器适配器”，核心就是基于已有容器，封装出自己的适配器接口，比如实现一个固定大小的栈：

#include <iostream>
#include <vector>
using namespace std;

// 自定义栈适配器，底层用vector实现
template <class T, class Container = vector<T>>
class MyStack {
private:
    Container c;
public:
    // 核心接口封装
    void push(const T& x) { c.push_back(x); }
    void pop() { c.pop_back(); }
    T& top() { return c.back(); }
    bool empty() { return c.empty(); }
    size_t size() { return c.size(); }
};

int main() {
    MyStack<int> s;
    s.push(10);
    s.push(20);
    cout << "栈顶元素：" << s.top() << endl; // 输出20
    s.pop();
    cout << "出栈后栈顶元素：" << s.top() << endl; // 输出10
    return 0;
}