在 C++ 中使用 STL 优先队列

Jinku Hu 2023年10月12日
  1. 使用 std::priority_queue 在 C++ 中声明优先队列
  2. 在 C++ 中使用模板参数指定排序函数
  3. 在 C++ 中使用自定义比较器指定元素排序
在 C++ 中使用 STL 优先队列

本文将演示如何在 C++ 中使用 STL 优先级队列的多种方法。

使用 std::priority_queue 在 C++ 中声明优先队列

std::priority_queue 类是一个容器适配器,它实现了一个队列,根据它们的优先级从中读取元素。请注意,priority_queue 可以在内部为元素使用任何序列容器,并且用户可以将首选的作为第二个模板参数传递。如果未指定后一个参数,则默认使用 vector 容器。

priority_queue 的元素使用与 queue 容器相同的函数进行操作。push 成员函数向队列中插入一个新元素,top 函数访问顶部元素。这两个函数在 printQueue 函数中用于将元素输出到 cout 流。

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  std::priority_queue<int> q1;
  vector vec1 = {1, 8, 5, 6, 3, 7};

  for (int n : vec1) q1.push(n);

  printQueue(q1);

  return EXIT_SUCCESS;
}

输出:

8, 7, 6, 5, 3, 1,

在 C++ 中使用模板参数指定排序函数

每个元素的优先级是使用用户可以选择指定的比较函数来确定的。否则,默认选择降序。我们可以使用 std::greater 函数对象作为第三个模板参数,以相反的顺序从前面的示例代码中构造 priority_queue。请注意,新的队列容器是使用基于范围的构造函数初始化的。

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  std::priority_queue<int> q1;
  vector vec1 = {1, 8, 5, 6, 3, 7};

  std::priority_queue<int, vector<int>, std::greater<>> q2(vec1.begin(),
                                                           vec1.end());
  printQueue(q2);

  return EXIT_SUCCESS;
}

输出:

1, 3, 5, 6, 7, 8,

在 C++ 中使用自定义比较器指定元素排序

首先,我们定义一个用于初始化 priority_queue 的字符串 vector。接下来,定义一个 lambda 表达式以形成比较器函数。后者按长度比较两个字符串。现在,我们可以声明一个 priority_queue 对象,其中三个模板参数分别指定元素类型、底层容器类型和比较器函数。基于范围的构造函数用于初始化队列的内容。

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  vector vec2 = {"porro", "quisquam", "est", "qui", "dolorem", "ipsum", "quia"};
  auto compFunc = [](const string& s1, const string& s2) {
    return s1.length() < s2.length();
  };

  std::priority_queue<string, vector<string>, decltype(compFunc)> q3(
      vec2.begin(), vec2.end(), compFunc);

  printQueue(q3);

  return EXIT_SUCCESS;
}

输出:

quisquam, dolorem, ipsum, porro, quia, qui, est,
作者: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

DelftStack.com 创始人。Jinku 在机器人和汽车行业工作了8多年。他在自动测试、远程测试及从耐久性测试中创建报告时磨练了自己的编程技能。他拥有电气/电子工程背景,但他也扩展了自己的兴趣到嵌入式电子、嵌入式编程以及前端和后端编程。

LinkedIn Facebook

相关文章 - C++ Queue