priority_queueで自作のクラスを使う

C++のSTLの中のpriority_pueue（優先順位付きキュー）について。自作のクラスのオブジェクトを要素にして、そのオブジェクトのメンバを基準に降順（または昇順）に格納する方法のメモ。

参考サイト：STL PRIORITY_QUEUE クラスを使用して、カスタムの型にする方法

priority_queueってなんだ

まず初めに、priority_queueを知らないという人のために軽く説明を。簡単に言えば、中に入っている要素を勝手にソートしておいてくれる便利な箱です。

アルゴリズムを多少でもかじったことがある人なら聞いたことがあるかと思いますが、ヒープと呼ばれるものですね。（より正確には、優先順序付きキューはヒープを使って実現できる、というだけですが）

要素の挿入・削除ごとに要素の順序を守るよう並び替えを行うことで、最大（または最小）の要素を、要素の総数に関係なく素早く取り出すことができる、というデータ構造です。

プログラマ観点だと、何も考えずにポイポイとオブジェクトを挿入するだけで、sort関数やらmax関数やらを駆使することなく常に最大（または最小）のオブジェクトを取り出せる、ということです。

priority_queueを使う

priority_queueで自分で作ったクラスのオブジェクトを扱いたいという場合、当然ですがそのまま挿入したところで上手いことソートしてくれるわけはありません。何を基準にソートすればいいかわかりませんからね。

ということで、以下、priority_queueでint型と自前のクラスそれぞれを扱う方法を見ていきます。

int型を扱う

ではまずint型から。

#include <queue>
#include <iostream>

int main(){
  // 宣言
  std::priority_queue<int> pqInt;

  // 要素の追加
  pqInt.push(20);
  pqInt.push(10);
  pqInt.push(30);

  // 要素の表示
  while(!pqInt.empty()){
    // 要素の参照
    std::cout << pqInt.top() << std::endl;
    // 要素の削除
    pqInt.pop();
  }

  return 0;
}

出力結果は以下の通り。

30
20
10

int型は簡単ですね。

自作のクラスを扱う

次に、自作のクラスを使う場合。以下のようなstudentクラス

#include <string>

class student{
public:
    std::string name; // 名前
    int num; // 学生番号
    student(std::string name, int num){ // コンストラクタ
        this->name = name;
        this->num = num;
    };
};

を考え、学生番号の降順に並べるとします。

ここでint型の場合と同じように宣言をするんですが、その前にオペランドのオーバーロードを行います。 studentクラスのインスタンス同士はそのままでは比較できないのでソートの基準を決めてやるということですね。

降順に並べ替えるためには “<（小なり）” をオーバーロードしておく必要があります。

// "<" のオーバーロード numを基準に大小比較を行う
bool operator< (const student &student1, const student &student2){
    return student1.num < student2.num;
};

これでようやくint型の時と同じように宣言して使用できます。

#include <queue>
#include <iostream>

int main(){
    // 宣言
    std::priority_queue<student> pqStu;

    // 要素の追加
    pqStu.push(student("taro", 2003));
    pqStu.push(student("jiro", 2001));
    pqStu.push(student("saburo", 2002));

    // 要素の表示
    while(!pqStu.empty()){
        std::cout << pqStu.top().name << ": " << pqStu.top().num << std::endl;
        pqStu.pop();
    }

    return 0;
}

出力結果は以下の通り。

taro: 2003
saburo: 2002
jiro: 2001

昇順にする場合

priority_queueはデフォルトでは降順に（先頭が最大となるように）格納されますが、昇順に格納したい！と思うこともあると思います。その場合は宣言のときに比較のための関数を指定します。

#include <queue>
#include <vector>
#include <iostream>

int main(){
    /* studentクラスのオブジェクトを昇順に */
    std::priority_queue< student,
                         std::vector<student>,
                         std::greater<student> > pqStu;

greaterを指定すると昇順（先頭が最小）、lessを指定すると降順（先頭が最大）となります。

ちなみに、自作のクラスを昇順にしたい場合は “>（大なり）” 演算子をオーバーロードしておく必要があります。

// ">" のオーバーロード numを基準に大小比較を行う
bool operator> (const student &student1, const student &student2){
    return student1.num > student2.num;
};