priority_queue | Programming Place Plus　C++編【標準ライブラリ】　第１２章

トップページ – C++編

C++編で扱っている C++ は 2003年に登場した C++03 という、とても古いバージョンのものです。C++ はその後、C++11 -> C++14 -> C++17 -> C++20 -> C++23 と更新されています。
なかでも C++11 での更新は非常に大きなものであり、これから C++ の学習を始めるのなら、C++11 よりも古いバージョンを対象にするべきではありません。特に事情がないなら、新しい C++ を学んでください。 当サイトでは、C++14 をベースにした新C++編を作成中です。

この章の概要 🔗

この章の概要です。


priority_queue 🔗

priority_queue は、コンテナアダプタの一種で、その名のとおり、優先度付きキュー（アルゴリズムとデータ構造編【データ構造】第１０章）を提供します。使用するには、queue（第１１章）と同じく、<queue> という名前の標準ヘッダをインクルードする必要があります（<priority_queue> ではありません）。

priority_queue は、次のように定義されています。

namespace std {
    template <typename T,
              typename Container = vector<T>,
              typename Compare = less<typename Container::value_type> >
    class priority_queue {
    };
}

テンプレート仮引数 T は、格納する要素の型です。

テンプレート仮引数 Container は、要素を格納するために内部で使用するコンテナを指定します。デフォルトでは、vector（第５章）が使用されます。Container には、deque（第７章） や list（第６章） のような他のコンテナを指定できます。

指定できるコンテナの種類には条件があり、push_backメンバ関数、pop_backメンバ関数、frontメンバ関数を持っている必要があります。結果的に、標準の STLコンテナとしては、vector、list、deque のいずれかから選択することになります。

テンプレート仮引数 Compare は、ソートの基準を指定します。デフォルトでは std::less（第１９章）が指定されていますが、これは、要素の大小関係の比較に <演算子を用いることを意味しています。つまり、T型の要素２つを <演算子で比較し、どちらがより小さいかを判断し、小さい方が手前に来るように並び替えます。したがって、デフォルトでは昇順にソートされます。

なお、ソートは安定（アルゴリズムとデータ構造編【整列】第０章）ではないので、同じ優先度を持った要素が複数ある場合、どちらが優先されるかは不定です。

なお、使用しているコンテナの型は、container_type という名前で型別名が与えられています。


サイズ 🔗

priority_queue の中に実際に存在している要素数が「サイズ」です。

現在の「サイズ」を知るには、sizeメンバ関数を使います。また、「サイズ」が 0 かどうかは、emptyメンバ関数で調べられます。空かどうかを知りたい場合は、効率面から、emptyメンバ関数を優先した方が良いです。

これらの関数は、内部で使用されているコンテナの同名関数を呼び出すように実装されます。C++03 時点の list においては、sizeメンバ関数の効率が悪い可能性があります（第６章参照）。

使用例としては、次のようになります。

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
    IntPrioQueue iPrioQueue;

    for (int i = 0; i < 5; ++i) {
        iPrioQueue.push(i);
    }

    std::cout << iPrioQueue.size() << "\n"
              << std::boolalpha << iPrioQueue.empty() << std::endl;
}

実行結果：

5
false

ソート基準 🔗

priority_queue のソート基準は、テンプレート実引数で指定するか、コンストラクタの引数で指定します。

まず、テンプレート実引数で指定する方法を見ていきましょう。

#include <iostream>
#include <queue>
#include <functional>

typedef std::priority_queue<int> IntPrioQueue;
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue;

int main()
{
    IntPrioQueue iPrioQueue1;
    IntReversePrioQueue iPrioQueue2;

    for (int i = 0; i < 5; ++i) {
        iPrioQueue1.push(i);
        iPrioQueue2.push(i);
    }

    while (!iPrioQueue1.empty()) {
        std::cout << iPrioQueue1.top() << " ";
        iPrioQueue1.pop();
    }
    std::cout << std::endl;
    while (!iPrioQueue2.empty()) {
        std::cout << iPrioQueue2.top() << " ";
        iPrioQueue2.pop();
    }
    std::cout << std::endl;
}

実行結果：

4 3 2 1 0
0 1 2 3 4

typedef によって、２つの型の別名を定義しています。IntPrioQueue の方は、ソート基準を定義していないので、デフォルト実引数 (std::less<>) が使用されます。この場合、ソートには <演算子が使用されることになり、int型の要素達は昇順に並びます。

IntReversePrioQueue の方は、ソート基準として std::greater<> を使用しました。こちらは、ソートに >演算子を使用するので、要素は降順に並びます。

std::less<> や std::greater<> は、標準の関数オブジェクトで、<functional> という標準ヘッダに定義されています。関数オブジェクトについては、第１９章で取り上げます。

２つの priority_queue は、共通の要素で初期化されていますが、要素を順番に出力してみると、逆の順序に並ぶことが分かります。topメンバ関数は、一番優先度が高い要素（キューの末尾にある要素）を返し、popメンバ関数は実際にキューから取り除きます。そのため、IntPrioQueue の方は、大きい数の要素から順に取り除かれ、IntReversePrioQueue の方は、小さい数の要素から順に取り除かれています。

