priority_queue クラス

最も大きい (または最も優先度の高い) 要素に常にアクセスできる要素のコレクションを保持するコンテナー アダプター。 新しい要素を追加したり、最上位の要素を削除したり調べたりすることはできますが、コレクションの中央にある要素に直接アクセスすることはできません。

構文

template <class Type, class Container= vector <Type>, class Compare= less <typename Container ::value_type>>
class priority_queue

パラメーター

Type
priority_queueに格納する要素データ型。

Container
priority_queueの要素を格納する基になるコンテナーの型。

Compare
2 つの要素値を並べ替えキーとして比較して、 priority_queue内の相対的な順序を決定する関数オブジェクトを提供する型。 この引数は省略可能です。 既定では、二項述語 less<typename Container::value_type> が使用されます。

解説

priority_queue オブジェクトの最初のテンプレート パラメーターで指定Typeクラスの要素は、value_typeと同じであり、基になるコンテナー クラスの要素型と一致Container、2 番目のテンプレート パラメーターで指定する必要があります。 Typeは代入可能である必要があります。つまり、その型のオブジェクトをコピーし、その型の変数に値を割り当てることができます。

priority_queueでは、比較関数を使用して、どの要素の優先度が高いかを判断します。 この比較関数は、クラス Traitsの関数オブジェクトです。 priority_queueを操作するには、要素を順番に配置できるように、より小さい演算子 (<) を使用した比較のみをサポートする必要があります。

priority_queueで使用される基になるコンテナーの種類を変更できます。 パフォーマンス上の理由から、これを行うことをお勧めします。 要素は連続したストレージに格納され、増加するにつれて割り当てが少なくなるため、既定の vectorは通常、キャッシュの局所性に最適です。 しかし、非常に大きいキューや無制限のキューがあり、要素の移動にコストがかかる場合は、 deque を検討することをお勧めします。 適切な基になるコンテナー クラスの詳細については、「 container_type」を参照してください。

priority_queueの要素の追加と削除の両方に対数の複雑さがあります。 priority_queue 内の要素へのアクセスには、定数の複雑さがあります。

C++ 標準ライブラリでは、 priority_queueに要素を格納するために使用できる他のコンテナー アダプター ( stack、 queue、 priority_queue) が定義されています。

• stack クラスは、後入れ先出し (LIFO) のデータ構造をサポートしています。 プレートのスタックについて考えてみましょう。要素 (プレート) を挿入、検査、または削除できるのは、ベース コンテナーの最後の要素であるスタックの上部からのみ行うことができます。
• queue クラスは、先入れ先出し (FIFO) のデータ構造をサポートしています。 一列に並びの人を考えてみましょう。 行の背面に要素 (ユーザー) を追加し、行の先頭から削除します。 線の前面と背面の両方を検査できます。
• priority_queue クラスは、最も大きい要素が常に最上位になるように要素を並べ替えます。 要素の挿入、および先頭の要素の検査と削除をサポートしています。

例示

• priority_queueが空かどうかを確認する
• 要素をポップしてキューのサイズを確認する
• カスタム コンテナーと比較子を使用する
• 要素をプッシュして上部を読み取る
• 要素の数を取得する
• 最上位の要素にアクセスする
• priority_queue value_type エイリアスを使用する
• ユーザー定義データ型を使用する

コンストラクター

コンストラクター	説明
priority_queue	空であるか、基本のコンテナー オブジェクトまたはその他の priority_queue の範囲のコピーである priority_queue を構築します。

Typedefs

型名	説明
container_type	priority_queueが適応する基本コンテナーを提供する型。
size_type	priority_queue 内の要素の数を表すことができる符号なし整数型。
value_type	priority_queue 内に要素として格納されるオブジェクトの種類を表す型。

メンバー関数

メンバー関数	説明
empty	priority_queue が空かどうかをテストします。
pop	最上位から priority_queue の最大の要素を削除します。
push	operator< からの要素の優先順位に基づいて、優先順位キューに要素を追加します。
size	priority_queue 内の要素数を返します。
top	priority_queue の最上位にある最大要素への const 参照を返します。

要件

ヘッダー: <queue>

名前空間: std

priority_queue::container_type

適合されるように、基本のコンテナーを提供する型。

typedef Container container_type;

解説

この型は、テンプレート パラメーター Containerのシノニムです。

priority_queueに適した基になるコンテナー クラスには、deque クラス、既定のvector クラス、またはfront、push_back、およびpop_backの操作とランダム アクセス反復子をサポートするその他のシーケンス コンテナーが含まれます。 コンテナー アダプターは、基になるコンテナー クラスをカプセル化し、シーケンス コンテナー メンバー関数の限られたセットのみをパブリック インターフェイスとして公開します。

