読み込み中...

【C++】priority_queueの使い方5選

C++のpriority_queueの使い方を紹介する記事のサムネイル C++
2024.03.30
この記事は約20分で読めます。

【サイト内のコードはご自由に個人利用・商用利用いただけます】

この記事では、プログラムの基礎知識を前提に話を進めています。

説明のためのコードや、サンプルコードもありますので、もちろん初心者でも理解できるように表現してあります。

本記事のサンプルコードを活用して機能追加、目的を達成できるように作ってありますので、是非ご活用ください。

※この記事は、一般的にプロフェッショナルの指標とされる『実務経験10,000時間以上』を満たす現役のプログラマチームによって監修されています。

※Japanシーモアは、常に解説内容のわかりやすさや記事の品質に注力しております。不具合、分かりにくい説明や不適切な表現、動かないコードなど気になることがございましたら、記事の品質向上の為にお問い合わせフォームにてご共有いただけますと幸いです。
(送信された情報は、プライバシーポリシーのもと、厳正に取扱い、処分させていただきます。)

はじめに

この記事を読めば、C++のpriority_queueをマスターできるようになります。

C++を学ぶ上で、データ構造は欠かせない部分です。

特にpriority_queueは、効率的なデータの管理と処理に非常に役立つため、この機会にしっかりと理解し、実践で使えるようになりましょう。

●C++のpriority_queueとは

priority_queueは、特定の規則に従って整列されたデータの集合を扱うためのデータ構造です。

C++の標準テンプレートライブラリ(STL)に含まれるこの構造は、内部的には通常ヒープを用いて実装されます。

それにより、最大値や最小値を迅速に取り出す操作が可能となり、多くのアルゴリズムやアプリケーションで利用されます。

priority_queueは、要素を追加する際に自動的に優先順位に基づいて整列されます。

この優先順位はデフォルトでは要素の大きさに基づいていますが、カスタムの比較関数を定義することで変更することもできます。

○priority_queueの内部構造と動作原理

priority_queueの内部では、通常ヒープというデータ構造が使用されます。

ヒープは、木構造の一種で、特定の順序特性（例えば、任意の親ノードはその子ノードより大きい、あるいは小さい）を持つことによって、優先度の高い要素を迅速に取り出すことができるようになっています。

ヒープにおける要素の追加や削除は、木の再構築を伴うため、これらの操作は対数時間で実行されます。

この特性により、priority_queueは多くのデータを扱う際にも高いパフォーマンスを発揮します。

また、C++のpriority_queueはテンプレートを用いることで、様々なデータ型に対応しています。

デフォルトでは大きい要素が優先されますが、std::greater<データ型>などの比較関数を指定することで、小さい要素を優先するなどの動作をカスタマイズすることが可能です。

●priority_queueの基本的な使い方

C++のpriority_queueは、効率的に最大値または最小値を管理するのに適したデータ構造です。

基本的な使い方を理解することで、データの優先度に基づく処理を簡単に行うことができます。

ここでは、priority_queueの追加と取得について具体的に見ていきましょう。

まず、priority_queueの宣言方法についてです。

priority_queueは、テンプレートクラスであり、次のようにして宣言します。

   std::priority_queue<データ型> queue名;

ここでのデータ型には、整数型(int)や浮動小数点型(double)など、任意の型を指定することができます。

○サンプルコード1：基本的な追加と取得

ここでは、priority_queueに要素を追加し、最大値を取得する基本的な方法を紹介します。

下記のサンプルコードでは、整数型のpriority_queueを使用しています。

   #include <iostream>
   #include <queue>

   int main() {
       std::priority_queue<int> pq;
       pq.push(10); // 10を追加
       pq.push(5);  // 5を追加
       pq.push(20); // 20を追加

       // priority_queueは、デフォルトで最大値を優先するため、
       // ここでは20が最大値として取り出される
       std::cout << "最大値: " << pq.top() << std::endl; // 出力: 最大値: 20

       pq.pop(); // 最大値を削除

       // 次の最大値は10になる
       std::cout << "次の最大値: " << pq.top() << std::endl; // 出力: 次の最大値: 10
       return 0;
   }