このように、ソート基準をテンプレート実引数で指定する方法では、コンテナの型自体が異なったものになります。そのため、型の不一致がコンパイラによって検出されます。これは利点でもあるし、不便さが生まれることもあります。実際、型が違うため、要素を出力する部分の処理は、IntPrioQueue と intReversePrioQueue とで同じですが、テンプレートを使わない普通の関数にまとめることができません。

次に、コンストラクタの引数で指定する方法です。

#include <iostream>
#include <queue>

template <typename T>
class MyCompare {
public:
    enum Mode {
        MODE_NORMAL,
        MODE_REVERSE,
    };

public:
    explicit MyCompare(Mode mode = MODE_NORMAL) :
        mMode(mode)
    {}

    inline bool operator()(const T& a, const T& b) const
    {
        return mMode == MODE_NORMAL ? a < b : a > b;
    }

private:
    Mode    mMode;
};

typedef std::priority_queue<int, std::vector<int>, MyCompare<int> > IntPrioQueue;

void PrintAndClearIntPrioQueue(IntPrioQueue& iPrioQueue)
{
    while (!iPrioQueue.empty()) {
        std::cout << iPrioQueue.top() << " ";
        iPrioQueue.pop();
    }
    std::cout << std::endl;
}

int main()
{
    IntPrioQueue iPrioQueue1;
    IntPrioQueue iPrioQueue2((MyCompare<int>(MyCompare<int>::MODE_REVERSE)));

    for (int i = 0; i < 5; ++i) {
        iPrioQueue1.push(i);
        iPrioQueue2.push(i);
    }

    PrintAndClearIntPrioQueue(iPrioQueue1);
    PrintAndClearIntPrioQueue(iPrioQueue2);
}

実行結果：

4 3 2 1 0
0 1 2 3 4

この方法の場合は、ソート基準を表現する関数オブジェクトを独自で用意します。ここで用意した MyCompare は、コンストラクタに渡す引数によって、ソートの方法を切り替えられるようになっています。

priority_queue の２つ目のテンプレート仮引数には、MyCompare を指定しています。ソート基準は、コンストラクタで指定するので、priority_queue としては、１つの型で済みます。実際、要素を出力する部分を、PrintAndClearIntPrioQueue関数にまとめることができています。

上記サンプルプログラムで、iPrioQueue2 に渡す実引数全体が ( ) で囲まれていることに注意してください。これがないと、構文解析の問題で、コンパイルエラーになります。

なお、MyCompare に、デフォルトコンストラクタ（【言語解説】第１３章）がないと、priority_queue のコンストラクタで、必ず明示的にソート基準を指定しないといけなくなります。

生成と初期化 🔗

priority_queue には、複数のコンストラクタが定義されているので、さまざまな方法でインスタンス化できます。

#include <queue>
#include <vector>
#include <functional>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
    IntPrioQueue::container_type c;

    const int a[] = {4, 7, 2, 3, 5};

    IntPrioQueue iPrioQueue1;                                // 空
    IntPrioQueue iPrioQueue2((std::less<int>()));            // ソート基準を指定。要素は空
    IntPrioQueue iPrioQueue3(std::less<int>(), c);           // ソート基準を指定し、内部で使用しているコンテナと同種のコンテナからコピー
    IntPrioQueue iPrioQueue4(iPrioQueue3);                   // 他の priority_queue からコピー
    IntPrioQueue iPrioQueue5(a, a + 5);                      // ある範囲から要素を作成
    IntPrioQueue iPrioQueue6(a, a + 5, std::less<int>());    // ソート基準を指定し、ある範囲から要素を作成
    IntPrioQueue iPrioQueue7(a, a + 5, std::less<int>(), c); // ソート基準を指定し、内部で使用しているコンテナと同種のコンテナと、ある範囲から要素を作成
}

iPrioQueue2 は、ソート基準を指定しています。

iPrioQueue3 のように、第２引数で、内部で使用しているコンテナと同種のコンテナを指定でき、この場合、指定したコンテナの要素をコピーして、新しい priority_queue を生成します。内部で使用するコンテナの型は、std::priority_queue<>::container_type で得られます。

第１引数のところにソート基準の指定があるため、このスタイルで初期化するには、ソート基準の指定も行わないといけません。ソート基準を変更するつもりがないのなら、std::less<> を渡してください。

iPrioQueue5、iPrioQueue6、iPrioQueue7 は、２つのイテレータを使って表現される範囲内にある要素を使って初期化します。この３種のコンストラクタに関しては、テンプレートコンストラクタ（【言語解説】第２３章）になっており、priority_queue の要素の型と、イテレータが指す先の要素の型は、完全一致していなくても、変換可能であれば受け付けられます。

iPrioQueue7 については少しわかりにくいですが、第４引数で指定したコンテナのすべての要素と、第１，２引数で指定した範囲内の要素とを加えて初期化します。

STLコンテナの場合、コンストラクタからアロケータ（第３２章）を指定できますが、コンテナアダプタにはありません。コンテナアダプタの場合、使用するアロケータは、内部で使用しているコンテナ次第で決まります。

