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

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

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

// 将 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

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

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>, Great<int>> pq; // Great：建小堆
  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 Great {
 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;
}

四、模拟实现完整代码

stack.h

#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;
  };
}

queue.h

#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() {}
    // 获取有效数据个数
    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;
  };
}

priority_queue.h

#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 Great {
 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;
  };
}