このコードでは、10、5、20をpriority_queueに追加しています。

priority_queueはデフォルトで最大値を先頭に配置するため、最初に20が取り出され、次に10が取り出されることを表しています。

○サンプルコード2：カスタム比較関数を使用する

priority_queueは、比較関数をカスタマイズすることで、異なる優先順位のルールを適用することができます。

たとえば、小さい数値を優先するように設定することも可能です。

下記のサンプルコードでは、std::greaterを用いて小さい数値を優先するpriority_queueを作成しています。

   #include <iostream>
   #include <queue>
   #include <functional> // std::greaterのためのヘッダ

   int main() {
       // 小さい数値を優先するpriority_queue
       std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
       pq.push(10);
       pq.push(5);
       pq.push(20);

       // ここでは5が最小値として取り出される
       std::cout << "最小値: " << pq.top() << std::endl; // 出力: 最小値: 5

       pq.pop(); // 最小値を削除

       // 次の最小値は10になる
       std::cout << "次の最小値: " << pq.top() << std::endl; // 出力: 次の最小値: 10
       return 0;
   }

この例では、std::greaterを比較関数として使用しており、最小値が優先されます。

そのため、5、10、20の順に要素が取り出されることがわかります。

●priority_queueでのエラーとその対処法

priority_queueを使用する際には、さまざまなエラーに遭遇する可能性があります。

これらのエラーを理解し、適切に対処することは、C++プログラミングの効率を高めるために非常に重要です。

ここでは、priority_queueでよくあるエラーシナリオとその対処法について解説します。

○エラー例1：型不一致によるエラー

priority_queueはテンプレートを使用して宣言されるため、指定した型のオブジェクトのみを格納できます。

異なる型のオブジェクトを格納しようとすると、コンパイル時に型不一致エラーが発生します。

このエラーを避けるには、priority_queueに追加する要素が宣言した型と一致していることを確認する必要があります。

例えば、int型のpriority_queueにdouble型の数値を追加しようとすると、下記のようなコードではコンパイルエラーが発生します。

   #include <queue>
   int main() {
       std::priority_queue<int> pq;
       pq.push(3.14); // double型の値を追加しようとしてエラー
       return 0;
   }

このエラーを解決するためには、pushされる値がpriority_queueの型と一致していることを確認する必要があります。

例えば、この場合はpq.push(3);とすればエラーは発生しません。

○エラー例2：空のqueueからの要素取得

priority_queueから要素を取り出す際に、queueが空の状態でtop()やpop()を呼び出すと、ランタイムエラーが発生する可能性があります。

このエラーを防ぐためには、要素を取り出す前にqueueが空でないことを確認することが重要です。

下記のコード例では、空のpriority_queueから要素を取り出そうとしてエラーが発生しています。

   #include <iostream>
   #include <queue>
   int main() {
       std::priority_queue<int> pq;
       if (!pq.empty()) {
           std::cout << pq.top() << std::endl; // queueが空でなければ要素を取り出す
       } else {
           std::cout << "queueは空です。" << std::endl;
       }
       return 0;
   }

このコードでは、priority_queueが空の状態であるかをempty()関数でチェックしています。

空でない場合のみtop()を使用して要素を取り出し、空の場合はエラーメッセージを表示しています。

このように、条件分岐を使ってqueueが空である場合の処理を記述することで、ランタイムエラーを防ぐことができます。

●priority_queueの応用例

C++のpriority_queueは多様な応用が可能です。

ここでは、priority_queueを利用したいくつかの実用的な例を紹介します。

これらの例を通じて、priority_queueの使い方の幅が広がるでしょう。

○サンプルコード3：優先順位付きタスク管理

priority_queueは、優先順位が異なるタスクを管理するのに役立ちます。

