MENU
  1. ホーム
  2. C++
  3. C++のstd::priority_queueの活用方法を徹底解説：初心者から上級者まで

C++のstd::priority_queueの活用方法を徹底解説：初心者から上級者まで

C++

C++の標準ライブラリに含まれるstd::priority_queueは、効率的な優先度付きキューの実装を提供します。本記事では、std::priority_queueの基本概念から始まり、実際の使用例やカスタム比較関数を用いた高度な使用方法までを詳細に解説します。初心者でも理解しやすいように具体的なコード例を交えつつ、段階的に説明していきます。これを読めば、std::priority_queueを自在に操れるようになるでしょう。

目次

std::priority_queueの基礎

std::priority_queueは、C++標準ライブラリに含まれるコンテナアダプタで、要素を自動的に優先順位付きで管理します。デフォルトでは最大ヒープを使用し、最も高い優先度の要素が常にキューの先頭に来るようになっています。

priority_queueの宣言

std::priority_queueは以下のように宣言します。

#include <queue>
#include <vector>

std::priority_queue<int> pq;

このコードでは、int型の要素を持つ優先度キューpqを作成しています。

要素の追加と削除

priority_queueに要素を追加するにはpushメソッドを、先頭の要素を削除するにはpopメソッドを使用します。

pq.push(10);
pq.push(5);
pq.push(20);

pq.pop(); // 20が削除される

この例では、20が最も高い優先度を持つため、popメソッドで最初に削除されます。

先頭要素の取得

先頭の要素を取得するにはtopメソッドを使用します。

int topElement = pq.top(); // topElementは10になる

topメソッドは、最も高い優先度の要素を返しますが、キューからは削除しません。

優先度の設定方法

std::priority_queueのデフォルト動作では、要素の優先度はその大小関係に基づきます。しかし、カスタムの優先度を設定することも可能です。これにより、特定の条件に基づいて要素の優先順位を決定できます。

デフォルトの優先度

デフォルトでは、std::priority_queueは最大ヒープを使用し、最も大きい要素が常にキューの先頭に来るように動作します。これは、内部的にstd::lessを使用しているためです。

#include <queue>

std::priority_queue<int> pq;
pq.push(10);
pq.push(5);
pq.push(20);

int topElement = pq.top(); // topElementは20になる

最小ヒープの作成

最小ヒープを作成するには、std::greaterを使用します。これにより、最も小さい要素がキューの先頭に来るようになります。

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

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

int topElement = minHeap.top(); // topElementは5になる

カスタム比較関数の使用

カスタム比較関数を使用して、独自の優先度基準を設定することができます。例えば、構造体のメンバ変数に基づいて優先度を決定する場合などです。

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

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

struct CompareAge {
    bool operator()(Person const& p1, Person const& p2) {
        return p1.age > p2.age; // 年齢が低い方を優先する
    }
};

std::priority_queue<Person, std::vector<Person>, CompareAge> pq;
pq.push({"Alice", 30});
pq.push({"Bob", 25});
pq.push({"Charlie", 35});

Person topPerson = pq.top(); // topPersonはBobになる

このようにして、std::priority_queueは様々な優先度設定に対応できます。優先度をカスタマイズすることで、特定の条件に基づいたキュー操作が可能になります。

カスタム比較関数の使用

std::priority_queueでは、カスタム比較関数を用いることで、独自の基準に基づいて要素の優先順位を決定することができます。これは、特定の条件や要件に応じた柔軟なデータ管理を可能にします。

カスタム構造体と比較関数

カスタム構造体を定義し、その構造体に基づいた比較関数を作成します。以下の例では、タスク管理をシミュレートし、タスクの優先度に基づいて優先度キューを操作します。

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

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

    Task(std::string n, int p) : name(n), priority(p) {}
};

struct CompareTask {
    bool operator()(const Task& t1, const Task& t2) {
        return t1.priority < t2.priority; // 優先度が高いタスクを先に処理する
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, CompareTask> taskQueue;

    taskQueue.push(Task("Task1", 2));
    taskQueue.push(Task("Task2", 1));
    taskQueue.push(Task("Task3", 3));

    while (!taskQueue.empty()) {
        Task topTask = taskQueue.top();
        std::cout << "Processing " << topTask.name << " with priority " << topTask.priority << std::endl;
        taskQueue.pop();
    }

    return 0;
}

この例では、Taskという構造体を定義し、その中にタスクの名前と優先度を持たせています。CompareTaskという構造体は、operator()をオーバーロードしており、優先度の高いタスクが先に処理されるようにします。

ラムダ式を使用したカスタム比較関数

C++11以降では、ラムダ式を使用してカスタム比較関数を定義することも可能です。以下の例は、同様のタスク管理をラムダ式で実装したものです。

#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <functional>

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

