C++ STL 容器适配器详解：stack、queue 与 priority_queue 原理

一、什么是容器适配器？

在 C++ 标准库中，**容器适配器（Container Adapters）**是一种基于现有容器实现的特殊容器，它们提供了更特定的接口和功能，隐藏了底层容器的部分特性，仅暴露适配后的操作方式。

⭐️容器适配器不直接存储数据，而是通过封装底层容器（如 vector、deque、list 等）来实现功能，底层容器可以通过模板参数指定（通常有默认值）。

C++中最常用的容器适配器有三种：std::stack（栈）；std::queue（队列)；std::priority_queue（优先队列）。

容器适配器的特点

接口简化：仅提供适配场景所需的操作（如 stack 没有迭代器，无法遍历内部元素）。

底层可配置：通过模板参数指定底层容器（需满足适配器的操作要求，如 stack 需要 push_back、pop_back 等接口）。

无迭代器：适配器不提供迭代器，无法像普通容器那样遍历元素，只能通过其特定接口操作。

栈和队列的接口比较简单，所以我们不再作介绍，具体接口可以通过上面的文档查看。下面我们直接模拟实现，来加深我们对这种特殊结构的理解！！！

**由于适配器的底层结构为其他容器（vector，list，deque...），像插入删除执行操作，其实是由底层的容器实现，所以，我们只需要运用底层容器的函数接口。**同样我们创建一个自己的命名空间，在自己的命名空间中写代码

二、3 大容器适配器

1、栈——stack

文档：栈（stack）

// 将 deque 作为默认容器
template<class T, class Container = deque<T>>
class stack {
public:
    // ...
private:
    Container _con; // 成员变量
};

成员变量其实就是我们通过底层容器实例化出的一个对象，我们只需要用这个对象来找到相应的函数接口。

2.1、在栈顶插入——push

void push(const T& x) { _con.push_back(x); }

2.2、获取有效数据个数——size

size_t size()const { return _con.size(); }

2.3、获取栈顶数据——top

const T& top()const { return _con.back(); }

2.4、删除栈顶数据——pop

void pop() { _con.pop_back(); }

2.5、判空——empty

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

2、队列——queue

文档：队列（queue）

// 将 deque 作为默认容器
template<class T, class Container = deque<T>>
class queue {
public:
    // ...
private:
    Container _con; // 成员变量
};

3.1、在队尾插入——push

void push(const T& x) { _con.push_back(x); }

3.2、删除队头数据——pop

void pop() { _con.pop_front(); }

3.3、获取有效数据个数——size

const size_t size()const { return _con.size(); }

3.4、获取队头数据——front

const T& front()const { return _con.front(); }

3.5、获取队尾数据——back

const T& back()const { return _con.back(); }

3.6、判空——empty

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

3、优先级队列——priority_queue

文档：priority_queue

1、priority_queue 介绍

priority_queue 底层选择用 vector 作为默认容器，它基于底层容器实现，能保证每次从顶部取出走的元素都是'优先级最高'的（默认是最大值）。其核心特性是通过 堆（heap）算法维护优先级（通常是大根堆，即最大值在顶部），插入元素后会自动调整结构以满足优先级规则。

即 priority_queue 的底层支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用 算法函数建堆（make_heap）、堆尾插入（push_heap）和堆顶删除（pop_heap）来自动完成此操作。

相关接口：

• empty()：检测容器是否为空
• size()：返回容器中有效元素个数
• top()：返回容器中第一个元素的引用
• push()：在队尾插入元素
• pop()：删除队头元素

2、特性测试

插入 5 个没有排好序的数进行排序：

void test01() {
    priority_queue<int> pq;
    pq.push(5);
    pq.push(2);
    pq.push(4);
    pq.push(3);
    pq.push(1);
    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }
}

priority_queue 底层默认建大堆，即输出结果为降序

void test02() {
    priority_queue<int, vector<int>, Greater<int>> pq; // Greater：建小堆
    pq.push(5);
    pq.push(2);
    pq.push(4);
    pq.push(3);
    pq.push(1);
    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }
}

这里需要注意：当我们建大堆时——降序；建小堆——升序。

3、模拟实现

/*第二个参数：默认适配容器为 vector 数组容器
第三个参数：采用仿函数，默认建大堆*/
template<class T,class Container = vector<T>,class Compare = Less<T>>
class priority_queue {
public:
    // ...
private:
    Container _con; // 成员变量
};

⭐️我们要用一个类实现建大堆和建小堆的功能，这里就需要仿函数（也就是类模板的第三个参数）来实现

/*为了能够满足 priority_queue 实现升序（建小堆）和降序（建大堆）的功能，我们实现两个仿函数的类作为 priority_queue 类模板的第三个参数
用于随时满足 priority_queue 实现升序和降序的效果*/
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;
    }
};

3.1、获取有效数据个数

size_t size()const { return _con.size(); }

3.2、获取队头数据

const T& top() { return _con.front(); }

3.3、队尾插入

在队尾插入数据后，堆的结构就可能被破坏，所以我们要向上调整建堆来维持数据的优先级。

// 向上调整建堆
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 push(const T& x) {
    _con.push_back(x);
    AdjustUp(_con.size() - 1);
}

3.4、队头删除

删除队头数据后，堆的结构被破坏，我们需要将最后一个数据放到原来第一个数据的位置，保证堆的剩余结构不被破坏，然后通过向下调整建堆的方式，维持数据的优先级。

