priority_queue

[機能]

  優先順位付き待ち行列を保持します.要素を追加すると,優先順位に従いソートされます.STL コンテナの一部を利用して,特別な機能を持たせたクラスであり,コンテナアダプタと呼ばれています.Container は queue を実際に保持するコンテナであり,省略すると vector になります.Comp に対しては,比較を行う二項関数オブジェクト名を指定します.指定しないと less (この場合は,降順)が選択されます.
template <class T, class Container = vector<T>, class Comp = less<Container::value_type> > class priority_queue
		

[使用方法]
#include <queue>
using namespace std;
priority_queue <T, Container, Comp> 変数名;
		
[メンバー関数等]

[使用例]

  1. priority_queue の使用方法です.
    #include <stdio.h>
    #include <queue>
    using namespace std;
    
    void print1(priority_queue<int> &q) {
    	if (q.empty())
    		printf("   priority_queue は空です\n");
    	else
    		printf("   先頭の要素: %d\n", q.top());
    }
    
    void print2(priority_queue<int, vector<int>, greater<int> > &q) {
    	if (q.empty())
    		printf("   priority_queue は空です\n");
    	else
    		printf("   先頭の要素: %d\n", q.top());
    }
    
    int main()
    {
    	printf("less の場合\n");
    	priority_queue<int, vector<int>, less<int> > q1;
    					// push
    	q1.push(1);
    	print1(q1);
    	q1.push(3);
    	print1(q1);
    	q1.push(2);
    	print1(q1);
    					// pop
    	q1.pop();
    	print1(q1);
    	q1.pop();
    	print1(q1);
    	q1.pop();
    	print1(q1);
    
    	printf("\ngreater の場合\n");
    	priority_queue<int, vector<int>, greater<int> > q2;
    					// push
    	q2.push(1);
    	print2(q2);
    	q2.push(3);
    	print2(q2);
    	q2.push(2);
    	print2(q2);
    					// pop
    	q2.pop();
    	print2(q2);
    	q2.pop();
    	print2(q2);
    	q2.pop();
    	print2(q2);
    
    	return 0;
    }
    			
    (出力)
    less の場合
       先頭の要素: 1
       先頭の要素: 3
       先頭の要素: 3
       先頭の要素: 2
       先頭の要素: 1
       priority_queue は空です
    
    greater の場合
       先頭の要素: 1
       先頭の要素: 1
       先頭の要素: 1
       先頭の要素: 2
       先頭の要素: 3
       priority_queue は空です
    			
  2. priority_queue の使用方法です.クラス Test における整数値の和が小さいものがトップに来ます.
    #include <stdio.h>
    #include <queue>
    #include <string>
    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)
    		{
    			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);
    					// 二項関数オブジェクトを利用する場合
    	priority_queue<Test, vector<Test>, GT> q;
    					// < 演算子のオーバーロードを利用する場合
    //	priority_queue<Test> q;
    					// push
    	q.push(t1);
    	q.push(t2);
    	q.push(t2);
    	q.push(t3);
    					// 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("%d %d\n", (q.top()).n1, (q.top()).n2);
    	q.pop();
    
    	return 0;
    }
    			
    (出力)
    30 10
    30 10
    20 30
    40 50
    			
[参照]

setmultimapbitsetdequelistmapmultisetpairqueuestackstringvector

菅沼ホーム 本文目次 演習問題解答例 付録目次 索引