C++ 容器适配器：从接口到实现，理解 stack、queue 和 priority_queue

优先队列（priority_queue）

优先队列要比前两个复杂得多。它默认使用 vector，依靠堆算法维护优先级。除了容器，还多了一个比较器的模板参数，默认是 Less，建大根堆。如果你想要小根堆，可以传入 Greater。

void test01() {
    priority_queue<int> pq; // 默认大堆
    pq.push(5); pq.push(2); pq.push(4);
    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }
}

仿函数（Functor）

为了允许自定义排序规则，C++ 把比较逻辑包装成一个可调用对象，也就是重载了 operator() 的类。比如 Less 和 Greater：

template<class T>
class Less {
public:
    bool operator()(const T& x, const T& y) {
        return x < y; // 看似'小于'，但在此语境下建大堆
    }
};

template<class T>
class Greater {
public:
    bool operator()(const T& x, const T& y) {
        return x > y; // 建小堆
    }
};

注意：Less 使用 < 比较，实际配合下面的堆调整代码构建的是大根堆（堆顶最大），而 Greater 用 > 则得到小根堆。命名与直接语义有点出入，但这是标准库的惯例，理解调整算法后自然明白。

完整模拟实现

下面是对三个适配器的整体模拟，放在了 hds 命名空间里。为了方便演示，这里用了 using namespace std，实际工程中建议避免。

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

// 仿函数定义
template<class T>
class Less {
public:
    bool operator()(const T& x, const T& y) {
        return x < y;
    }
};

template<class T>
class Greater {
public:
    bool operator()(const T& x, const T& y) {
        return x > y;
    }
};

namespace hds {
    // Stack 实现
template<class T, class Container = deque<T>>
class stack {
public:
    void push(const T& x) { _con.push_back(x); }
    const T& top()const { return _con.back(); }
    void pop() { _con.pop_back(); }
    bool empty()const { return _con.empty(); }
    size_t size()const { return _con.size(); }
private:
    Container _con;
};

    // Queue 实现
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()const { return _con.front(); }
    const T& back()const { return _con.back(); }
    bool empty()const { return _con.empty(); }
    size_t size()const { return _con.size(); }
private:
    Container _con;
};

    // Priority Queue 实现
template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue {
public:
    size_t size()const { return _con.size(); }
    const T& top() { return _con.front(); }
    
    void push(const T& x) {
        _con.push_back(x);
        AdjustUp(_con.size() - 1);
    }

    void pop() {
        swap(_con[0], _con[_con.size() - 1]);
        _con.pop_back();
        AdjustDown(0);
    }

    bool empty()const { return _con.empty(); }

private:
    Container _con;

    // 向上调整
    void AdjustUp(int child) {
        Compare com;
        int parent = (child - 1) / 2;
        while (child >= 0) {
            if (com(_con[parent], _con[child])) {
                swap(_con[parent], _con[child]);
                child = parent;
                parent = (child - 1) / 2;
            } else break;
        }
    }

    // 向下调整
    void AdjustDown(int parent) {
        Compare com;
        int child = 2 * parent + 1;
        while (child < _con.size()) {
            if ((child + 1) < _con.size() && com(_con[child], _con[child + 1])) {
                child++;
            }
            if (com(_con[parent], _con[child])) {
                swap(_con[parent], _con[child]);
                parent = child;
                child = 2 * parent + 1;
            } else break;
        }
    }
};
}

自己动手写过一遍，就能感受到适配器不过是在现有容器上套了一层壳，再加上特定的规则（比如堆调整）。知道这些，选型时心里更有底。默认 deque 的栈和队列通常足够快，但如果你需要连续内存，用 vector 做栈的底层有时缓存更友好——这也算一种微优化技巧。