container_typeを宣言して使用する方法の例については、「カスタム コンテナーと比較子を使用する」を参照してください。

priority_queue::empty

priority_queue が空かどうかをテストします。

bool empty() const;

戻り値

true が空の場合は priority_queue。false が空でない場合は priority_queue。

例: priority_queue が空かどうかを確認する

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue <int> q1, s2;

   q1.push(1);

   if (q1.empty())
      cout << "The priority_queue q1 is empty." << endl;
   else
      cout << "The priority_queue q1 is not empty." << endl;

   if (s2.empty())
      cout << "The priority_queue s2 is empty." << endl;
   else
      cout << "The priority_queue s2 is not empty." << endl;
}

The priority_queue q1 is not empty.
The priority_queue s2 is empty.

priority_queue::pop

最上位から priority_queue の最大の要素を削除します。

void pop();

解説

このメンバー関数を使用するには、 priority_queue が空でない必要があります。 priority_queueの上部には、常にコンテナー内の最大の要素が保持されます。

例: ポップ要素とチェック サイズ

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, s2;

   q1.push(10);
   q1.push(20);
   q1.push(30);

   priority_queue <int>::size_type i, iii;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;

   q1.pop();

   iii = q1.size();
   cout << "After a pop, the priority_queue length is " << iii << "." << endl;

   const int& iv = q1.top();
   cout << "After a pop, the element at the top of the " << "priority_queue is " << iv << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.
After a pop, the priority_queue length is 2.
After a pop, the element at the top of the priority_queue is 20.

priority_queue::priority_queue

空の priority_queue 、または基本コンテナー オブジェクトまたは別の priority_queueから範囲をコピーするを作成します。

priority_queue();

explicit priority_queue(const Traits& _comp);

priority_queue(const Traits& _comp, const container_type& _Cont);

priority_queue(const priority_queue& right);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp, const container_type& _Cont);

パラメーター

_comp
constTraits 内の要素の並べ替えに使用される、priority_queue 型の比較関数。既定では基本コンテナーの関数を比較します。

_Cont
構築される priority_queue のコピー元となる基本コンテナー。

right
構築される map のコピー元となる priority_queue。

first
コピーする要素範囲内の最初の要素の位置。

last
コピーする要素範囲を超える最初の要素の位置。

解説

最初の 3 つの各コンストラクターは、空の初期 priority_queue を指定します。2 番目のコンストラクターも要素の順序を確立するために使用する比較関数の型 (comp) を指定し、3 番目のコンストラクターは使用する container_type (_Cont) を明示的に指定します。 キーワード explicit は、特定の種類の自動型変換が実行されないようにします。

4 番目のコンストラクターは、priority_queue right のコピーを指定します。

最後の 3 つのコンストラクターは、一部のコンテナーの範囲 [first, last) をコピーし、値を使用して、より明確に priority_queue クラスの比較関数の型と Traits が指定されるように container_type を初期化します。

例: カスタム コンテナーと比較子を使用する

// compile with: /EHsc
#include <queue>
#include <vector>
#include <deque>
#include <list>
#include <iostream>