    Task(std::string n, int p) : name(n), priority(p) {}
};

int main() {
    auto compare = [](const Task& t1, const Task& t2) {
        return t1.priority < t2.priority; // 優先度が高いタスクを先に処理する
    };

    std::priority_queue<Task, std::vector<Task>, decltype(compare)> taskQueue(compare);

    taskQueue.push(Task("Task1", 2));
    taskQueue.push(Task("Task2", 1));
    taskQueue.push(Task("Task3", 3));

    while (!taskQueue.empty()) {
        Task topTask = taskQueue.top();
        std::cout << "Processing " << topTask.name << " with priority " << topTask.priority << std::endl;
        taskQueue.pop();
    }

    return 0;
}

この例では、ラムダ式を用いてカスタム比較関数を定義し、std::priority_queueに渡しています。ラムダ式を使用することで、コードがより簡潔で読みやすくなります。

カスタム比較関数を用いることで、std::priority_queueは非常に柔軟で強力なデータ構造となります。これにより、特定の条件に基づいた優先度付けが可能になり、様々なアプリケーションで有効に活用できます。

priority_queueの操作

std::priority_queueを使用する際には、いくつかの基本操作を理解しておくことが重要です。ここでは、代表的な操作であるpush、pop、top、empty、およびsizeについて具体的なコード例を交えて解説します。

要素の追加 (push)

pushメソッドを使って、要素をpriority_queueに追加します。追加された要素は、自動的に適切な位置に配置されます。

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

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(5);
    pq.push(20);

    std::cout << "Top element: " << pq.top() << std::endl; // 出力: 20

    return 0;
}

この例では、pqに10、5、20の順に要素を追加しています。最も大きな要素である20がキューの先頭に来ます。

要素の削除 (pop)

popメソッドを使って、キューの先頭にある要素を削除します。削除される要素は最も高い優先度を持つ要素です。

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

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(5);
    pq.push(20);

    pq.pop(); // 20が削除される

    std::cout << "Top element after pop: " << pq.top() << std::endl; // 出力: 10

    return 0;
}

この例では、最も大きな要素20が削除された後、次に大きな要素10が先頭に来ます。

先頭要素の取得 (top)

topメソッドを使って、キューの先頭にある要素を取得します。topは要素を削除せずにその値を返します。

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

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(5);
    pq.push(20);

    int topElement = pq.top(); // topElementは20になる
    std::cout << "Top element: " << topElement << std::endl; // 出力: 20

    return 0;
}

この例では、topメソッドを使用して最も大きな要素である20を取得しています。

キューの空チェック (empty)

emptyメソッドを使って、キューが空かどうかを確認できます。空の場合はtrueを返します。

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;

    if (pq.empty()) {
        std::cout << "The priority queue is empty." << std::endl;
    } else {
        std::cout << "The priority queue is not empty." << std::endl;
    }

    pq.push(10);

    if (pq.empty()) {
        std::cout << "The priority queue is empty." << std::endl;
    } else {
        std::cout << "The priority queue is not empty." << std::endl;
    }

    return 0;
}

この例では、キューが空かどうかをemptyメソッドで確認しています。要素が追加された後は、キューは空でなくなります。

キューのサイズ取得 (size)

sizeメソッドを使って、キューに含まれる要素の数を取得します。

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(5);
    pq.push(20);

    std::cout << "Size of priority queue: " << pq.size() << std::endl; // 出力: 3

    pq.pop();

    std::cout << "Size after one pop: " << pq.size() << std::endl; // 出力: 2

    return 0;
}

この例では、最初に3つの要素を追加し、その後1つの要素を削除した後のキューのサイズを表示しています。

これらの基本操作を理解することで、std::priority_queueを効果的に活用することができます。次に、std::priority_queueを使用するために必要なヘッダーファイルと名前空間について説明します。

ヘッダーファイルと名前空間

std::priority_queueを使用するためには、特定のヘッダーファイルをインクルードし、適切な名前空間を使用する必要があります。これにより、C++標準ライブラリの一部として提供される機能にアクセスできるようになります。

必要なヘッダーファイル

std::priority_queueを使用するためには、以下のヘッダーファイルをインクルードする必要があります。

#include <queue>

このヘッダーファイルには、priority_queueに関連するすべての宣言が含まれています。また、priority_queueをサポートするために、必要に応じて他のヘッダーファイルもインクルードすることがあります。