例えば、異なる緊急度を持つタスクをpriority_queueで管理し、最も緊急度の高いタスクから処理するといった使い方ができます。

   #include <iostream>
   #include <queue>
   #include <string>

   struct Task {
       int priority;
       std::string name;
       bool operator<(const Task& a) const {
           return priority < a.priority;
       }
   };

   int main() {
       std::priority_queue<Task> tasks;
       tasks.push({3, "低優先度タスク"});
       tasks.push({1, "高優先度タスク"});
       tasks.push({2, "中優先度タスク"});

       while (!tasks.empty()) {
           Task t = tasks.top();
           tasks.pop();
           std::cout << t.name << " (" << t.priority << ")" << std::endl;
       }
       return 0;
   }

このサンプルコードでは、各タスクに優先度を割り当てています。

priority_queueは優先度が高い順にタスクを取り出すように設計されているため、このコードは最も優先度の高いタスクから処理されます。

○サンプルコード4：グラフアルゴリズムへの適用

priority_queueは、グラフ理論におけるアルゴリズム、例えば最短経路問題や最小全域木問題などで広く使用されます。

最短経路を見つけるためには、各ノードを優先度（距離）に応じて処理する必要があります。

   // このコードは、priority_queueを用いた最短経路探索の簡略化された例です。
   #include <iostream>
   #include <queue>
   #include <vector>

   struct Edge {
       int to;
       int weight;
   };

   int main() {
       const int INF = 1000000000;
       int n = 5; // ノードの数
       std::vector<std::vector<Edge>> graph(n);
       // グラフのデータをここに入力...

       std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
       pq.push({0, 0}); // スタート地点

       std::vector<int> dist(n, INF);
       dist[0] = 0;

       while (!pq.empty()) {
           auto [weight, u] = pq.top();
           pq.pop();
           if (dist[u] < weight) continue;
           for (auto& e : graph[u]) {
               int v = e.to;
               int w = e.weight;
               if (dist[v] > dist[u] + w) {
                   dist[v] = dist[u] + w;
                   pq.push({dist[v], v});
               }
           }
       }
       // 結果の出力...
       return 0;
   }

このサンプルでは、priority_queueを使用して、グラフ上の各ノードへの最短距離を求める処理を行っています。

最短経路アルゴリズムにおいて、priority_queueは各ノードを効率的に処理するのに役立ちます。

○サンプルコード5：カスタムデータ構造を使う

priority_queueはカスタムデータ構造にも対応しており、特定の基準に基づいて要素を整列させることができます。

例えば、特定の属性を持つオブジェクトのコレクションを管理する際に役立ちます。

   #include <iostream>
   #include <queue>

   struct Person {
       std::string name;
       int age;
       bool operator<(const Person& a) const {
           return age < a.age; // 年齢が若い順に優先
       }
   };

   int main() {
       std::priority_queue<Person> people;
       people.push({"Alice", 30});
       people.push({"Bob", 25});
       people.push({"Carol", 35});

       while (!people.empty()) {
           Person p = people.top();
           people.pop();
           std::cout << p.name << " (" << p.age << "歳)" << std::endl;
       }
       return 0;
   }

このコードでは、Person構造体を定義し、年齢を基準にしてpriority_queueで整列させています。

このように、priority_queueはオブジェクトの集合を特定の属性に基づいて効率よく処理するのに役立ちます。

●priority_queueのカスタマイズ

C++のpriority_queueはカスタマイズが可能で、多様な用途に合わせて挙動を変更できます。

特に、比較関数をカスタマイズすることで、様々な条件に基づいた優先度付けが実現可能です。

ここでは、priority_queueをカスタマイズするいくつかの方法を紹介します。

○カスタマイズ例1：逆順priority_queue

priority_queueはデフォルトでは最大値が先頭に来るように設計されていますが、逆順、つまり最小値が先頭に来るように変更することもできます。

これは比較関数をカスタマイズすることで実現できます。

   #include <iostream>
   #include <queue>
   #include <functional> // std::greaterを使用するために必要

   int main() {
       std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
       pq.push(10);
       pq.push(5);
       pq.push(20);

       while (!pq.empty()) {
           std::cout << pq.top() << std::endl;
           pq.pop();
       }
       return 0;
   }

このコードでは、std::greaterを使用して最小値を優先するように設定しています。

このため、priority_queueは5, 10, 20の順で要素が取り出されます。

