priority_queue クラス

[機能]

　　優先順位付き待ち行列を保持します．要素を追加すると，優先順位に従いソートされます（デフォルトでは降順）．STL コンテナの一部を利用して，特別な機能を持たせたクラスであり，コンテナアダプタと呼ばれています．Container は queue を実際に保持するコンテナであり，省略すると vector になります．Comp に対しては，比較を行う二項関数オブジェクト名を指定します．指定しないと less （この場合は，降順）が選択されます．なお，以下に示す関数において，一般に，push よりも，emplace を使ったほうが処理効率は良くなります．

template <class T, class Container = vector<T>,
class Comp = less<Container::value_type>>
    class priority_queue		

[使用方法]

#include <queue>
using namespace std;
priority_queue <T> 変数名;
   priority_queue x;   // 空の priority_queue
   priority_queue x(y.it1, y.it2);   // it1 から it2 の範囲で初期化
   priority_queue x(y);   // priority_queue y で初期化		

[メンバー関数等]

• template <class... Args> void emplace(Args&&... args) // C++11
  直接構築で　priority_queue に要素を追加する（コピーもムーブもされない）．また，以下の 2 行目に示すように，ペアーを自動的に生成するような処理も可能である（ push との違いに注意）．

  	priority_queue<pair<int, double>> q;
  	q.emplace(5, 3.14);
  	q.emplace(make_pair(1, 4.55));
  //	q.push(10, 1.23);   // error
  	q.push(make_pair(3, 10.23));
  	while (!q.empty()) {
  		cout << "(" << q.top().first << ", " << q.top().second << ")"<< endl;
  		q.pop();
  	}
  	cout << endl;			

• bool empty()
  コンテナが空か否かを返す

• void pop()
  先頭の要素を削除する

• void push(const value_type& x)
  要素を追加する

• size_type size()
  要素数を返す

• void swap(priority_queue& other) // C++11
  2 つのコンテナの内容を入れ替える

• const_reference top()
  次に処理する要素（先頭の要素）を返す．要素は削除されない．

[演算子の多重定義]

=		

[使用例]

1. priority_queue の使用方法です．以下に示すプログラム例において，いくつかのコメント部分は，コメントの前に記述された方法とほぼ同等なものであることを示しています．

   #include <iostream>
   #include <queue>
   #include <vector>
   
   using namespace std;
   
   void print(priority_queue<int, vector<int>, greater<int>> &q) {
   	if (q.empty())
   		cout << "   priority_queue は空です\n";
   	else
   		cout << "   先頭の要素： " << q.top() << endl;
   }
   
   void print(priority_queue<int> &q) {
   	if (q.empty())
   		cout << "   priority_queue は空です\n";
   	else
   		cout << "   先頭の要素： " << q.top() << endl;
   }
   
   int main()
   {
   					// push（降順）
   	priority_queue<int> q1;
   	cout << "**push（降順）**\n";
   	q1.push(1);   // q.emplace(1);
   	print(q1);
   	q1.push(3);   // q.emplace(3);
   	print(q1);
   	q1.push(2);   // q.emplace(2);
   	print(q1);
   					// vector による初期設定（昇順），二項関数オブジェクト greater
   	cout << "**vector による初期設定（昇順）q2**\n";
   	vector<int> y = {1, 3, 2};
   	priority_queue<int, vector<int>, greater<int>> q2(y.begin(), y.end());
   	print(q2);
   	q2.pop();
   	print(q2);
   	q2.pop();
   	print(q2);
   	q2.pop();
   	print(q2);
   					// swap（q1 と 空の q3, q1 を出力）
   	cout << "**swap（q1 と 空の q3, q1 を出力）**\n";
   	priority_queue<int> q3;
   	q1.swap(q3);
   	print(q1);
   					// pop q3
   	cout << "**pop q3**\n";
   	print(q3);
   	q3.pop();
   	print(q3);
   	q3.pop();
   	print(q3);
   	q3.pop();
   	print(q3);
   
   	return 0;
   }
   			

   （出力）

   **push（降順）**
      先頭の要素： 1
      先頭の要素： 3
      先頭の要素： 3
   **vector による初期設定（昇順）q2**
      先頭の要素： 1
      先頭の要素： 2
      先頭の要素： 3
      priority_queue は空です
   **swap（q1 と 空の q3, q1 を出力）**
      priority_queue は空です
   **pop q3**
      先頭の要素： 3
      先頭の要素： 2
      先頭の要素： 1
      priority_queue は空です
   			

   priority_queue の使用方法です．クラス Test における整数値の和が小さいものがトップに来ます．コメントとして記述してあるように，比較演算子のオーバーロード（多重定義）を行えば，二項関数オブジェクトを定義しなくても構いません．

   #include <stdio.h>
   #include <queue>
   #include <vector>
   
   using namespace std;
   
   class Test {
   	public:
   		int n1, n2;
   		Test (int m1, int m2) {
   			n1 = m1;
   			n2 = m2;
   		}
   };
   					// 二項関数オブジェクト
   class GT
   {
   	public:
   		bool operator() (Test t1, Test t2) const
   		{
   			return (t1.n1+t1.n2 > t2.n1+t2.n2) ? true : false;
   		}
   };
   					// < 演算子のオーバーロード
   //bool operator< (Test t1, Test t2)
   //{
   //	return (t1.n1+t1.n2 > t2.n1+t2.n2) ? true : false;
   //}
   
   int main()
   {
   	Test t1(20, 30), t2(30, 10), t3(40, 50);
   	vector<Test> v {t1, t2, t3};
   					// 二項関数オブジェクトを利用する場合
   	priority_queue<Test, vector<Test>, GT> q(v.begin(), v.end());
   					// < 演算子のオーバーロードを利用する場合
   //	priority_queue<Test> q(v.begin(), v.end());
   					// pop
   	printf("%d %d\n", (q.top()).n1, (q.top()).n2);
   	q.pop();
   	printf("%d %d\n", (q.top()).n1, (q.top()).n2);
   	q.pop();
   	printf("%d %d\n", (q.top()).n1, (q.top()).n2);
   	q.pop();
   	printf("size of q  = %d\n", q.size());
   
   	return 0;
   }
   			

   （出力）

   30 10
   20 30
   40 50
   size of q  = 0			

[参照]

vector， set， multimap， array， list， map， multiset， queue， deque， stack， forward_list， unordered_map， unordered_multimap， unordered_set， unordered_multiset