破棄 🔗

デストラクタでは、priority_queue（が内部で使用しているコンテナ）が確保した領域が破棄されます。

仮想デストラクタ（【言語解説】第２７章）ではないので、priority_queue を継承して使用することは不適切であることに注意してください。

比較 🔗

他のコンテナと違い、priority_queue 同士を ==、!=、<、<=、>、>= の各演算子で比較できません。

代入 🔗

queue は、テンプレート実引数が同一であれば、代入演算子を使ってコピーできます。

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

void PrintAndClearIntPrioQueue(IntPrioQueue& iPrioQueue)
{
    while (!iPrioQueue.empty()) {
        std::cout << iPrioQueue.top() << " ";
        iPrioQueue.pop();
    }
    std::cout << std::endl;
}

int main()
{
    const int a[] = {4, 7, 2, 3, 5};

    IntPrioQueue iPrioQueue(a, a + 5);
    IntPrioQueue iPrioQueue2;

    iPrioQueue2 = iPrioQueue;

    PrintAndClearIntPrioQueue(iPrioQueue);
    PrintAndClearIntPrioQueue(iPrioQueue2);
}

実行結果：

7 5 4 3 2
7 5 4 3 2

要素のアクセス 🔗

priority_queue は、格納されている要素の中で、もっとも優先度の高い要素にしかアクセスできません。このためには、topメンバ関数を使用します。

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
    IntPrioQueue iPrioQueue;

    for (int i = 0; i < 5; ++i) {
        iPrioQueue.push(i);
    }

    std::cout << iPrioQueue.top() << std::endl;

    std::cout << iPrioQueue.size() << std::endl;
}

実行結果：

4
5

topメンバ関数はもっとも優先度が高い要素の参照を返します。queue の場合と違って、constメンバ関数版しかありません。これは、要素を書き換えられてしまうと、優先度が変化してしまい、その後の挙動が不適切になる可能性があるためです。

参照で返されることから分かるように、ヌルを知ることはできませんから、空の priority_queue に対する topメンバ関数の呼び出しは、未定義の動作になることに注意してください。

上記のサンプルプログラムの sizeメンバ関数の結果の出力からも分かるように、topメンバ関数は、priority_queue から要素を取り出すわけではありません。要素を取り出したいのであれば、popメンバ関数を使う必要があります。

なお、topメンバ関数は、内部で使用しているコンテナの frontメンバ関数を呼び出す形で実装されます。

追加 🔗

priority_queue への要素の追加には、pushメンバ関数を使用します。順序は、優先度によってしか決定できないので、挿入位置を選択する余地はありません。

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
    IntPrioQueue iPrioQueue;

    for (int i = 0; i < 5; ++i) {
        iPrioQueue.push(i);
    }

    std::cout << iPrioQueue.size() << "\n"
              << std::boolalpha << iPrioQueue.empty() << std::endl;
}

実行結果：

5
false

なお、pushメンバ関数は、内部で使用しているコンテナの push_backメンバ関数を呼び出す形で実装されます。

削除 🔗

priority_queue から要素を削除するには、popメンバ関数を使用します。必ず、優先度が一番高い要素が削除されます。なお、priority_queue が空の場合に使用すると、未定義の動作となるので注意してください。

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
    IntPrioQueue iPrioQueue;

    for (int i = 0; i < 5; ++i) {
        iPrioQueue.push(i);
    }

    while (!iPrioQueue.empty()) {
        iPrioQueue.pop();
    }

    std::cout << iPrioQueue.size() << std::endl;
}

実行結果：

0

popメンバ関数の戻り値は void であり、何も返しません。もし、要素の値を知る必要があるのなら、先に topメンバ関数を使用するようにします。

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
    IntPrioQueue iPrioQueue;

    for (int i = 0; i < 5; ++i) {
        iPrioQueue.push(i);
    }

    while (!iPrioQueue.empty()) {
        std::cout << iPrioQueue.top() << "を取り除きます" << std::endl;
        iPrioQueue.pop();
    }
}

実行結果：

4を取り除きます
3を取り除きます
2を取り除きます
1を取り除きます
0を取り除きます

【上級】popメンバ関数が要素を返さないのは、例外安全（【言語解説】第３１章）を保証するためです。もし、popメンバ関数が戻り値を返すとすれば、それは格納されている要素の「コピー」になります（格納されている要素は削除したい訳だから）が、これを呼び出し元が受け取るまでの課程で例外が発生すると、削除してしまった要素が完全に失われてしまいます。

なお、popメンバ関数は、内部で使用しているコンテナの pop_backメンバ関数を呼び出す形で実装されます。


練習問題 🔗

問題①　要素の型が std::string で、文字列の長さが短いものほど優先度が高い priority_queue を作成してください。


解答ページはこちら。

参考リンク 🔗


更新履歴 🔗

　コンパイラの対応状況について、対応している場合は明記しない方針にした。

　clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。

　VisualC++ 2017 に対応。

　clang の対応バージョンを 3.7 に更新。

　新規作成。


前の章へ　（第１１章　queue）

次の章へ　（第１３章　bitset）

C++編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る