○カスタマイズ例2：複数の基準での比較

priority_queueは、複数の基準で要素を比較するためのカスタム比較関数を設定することもできます。

これにより、より複雑な条件に基づいて優先度を決定することが可能になります。

例えば、Person構造体があり、名前と年齢の両方に基づいて優先度を決定したい場合、下記のようなカスタム比較関数を実装することができます。

   #include <iostream>
   #include <queue>
   #include <string>

   struct Person {
       std::string name;
       int age;
   };

   struct ComparePerson {
       bool operator()(const Person& a, const Person& b) {
           if (a.age == b.age) {
               return a.name > b.name; // 年齢が同じ場合は名前で比較
           }
           return a.age > b.age; // 年齢で比較
       }
   };

   int main() {
       std::priority_queue<Person, std::vector<Person>, ComparePerson> pq;
       pq.push({"Alice", 30});
       pq.push({"Bob", 25});
       pq.push({"Alice", 25});

       while (!pq.empty()) {
           Person p = pq.top();
           pq.pop();
           std::cout << p.name << " (" << p.age << "歳)" << std::endl;
       }
       return 0;
   }

このコードでは、年齢が同じ場合には名前の辞書順で優先度を決定し、そうでない場合は年齢が若い順に優先しています。

このように、カスタム比較関数を用いることで、複数の属性を基準にした複雑な優先度付けを行うことが可能です。

●エンジニアなら知っておくべきC++の小技

C++プログラミングにおいて、いくつかの小技を知っていると、コードの品質を向上させたり、開発プロセスを効率化できます。

ここでは、C++における有用な小技を2つ紹介します。

○小技1：効率的なメモリ管理

C++ではメモリ管理が非常に重要です。

特に、大きなデータ構造を扱う場合、メモリの割り当てと解放に注意する必要があります。

スマートポインタ（std::unique_ptrやstd::shared_ptrなど）を使用することで、メモリリークを防ぐことができます。

スマートポインタは、オブジェクトがもはや必要ない場合に自動的にメモリを解放します。

   #include <iostream>
   #include <memory>

   class MyClass {
   public:
       MyClass() { std::cout << "MyClassが生成されました。\n"; }
       ~MyClass() { std::cout << "MyClassが破棄されました。\n"; }
   };

   int main() {
       std::unique_ptr<MyClass> myClassPtr(new MyClass());
       // 何らかの処理...
       return 0;
   }

このコードでは、MyClassのインスタンスをstd::unique_ptrでラップしています。

このポインタがスコープ外に出ると、MyClassのインスタンスは自動的に破棄されます。

○小技2：STLアルゴリズムとの組み合わせ

C++の標準テンプレートライブラリ（STL）には、様々なアルゴリズムが含まれており、これらを使うことで効率的にコードを記述できます。

たとえば、std::sortでコンテナを簡単にソートしたり、std::findで要素を探索したりできます。

   #include <algorithm>
   #include <iostream>
   #include <vector>

   int main() {
       std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

       std::sort(vec.begin(), vec.end()); // ベクトルをソート
       for (int v : vec) {
           std::cout << v << " ";
       }
       std::cout << std::endl;

       auto result = std::find(vec.begin(), vec.end(), 5);
       if (result != vec.end()) {
           std::cout << "5はベクトル内に存在します。\n";
       } else {
           std::cout << "5はベクトル内に存在しません。\n";
       }
       return 0;
   }

この例では、std::sortを使用してベクトルをソートし、std::findを使用して特定の値を探しています。

STLアルゴリズムを使うことで、複雑な操作をシンプルで読みやすいコードで実現できます。

まとめ

この記事では、C++のpriority_queueの基本的な使い方から応用例、エラー処理、さらにはカスタマイズ方法までを詳細に解説しました。

また、効率的なメモリ管理やSTLアルゴリズムとの組み合わせといった小技も紹介しました。

これらの知識を身につけることで、C++プログラミングの効率と品質を大きく向上させることができます。

プログラミングにおける課題解決やデータ処理の幅が広がり、より複雑な問題に対応できるようになるでしょう。