C++ STL 容器适配器：stack、queue 与 priority_queue 实现细节

代码中巧妙的地方很多：用模板参数 Ref 和 Ptr 来区分普通迭代器和 const 迭代器，+= 负责跨缓存块的移动，然后 +、-=、- 都复用它。前后置 ++/-- 也是先实现前置，后置调用前置，再返回临时对象。这种复用技巧很值得在自己的项目中借鉴。

stack 的模拟实现

有了 deque，实现 stack 就像给交流电换个插头。我们只需要把 deque 的接口映射过去：

#pragma once
#include <vector>
#include <list>
#include <deque>
using namespace std;
namespace wgm {
template<class T, class Container = deque<T>>
class stack {
public:
    void push(const T& val) { _con.push_back(val); }
    void pop() { _con.pop_back(); }
    bool empty() const { return _con.empty(); }
    size_t size() const { return _con.size(); }
    const T& top() const { return _con.back(); }
private:
    Container _con;
};
}

这里 push 用的是 push_back，pop 用的是 pop_back，完美适配后进先出。top() 返回 back()。简单到几乎不用解释。

queue 的模拟实现

queue 类似，但两端都要操作：队尾入队用 push_back，队头出队用 pop_front。注意，如果你把 Container 换成 vector，编译会报错，因为 vector 没有 pop_front，这也是为什么默认用 deque——它同时支持 push_back 和 pop_front。

#pragma once
#include <vector>
#include <list>
#include <deque>
using namespace std;
namespace wgm {
template<class T, class Container = deque<T>>
class queue {
public:
    void push(const T& val) { _con.push_back(val); }
    void pop() { _con.pop_front(); }
    bool empty() const { return _con.empty(); }
    size_t size() const { return _con.size(); }
    const T& front() const { return _con.front(); }
    const T& back() const { return _con.back(); }
private:
    Container _con;
};
}

priority_queue 优先队列

优先队列不太一样，它不像栈或队列只关心顺序，而是维护元素的优先级。通常用堆实现，默认大根堆（最大值在顶）。STL 给了我们另一个适配器 priority_queue，默认底层容器是 vector，比较器默认 less（但实际是大顶堆，注意比较器的语义是'严格小于'）。

接口跟 stack 很像：

• push(val)：插入并向上调整
• pop()：弹出堆顶并向下调整
• top()：返回堆顶引用
• empty()、size()

自己实现一个带调整逻辑的版本，能加深对堆的理解：

#pragma once
#include <vector>
#include <iostream>
using namespace std;
namespace wgm {
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; }
};
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {
public:
#define FATHER(i) (((i) - 1) / 2)
#define LEFT(i) (((i) * 2) + 1)
#define RIGHT(i) (((i) * 2) + 2)

    void AdjustUp(int i) {
        Compare cmp;
        while (FATHER(i) >= 0 && Compare()(_con[FATHER(i)], _con[i])) {
            swap(_con[i], _con[FATHER(i)]);
            i = FATHER(i);
        }
    }
    void AdjustDown(int i) {
        while (LEFT(i) < _con.size()) {
            int l = LEFT(i), r = RIGHT(i), ind = i;
            Compare cmp;
            if (cmp(_con[ind], _con[LEFT(i)])) ind = LEFT(i);
            if (RIGHT(i) < _con.size() && cmp(_con[ind], _con[RIGHT(i)])) ind = RIGHT(i);
            if (ind == i) break;
            swap(_con[i], _con[ind]);
            i = ind;
        }
    }
    void push(const T& val) { _con.push_back(val); AdjustUp(_con.size() - 1); }
    void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); }
    bool empty() { return _con.empty(); }
    const T& top() { return _con[0]; }
    size_t size() { return _con.size(); }
private:
    Container _con;
};
}

这里的 AdjustUp 和 AdjustDown 就是经典的堆调整。Compare 默认是 less，意味着父节点要'小于'子节点时会交换，从而让大的往上浮，即大顶堆。如果用 greater，则小的在上，变成小顶堆。

最后说一句：deque 的迭代器实现虽然只有两百多行，但把非类型模板参数、运算符重载复用、分段连续空间管理都揉在了一起，值得自己动手敲一遍。