C++ で STL 優先キューを使用する
-
C++ で
std::priority_queueを使用して優先キューを宣言する - C++ でテンプレート引数を使用し順序付け関数を指定する
- C++ でカスタムコンパレータを使用して要素の順序を指定する
この記事では、C++ で STL 優先キューを使用する方法に関する複数の方法を示します。
C++ で std::priority_queue を使用して優先キューを宣言する
std::priority_queue クラスは、要素が優先度に従って読み取られるキューを実装するコンテナアダプタです。priority_queue は要素の内部で任意のシーケンスコンテナを利用でき、ユーザーは 2 番目のテンプレートパラメータとして優先コンテナを渡すことができることに注意してください。後者のパラメーターが指定されていない場合、デフォルトで vector コンテナーが使用されます。
priority_queue の要素は、queue コンテナと同じ関数を使用して操作されます。push メンバー関数は新しい要素をキューに挿入し、top 関数はトップ要素にアクセスします。これらの 2つの関数は、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++ でテンプレート引数を使用し順序付け関数を指定する
各要素の優先度は、ユーザーがオプションで指定できる比較機能を使用して決定されます。それ以外の場合は、デフォルトで降順が選択されます。3 番目のテンプレートパラメータとして 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 を定義します。次に、ラムダ式を定義してコンパレータ関数を形成します。後者は、2つの文字列を長さで比較します。これで、要素タイプ、基になるコンテナタイプ、およびコンパレータ関数をそれぞれ指定する 3つのテンプレートパラメータを使用して、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,