#include <vector>   // コンテナを指定するため
#include <functional> // 比較関数を指定するため

名前空間の使用

std::priority_queueは、C++標準ライブラリの一部であるため、std名前空間に属しています。したがって、priority_queueを使用する際には、名前空間指定を行う必要があります。

std::priority_queue<int> pq;

名前空間の指定を省略するためには、usingディレクティブを使用することもできます。ただし、大規模なプロジェクトでは名前の衝突を避けるために、あまり推奨されません。

using namespace std;

priority_queue<int> pq;

完全な例

以下に、必要なヘッダーファイルと名前空間を含む完全な例を示します。

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

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

    Task(std::string n, int p) : name(n), priority(p) {}
};

struct CompareTask {
    bool operator()(const Task& t1, const Task& t2) {
        return t1.priority < t2.priority; // 優先度が高いタスクを先に処理する
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, CompareTask> taskQueue;

    taskQueue.push(Task("Task1", 2));
    taskQueue.push(Task("Task2", 1));
    taskQueue.push(Task("Task3", 3));

    while (!taskQueue.empty()) {
        Task topTask = taskQueue.top();
        std::cout << "Processing " << topTask.name << " with priority " << topTask.priority << std::endl;
        taskQueue.pop();
    }

    return 0;
}

この例では、priority_queueを使用するために必要なヘッダーファイルをインクルードし、標準ライブラリの名前空間を適切に使用しています。また、カスタム構造体と比較関数を定義し、優先度付きキューを操作しています。

これで、std::priority_queueを使用するための準備が整いました。次に、実際のアプリケーションでのpriority_queueの使用例について説明します。

優先度キューの実用例

std::priority_queueは、様々な実際のアプリケーションで非常に有用です。ここでは、いくつかの具体的な使用例を紹介します。

タスクスケジューリング

タスクスケジューリングシステムでは、異なる優先度を持つタスクを管理する必要があります。priority_queueを使用すると、優先度の高いタスクを常に先に処理できます。

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

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

    Task(std::string n, int p) : name(n), priority(p) {}
};

struct CompareTask {
    bool operator()(const Task& t1, const Task& t2) {
        return t1.priority < t2.priority; // 優先度が高いタスクを先に処理する
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, CompareTask> taskQueue;

    taskQueue.push(Task("Task1", 2));
    taskQueue.push(Task("Task2", 1));
    taskQueue.push(Task("Task3", 3));

    while (!taskQueue.empty()) {
        Task topTask = taskQueue.top();
        std::cout << "Processing " << topTask.name << " with priority " << topTask.priority << std::endl;
        taskQueue.pop();
    }

    return 0;
}

この例では、タスクスケジューリングシステムをシミュレートし、優先度に基づいてタスクを処理しています。

イベント駆動型システム

イベント駆動型システムでは、イベントの優先度に応じてイベントを処理する必要があります。priority_queueを使用することで、重要なイベントを優先して処理できます。

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

struct Event {
    std::string type;
    int priority;

    Event(std::string t, int p) : type(t), priority(p) {}
};

struct CompareEvent {
    bool operator()(const Event& e1, const Event& e2) {
        return e1.priority < e2.priority; // 優先度が高いイベントを先に処理する
    }
};

int main() {
    std::priority_queue<Event, std::vector<Event>, CompareEvent> eventQueue;

    eventQueue.push(Event("Event1", 5));
    eventQueue.push(Event("Event2", 2));
    eventQueue.push(Event("Event3", 8));

    while (!eventQueue.empty()) {
        Event topEvent = eventQueue.top();
        std::cout << "Processing " << topEvent.type << " with priority " << topEvent.priority << std::endl;
        eventQueue.pop();
    }

    return 0;
}

この例では、イベント駆動型システムをシミュレートし、イベントの優先度に基づいて処理を行っています。

ダイクストラ法による最短経路探索

グラフアルゴリズムの一つであるダイクストラ法では、priority_queueを使用して効率的に最短経路を探索できます。以下に、ダイクストラ法のシンプルな実装例を示します。

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

const int INF = 1e9;
typedef std::pair<int, int> P; // first: 最短距離, second: 頂点番号

std::vector<int> dijkstra(int V, std::vector<std::vector<P>>& adj, int start) {
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    std::vector<int> dist(V, INF);
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int d = pq.top().first;
        int v = pq.top().second;
        pq.pop();

        if (dist[v] < d) continue;

        for (auto& edge : adj[v]) {
            int to = edge.first;
            int cost = edge.second;

            if (dist[v] + cost < dist[to]) {
                dist[to] = dist[v] + cost;
                pq.push({dist[to], to});
            }
        }
    }

