在 C++ 中使用 STL 優先佇列
Jinku Hu
2023年10月12日
本文將演示如何在 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