// 向下调整建堆
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;
    }
}

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

3.5、判空

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

三、仿函数

在上面测试 priority_queue 以及实现 priority_queue 的 push 和 pop 时就使用了仿函数，因为，当我们想要让一组数升序排序或者降序排序时，我们不可能说去实现两个 priority_queue 的类，一个默认建大堆，降序排序；一个默认建小堆，升序排序。所以，C++引入了仿函数的概念，在实现类模板时，可以将仿函数作为模板参数，这样在我们使用时调用对应的仿函数，就能达到我们想要的效果。

1、什么是仿函数？

仿函数（Functor）：也称为函数对象（Function Object），是一种在 C++ 中通过类或结构体实现的可调用实体，其实就是一个类。

仿函数的核心特点是 重载了 operator() 运算符，使得类的对象可以像普通函数一样被调用。 仿函数是 C++ 中'以类模拟函数'的重要机制，这种机制结合了面向对象的封装性和函数的灵活性，在 STL 和算法中有着广泛应用。

仿函数的核心特点：

1. 重载 operator()

使用：

Add add; //创建仿函数对象
int result = add(2, 3); //像函数一样调用，结果为 5

通过在类中定义 operator() 运算符，使得该类的对象可以像函数一样被调用：

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

2、仿函数的使用⭐️

让冒泡排序既可以升序又可以降序排序：

#include <iostream>
using namespace std;

/*-----------------------第一部分：实现比较仿函数（类模板）-----------------------*/
template<class T>
class Less {
public:
    bool operator()(const T& x, const T& y) const //注意：加 const 提高通用性
    {
        return x < y;
    }
};
template<class T>
class Greater {
public:
    bool operator()(const T& x, const T& y) const
    {
        return x > y;
    }
};

/*-----------------------第二部分：实现冒泡排序（函数模板）-----------------------*/
template<class Compare>
void BubbleSort(int* a, int n, Compare com) {
    for (int i = 1; i <= n - 1; i++) {
        int flag = 1;
        for (int j = 1; j <= n - i; j++) {
            if (com(a[j], a[j - 1])) //用仿函数来比较 a[j] 和 a[j-1] 的大小
            {
                swap(a[j - 1], a[j]);
                flag = 0;
            }
            if (flag) break; //如果某一趟排序没有进行交换，说明当前数组中的元素已经有序了，直接退出
        }
    }
}

int main() {
    // 创建仿函数对象
    Less<int> less;
    Greater<int> greater;

    // 冒泡排序结合仿函数进行排序
    int a[] = { 9,1,2,8,5,7,4,6,3 };
    int n = sizeof(a) / sizeof(a[0]);

    //1.使用仿函数进行冒泡排序（升序/降序）
    BubbleSort(a, n, less); //仿函数 Less<int> less'进行升序排序
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    BubbleSort(a, n, greater); // 仿函数 Greater<int>进行降序排序
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    // 也可直接传递匿名对象（临时对象）
    BubbleSort(a, n, Less<int>()); // 升序
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    BubbleSort(a, n, Greater<int>()); // 降序
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

四、模拟实现完整代码

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

namespace hds {
    template<class T, class Container = deque<T>>
    class stack {
    public:
        stack() {}
        // 获取有效数据个数
        size_t size()const { return _con.size(); }
        // 获取栈顶数据
        const T& top()const { return _con.back(); }
        // 向栈顶插入数据
        void push(const T& x) { _con.push_back(x); }
        // 删除栈顶数据
        void pop() { _con.pop_back(); }
        // 判空
        bool empty() { return _con.empty(); }
    private:
        Container _con;
    };
}

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

// deque 是 vector 和 list 的混合
// deque 的头插和尾插，以及头删和尾删效率很高，更甚于 vector 和 list
// deque 的下标访问效率还行，略逊于 vector
// deque 在中间位置插入数据，效率极低
// 而栈和队列一般不会中间插入数据，所以 deque 作为栈和队列的默认容器非常合适
namespace hds {
    template<class T, class Container = deque<T>>
    class queue {
    public:
        queue() {}
        // 获取有效数据个数
        const size_t size()const { return _con.size(); }
        // 获取队头数据
        const T& front()const { return _con.front(); }
        // 获取队尾数据
        const T& back()const { return _con.back(); }
        // 再队尾插入数据（先进先出）
        void push(const T& x) { _con.push_back(x); }
        // 删除队头数据（先进先出）
        void pop() { _con.pop_front(); }
        // 判空
        bool empty() { return _con.empty(); }
    private:
        Container _con;
    };
}

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

// 仿函数：本质是一个类，这个类重载 operator(), 他的对象可以像函数一样使用
/*为了能够满足 priority_queue 实现升序（建小堆）和降序（建大堆）的功能，我们实现两个仿函数的类作为 priority_queue 类模板的第三个参数
用于随时满足 priority_queue 实现升序和降序的效果*/
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 {
    /*第二个参数：默认适配容器为 vector 数组容器
    第三个参数：采用仿函数，默认建大堆*/
    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 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 push(const T& x) {
            _con.push_back(x);
            AdjustUp(_con.size() - 1);
        }
        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;
            }
        }
        void pop() {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            AdjustDown(0);
        }
        bool empty()const { return _con.empty(); }
    private:
        Container _con;
    };
}