    return dist;
}

int main() {
    int V = 5;
    std::vector<std::vector<P>> adj(V);

    // グラフの辺を追加
    adj[0].emplace_back(1, 2);
    adj[0].emplace_back(2, 4);
    adj[1].emplace_back(2, 1);
    adj[1].emplace_back(3, 7);
    adj[2].emplace_back(4, 3);
    adj[3].emplace_back(4, 1);

    std::vector<int> distances = dijkstra(V, adj, 0);

    for (int i = 0; i < V; ++i) {
        std::cout << "Distance to vertex " << i << " is " << distances[i] << std::endl;
    }

    return 0;
}

この例では、ダイクストラ法を使用して、グラフの頂点間の最短距離を計算しています。priority_queueを使用することで、効率的な最短経路探索が可能になります。

これらの実用例を通じて、std::priority_queueの強力さと柔軟性を実感できるでしょう。次に、理解を深めるための演習問題を提供します。

演習問題

ここでは、std::priority_queueの理解を深めるためのいくつかの演習問題を紹介します。これらの問題を解くことで、priority_queueの使用方法やカスタム比較関数の実装方法についての実践的な知識を身につけることができます。

問題1: 基本的なpriority_queueの操作

以下の要件を満たすプログラムを作成してください。

  • std::priority_queue<int>を使用して整数の優先度キューを作成する。
  • 5つの整数をキューに追加する。
  • すべての要素を優先度の高い順に出力する。
#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;

    // 5つの整数を追加
    pq.push(10);
    pq.push(20);
    pq.push(5);
    pq.push(30);
    pq.push(15);

    // 要素を優先度の高い順に出力
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

問題2: カスタム構造体の使用

以下の要件を満たすプログラムを作成してください。

  • std::priority_queueを使用して、カスタム構造体Personを管理する。
  • Person構造体は、名前と年齢を持つ。
  • 年齢が低い順に優先度が高くなるようにpriority_queueを実装する。
  • 3人のPersonをキューに追加し、年齢の低い順に出力する。
#include <queue>
#include <vector>
#include <string>
#include <iostream>

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

    Person(std::string n, int a) : name(n), age(a) {}
};

struct ComparePerson {
    bool operator()(const Person& p1, const Person& p2) {
        return p1.age > p2.age; // 年齢が低い順に優先度を高くする
    }
};

int main() {
    std::priority_queue<Person, std::vector<Person>, ComparePerson> pq;

    // 3人のPersonを追加
    pq.push(Person("Alice", 30));
    pq.push(Person("Bob", 25));
    pq.push(Person("Charlie", 35));

    // 年齢が低い順に出力
    while (!pq.empty()) {
        Person topPerson = pq.top();
        std::cout << topPerson.name << " (" << topPerson.age << ")" << std::endl;
        pq.pop();
    }

    return 0;
}

問題3: カスタム比較関数をラムダ式で実装

以下の要件を満たすプログラムを作成してください。

  • std::priority_queueを使用して、タスク管理システムを作成する。
  • 各タスクには名前と優先度があり、優先度が高いタスクが先に処理される。
  • 比較関数をラムダ式で実装し、3つのタスクをキューに追加して優先度の高い順に出力する。
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <functional>

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

    Task(std::string n, int p) : name(n), priority(p) {}
};

int main() {
    auto compare = [](const Task& t1, const Task& t2) {
        return t1.priority < t2.priority; // 優先度が高いタスクを先に処理する
    };

    std::priority_queue<Task, std::vector<Task>, decltype(compare)> pq(compare);

    // 3つのタスクを追加
    pq.push(Task("Task1", 2));
    pq.push(Task("Task2", 1));
    pq.push(Task("Task3", 3));

    // 優先度の高い順に出力
    while (!pq.empty()) {
        Task topTask = pq.top();
        std::cout << "Processing " << topTask.name << " with priority " << topTask.priority << std::endl;
        pq.pop();
    }

    return 0;
}

これらの演習問題を通じて、std::priority_queueの操作方法やカスタム比較関数の実装方法を学ぶことができます。問題に取り組むことで、priority_queueの実践的な応用力が身につくでしょう。次に、std::priority_queueの応用的な使用方法について説明します。

応用的な使い方

std::priority_queueは、基本的な使用方法を理解した後、さらに応用的な使い方を学ぶことで、より高度なデータ処理が可能になります。ここでは、いくつかの応用的な使用方法を紹介します。

複数の優先度を持つタスク管理