int main()
{
   using namespace std;

   // Declares a priority_queue with a default vector base container
   priority_queue <int> q1;
   cout << "q1 = ( ";
   while (!q1.empty())
   {
      cout << q1.top() << " ";
      q1.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue with nondefault deque base container
   priority_queue <int, deque <int>> q2;
   q2.push(5);
   q2.push(15);
   q2.push(10);
   cout << "q2 = ( ";
   while (!q2.empty())
   {
      cout << q2.top() << " ";
      q2.pop();
   }
   cout << ")" << endl;
   cout << "After printing, q2 has " << q2.size() << " elements." << endl;

   // Declares a priority_queue with a vector base container and specifies that
   // the comparison function greater is to be used for ordering elements
   priority_queue <int, vector<int>, greater<int>> q3;
   q3.push(2);
   q3.push(1);
   q3.push(3);
   cout << "q3 = ( ";
   
   while (!q3.empty())
   {
      cout << q3.top() << " ";
      q3.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue and initializes it with elements copied from another
   // container by first inserting elements into q1 and then copying q1 elements into q4
   q1.push(100);
   q1.push(200);
   priority_queue <int> q4(q1);
   cout << "q4 = ( ";
   while (!q4.empty())
   {
      cout << q4.top() << " ";
      q4.pop();
   }
   cout << ")" << endl;

   // Creates an auxiliary vector object v5 to be used to initialize q5
   vector <int> v5;
   vector <int>::iterator v5_Iter;
   v5.push_back(10);
   v5.push_back(30);
   v5.push_back(20);
   cout << "v5 = ( " ;
   for (v5_Iter = v5.begin() ; v5_Iter != v5.end() ; v5_Iter++)
   {
      cout << *v5_Iter << " ";
   }
   cout << ")" << endl;

   // Declares and initializes a priority_queue q5 by copying the
   // range v5[ first,  last) from vector v5
   priority_queue <int> q5(v5.begin(), v5.begin() + 2);
   cout << "q5 = ( ";
   while (!q5.empty())
   {
      cout << q5.top() << " ";
      q5.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue q6 with a comparison function greater and
   // initializes q6 by copying the range v5[ first,  last) from vector v5
   priority_queue <int, vector<int>, greater<int>> q6(v5.begin(), v5.begin() + 2);
   cout << "q6 = ( ";
   while (!q6.empty())
   {
      cout << q6.top() << " ";
      q6.pop();
   }
   cout << ")" << endl;
}

priority_queue::push

operator< からの要素の優先順位に基づいて、優先順位キューに要素を追加します。

void push(const Type& val);

パラメーター

val
priority_queueの先頭に追加する要素。

解説

priority_queueの上部には、コンテナー内の最大の要素が含まれています。

例: 要素をプッシュして先頭を読み取る

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::size

priority_queue 内の要素数を返します。

size_type size() const;

戻り値

priority_queue の現在の長さ。

例: 次の要素の数を取得します。 priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, q2;
   priority_queue <int>::size_type i;

   q1.push(1);
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   q1.push(2);
   i = q1.size();
   cout << "The priority_queue length is now " << i << "." << endl;
}

The priority_queue length is 1.
The priority_queue length is now 2.

priority_queue::size_type

priority_queue内の要素の数を表す符号なし整数型。

typedef typename Container::size_type size_type;

解説

この型は、priority_queueが適応する基本コンテナーのsize_typeのシノニムです。

例: Top 要素にアクセスする

size_typeを宣言して使用する方法の例については、「要素の数を取得する」を参照してください。

priority_queue::top

priority_queue の最上位にある最大要素への const 参照を返します。

const_reference top() const;

戻り値

Traits 関数によって決定される priority_queue オブジェクトの最大要素への参照。

解説

このメンバー関数を使用するには、 priority_queue が空でない必要があります。

例: 次の最上位要素を取得します。 priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::value_type

priority_queue 内に要素として格納されるオブジェクトの種類を表す型。

typedef typename Container::value_type value_type;

解説

この型は、priority_queueが適応する基本コンテナーのvalue_typeのシノニムです。

例: priority_queue value_type エイリアスを使用する

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue<int>::value_type AnInt;

   AnInt = 69;
   cout << "The value_type is AnInt = " << AnInt << endl;

   priority_queue<int> q1;
   q1.push(AnInt);
   cout << "The element at the top of the priority_queue is " << q1.top() << "." << endl;
}

The value_type is AnInt = 69
The element at the top of the priority_queue is 69.

例: ユーザー定義データ型を使用する

ユーザー定義型要素で priority_queue を使用するには、要素を比較する方法を提供する必要があります。 型の operator< を定義することも、カスタム比較関数オブジェクトを指定することもできます。

次の例は、優先度レベルで並べ替えられたTaskオブジェクトを格納するpriority_queueを示しています。 優先順位の高い値を持つタスクは、キューの一番上にあります。

// compile with: /EHsc
#include <queue>
#include <iostream>
#include <string>

struct Task
{
    int priority;
    std::string name;

    // Define operator< for priority_queue ordering
    // Returns true if this task has LOWER priority than other
    // (priority_queue puts the "largest" element at the top)
    bool operator<(const Task& other) const
    {
        return priority < other.priority;
    }
};

int main()
{
    std::priority_queue<Task> tasks;

    tasks.push({3, "Low priority task"});
    tasks.push({10, "High priority task"});
    tasks.push({5, "Medium priority task"});

    std::cout << "Processing tasks by priority:\n";
    while (!tasks.empty())
    {
        const Task& t = tasks.top();
        std::cout << "  Priority " << t.priority << ": " << t.name << "\n";
        tasks.pop();
    }
}

Processing tasks by priority:
  Priority 10: High priority task
  Priority 5: Medium priority task
  Priority 3: Low priority task

解説

異なる順序 (たとえば、最初に小さい値) が必要な場合は、カスタム比較子を指定します。

struct ComparePriority
{
    bool operator()(const Task& a, const Task& b)
    {
        return a.priority > b.priority; // Lower priority value means higher priority
    }
};

std::priority_queue<Task, std::vector<Task>, ComparePriority> minQueue;

関連項目

C++ 標準ライブラリ内のスレッド セーフ
C++ 標準ライブラリ リファレンス