std::priority_queue

std::priority_queue を試してみます。

 

 

 

std::priority_queue
ヘッダ <queue> で定義
template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;		  

 

テンプレート引数
T - 要素の型
Container - 要素を格納するために使用するベースとなるコンテナの型。コンテナは SequenceContainer の要件を満たさねばならず、そのイテレータは LegacyRandamAccessIterator の要件を満たさなければなりません。さらに、通常のセマンティクスを持つ以下の関数を提供していなければなりません。
  • front()
  • push_back()
  • pop_back()
標準のコンテナ std::vector および std::deque はこれらの要件を満たします。
Compare - 狭義弱順序を提供する Compare 型。

 

Compare 引数は弱順序で第１引数が第２引数よりも前にくる場合に true を返すように定義されていることに注意してください。
しかし優先度付きキューは最も大きな要素を最初に出力するため、「前にくる」要素は実際には最後に出力されます。つまり、Compare によって定める弱順序に従って「最後」の要素がキューの先頭に格納されます。

 

 

1. 始めに

[概要]

まずは単純に、数字をいろいろ push してから top/pop してみます。
これで priority_queue の基本動作がわかると思います。

 

[環境]

コンパイラ : g++, 9.3.0
OS : Ubuntu (WSL2),  20.04

 

[プログラムソース]

#include <iostream>
#include <queue>
#include <vector>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue q;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2}){
        q.push(n);
    }
 
    print_queue(q);
}

 

[出力]

9 8 7 6 5 4 3 2 1 0

 

なるほど、デフォルトでは大きい順になるみたいですね。

 

 

2. 逆順にする - Compare に std::greater を指定する

[概要]

Compare に std::greater を指定して出力を逆順にしてみます。

 

[環境]

コンパイラ : g++, 9.3.0
OS : Ubuntu (WSL2),  20.04

 

[プログラムソース]

#include <iostream>
#include <queue>
#include <vector>  // vector
#include <functional>  // greater
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2);
}

 

[出力]

0 1 2 3 4 5 6 7 8 9

 

逆順で出力することができました。
なるほど、priority_queue の説明に書かれていた意味が少しわかってきました。greater を設定したら小さい値が先頭に入る、という機能は直観的な動作とは逆になるようですね。

 

 

3. Compare を独自に指定する

[概要]

Compare に 独自の処理を指定します。lambda式で定義してみます。

 

[環境]

コンパイラ : g++, 9.3.0
OS : Ubuntu (WSL2),  20.04

 

[プログラムソース]

#include <iostream>
#include <queue>
#include <vector>  // vector
#include <functional>  // greater
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    auto cmpFunc = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(comFunc)> q3(cmpFunc);
    
    for(int n : {1,8,5,6,3,4,0,9,7,2}){
        q3.push(n);
    }
 
    print_queue(q3);
}

 

[出力]

8 9 6 7 4 5 2 3 0 1

 

 

 

参考

 

 

記載

2020-12-19 - 新規作成