タスク管理システムにおいて、タスクの優先度だけでなく、期限など複数の属性を考慮する場合、複数の優先度基準を組み合わせることができます。以下の例では、優先度と期限を持つタスクを管理します。

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

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

    Task(std::string n, int p, int d) : name(n), priority(p), deadline(d) {}
};

struct CompareTask {
    bool operator()(const Task& t1, const Task& t2) {
        if (t1.priority == t2.priority) {
            return t1.deadline > t2.deadline; // 同じ優先度なら、期限が早い方を優先
        }
        return t1.priority < t2.priority; // 優先度が高い方を優先
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, CompareTask> taskQueue;

    taskQueue.push(Task("Task1", 2, 5));
    taskQueue.push(Task("Task2", 1, 3));
    taskQueue.push(Task("Task3", 2, 1));

    while (!taskQueue.empty()) {
        Task topTask = taskQueue.top();
        std::cout << "Processing " << topTask.name << " with priority " << topTask.priority << " and deadline " << topTask.deadline << std::endl;
        taskQueue.pop();
    }

    return 0;
}

この例では、タスクの優先度が同じ場合、期限が早いタスクを優先して処理するようにしています。

カスタムコンテナの使用

std::priority_queueは、デフォルトでstd::vectorを内部コンテナとして使用しますが、他のコンテナを指定することもできます。例えば、std::dequeを使用する場合の例を示します。

#include <queue>
#include <deque>
#include <iostream>

int main() {
    std::priority_queue<int, std::deque<int>> pq;

    pq.push(10);
    pq.push(5);
    pq.push(20);

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

    return 0;
}

この例では、std::dequeを内部コンテナとして指定しています。

多重優先度キュー

多重優先度キューを実装することで、異なる優先度のタスクを複数のキューで管理することができます。以下の例では、高、中、低の3つの優先度レベルのキューを実装します。

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

enum class PriorityLevel { HIGH, MEDIUM, LOW };

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

    Task(std::string n, PriorityLevel p) : name(n), priority(p) {}
};

int main() {
    std::priority_queue<Task, std::vector<Task>, std::function<bool(Task, Task)>> highQueue([](Task t1, Task t2) {
        return t1.name > t2.name;
    });
    std::priority_queue<Task, std::vector<Task>, std::function<bool(Task, Task)>> mediumQueue([](Task t1, Task t2) {
        return t1.name > t2.name;
    });
    std::priority_queue<Task, std::vector<Task>, std::function<bool(Task, Task)>> lowQueue([](Task t1, Task t2) {
        return t1.name > t2.name;
    });

    // 各優先度キューにタスクを追加
    highQueue.push(Task("HighTask1", PriorityLevel::HIGH));
    highQueue.push(Task("HighTask2", PriorityLevel::HIGH));
    mediumQueue.push(Task("MediumTask1", PriorityLevel::MEDIUM));
    lowQueue.push(Task("LowTask1", PriorityLevel::LOW));

    // 高優先度キューから順に処理
    while (!highQueue.empty()) {
        Task topTask = highQueue.top();
        std::cout << "Processing high priority " << topTask.name << std::endl;
        highQueue.pop();
    }
    while (!mediumQueue.empty()) {
        Task topTask = mediumQueue.top();
        std::cout << "Processing medium priority " << topTask.name << std::endl;
        mediumQueue.pop();
    }
    while (!lowQueue.empty()) {
        Task topTask = lowQueue.top();
        std::cout << "Processing low priority " << topTask.name << std::endl;
        lowQueue.pop();
    }

    return 0;
}

この例では、異なる優先度レベルごとに別々のpriority_queueを使用し、それぞれのキューを処理しています。

これらの応用的な使用方法を理解することで、std::priority_queueをさらに効果的に活用することができます。最後に、本記事のまとめを行います。

まとめ

本記事では、C++のstd::priority_queueの基本から応用までを徹底解説しました。まず、priority_queueの基本的な使用方法や操作方法について学び、優先度の設定方法やカスタム比較関数の使用方法を具体例を通じて理解しました。また、実際のアプリケーションにおける使用例を紹介し、演習問題を通じて実践的な知識を身につけました。

最後に、応用的な使用方法として複数の優先度基準を組み合わせたタスク管理やカスタムコンテナの使用、多重優先度キューの実装などを学びました。これらの知識を活用することで、より高度なデータ処理が可能になります。

std::priority_queueは非常に強力で柔軟なデータ構造です。この記事を参考に、様々な場面で効果的に活用してください。

C++
プログラミング C++ priority_queue

コメント

コメントする

目次