C++ Priority Queueとは：基礎から実践まで
優先順位付きキューの概念と特徴を理解する
Priority Queue（優先順位付きキュー）は、要素に優先順位を付けて管理するデータ構造です。通常のキューがFirst-In-First-Out（FIFO）の原則で動作するのに対し、Priority Queueは各要素に関連付けられた優先度に基づいて要素を取り出します。
主な特徴：
- 要素の挿入：O(log n)の時間複雑度
- 最高優先度要素の取得：O(1)の時間複雑度
- 最高優先度要素の削除：O(log n)の時間複雑度
- ヒープ構造を内部で使用
STLのpriority_queueクラスの仕組みを解説
C++のSTLでは、priority_queueクラステンプレートとして実装されています。基本的な構文は以下の通りです：
#include <queue>
#include <vector>
// 基本的な宣言
priority_queue<int> pq; // デフォルトは最大ヒープ
// 最小ヒープとして使用する場合
priority_queue<int, vector<int>, greater<int>> min_pq;
// カスタム型での使用例
struct Task {
int priority;
string name;
// 比較演算子のオーバーロード
bool operator<(const Task& other) const {
return priority < other.priority;
}
};
priority_queue<Task> task_queue;
内部実装の特徴：
- コンテナアダプタとしての実装
// デフォルトの実装イメージ
template<
class T,
class Container = vector<T>,
class Compare = less<typename Container::value_type>
> class priority_queue;
- 主要なメンバ関数
// 使用例とコメント priority_queue<int> pq; // 要素の追加 pq.push(10); // ヒープに要素を追加：O(log n) // 先頭要素の参照 int top = pq.top(); // 最高優先度の要素を取得：O(1) // 先頭要素の削除 pq.pop(); // 最高優先度の要素を削除：O(log n) // サイズの確認 size_t size = pq.size(); // 現在の要素数を取得 // 空かどうかの確認 bool empty = pq.empty(); // キューが空かどうかを確認
- ヒープ操作の内部動作
priority_queueは内部でバイナリヒープを使用しており、以下の操作が行われています：
// プライオリティキューの内部動作イメージ
void push(const value_type& val) {
// 1. コンテナの末尾に要素を追加
c.push_back(val);
// 2. ヒープ条件を満たすように要素を上方へ移動
push_heap(c.begin(), c.end(), comp);
}
void pop() {
// 1. ルート要素を末尾に移動し、ヒープ条件を再構築
pop_heap(c.begin(), c.end(), comp);
// 2. 末尾要素（元のルート）を削除
c.pop_back();
}
この実装により、常に最も優先度の高い要素に効率的にアクセスできる構造が実現されています。次のセクションでは、これらの基本操作を実践的な例を通じて詳しく見ていきます。
Priority Queueの基本操作をマスターする
要素の追加と取り出しの方法を実装例で学ぶ
Priority Queueの基本操作を、実践的な例を通じて解説します。
- 基本的な操作の実装例
#include <iostream>
#include <queue>
#include <vector>
int main() {
// 優先度付きキューの初期化
std::priority_queue<int> pq;
// 要素の追加
pq.push(30); // O(log n)
pq.push(10);
pq.push(50);
pq.push(20);
// キューの状態確認
std::cout << "サイズ: " << pq.size() << std::endl; // 4
std::cout << "空かどうか: " << (pq.empty() ? "はい" : "いいえ") << std::endl;
// トップ要素の取得と削除
while (!pq.empty()) {
std::cout << pq.top() << " "; // top()はO(1)
pq.pop(); // pop()はO(log n)
}
// 出力: 50 30 20 10
return 0;
}
カスタム比較関数で優先順位を自由に設定
Priority Queueの真の力を引き出すには、カスタム比較関数の活用が重要です。以下に、様々なユースケースでの実装例を示します。
- ラムダ式を使用した比較関数
#include <functional>
// カスタム比較関数を使用した優先度付きキュー
auto compare = [](const int& a, const int& b) { return a > b; };
std::priority_queue<int, std::vector<int>, decltype(compare)> min_heap(compare);
- 構造体を使用したカスタム型の例
struct Process {
int priority;
std::string name;
time_t timestamp;
// カスタム比較演算子
bool operator<(const Process& other) const {
// 優先度が高いものが先に処理される
if (priority != other.priority)
return priority < other.priority;
// 優先度が同じ場合は、タイムスタンプが古いものを優先
return timestamp > other.timestamp;
}
};
// プロセス管理用の優先度付きキュー
std::priority_queue<Process> process_queue;
// 使用例
void process_management_example() {
Process p1 {10, "backup", time(nullptr)};
Process p2 {20, "user_request", time(nullptr)};
Process p3 {10, "maintenance", time(nullptr)};
process_queue.push(p1);
process_queue.push(p2);
process_queue.push(p3);
// 最も優先度の高いプロセスを取得
Process top_priority = process_queue.top();
}
- 複数の基準による優先順位付け
struct Task {
int priority;
int deadline;
std::string description;
};
// 複数の基準を考慮した比較関数
struct TaskComparator {
bool operator()(const Task& a, const Task& b) const {
// 優先度が異なる場合は優先度で比較
if (a.priority != b.priority)
return a.priority < b.priority;
// 優先度が同じ場合はデッドラインで比較
return a.deadline > b.deadline;
}
};
// タスク管理用の優先度付きキュー
std::priority_queue<Task, std::vector<Task>, TaskComparator> task_queue;
// 実践的な使用例
void task_scheduling_example() {
Task t1 {1, 100, "緊急バグ修正"};
Task t2 {1, 50, "セキュリティアップデート"};
Task t3 {2, 150, "新機能開発"};
task_queue.push(t1);
task_queue.push(t2);
task_queue.push(t3);
// タスクの処理
while (!task_queue.empty()) {
Task current = task_queue.top();
task_queue.pop();
// タスク処理のロジック
}
}
このように、Priority Queueは比較関数をカスタマイズすることで、様々なユースケースに対応できます。次のセクションでは、これらの基本操作を踏まえた上で、より高度な最適化テクニックを見ていきます。
実践的な最適化テクニック7選
メモリアロケーションを重視する方法
Priority Queueのメモリ効率を最適化する手法を解説します。
#include <queue>
#include <vector>
// 1. リザーブによるメモリ事前確保
void optimize_memory_allocation() {
std::vector<int> container;
container.reserve(1000); // メモリを事前確保
std::priority_queue<int, std::vector<int>> pq(std::less<int>(), std::move(container));
// この時点でメモリの再確保が発生しにくい
}
// 2. カスタムアロケータの使用
template<typename T>
class PoolAllocator {
// メモリプールの実装
public:
using value_type = T;
T* allocate(std::size_t n) {
// プールからメモリを割り当て
return static_cast<T*>(pool_allocate(n * sizeof(T)));
}
void deallocate(T* p, std::size_t n) {
// プールにメモリを返却
pool_deallocate(p, n * sizeof(T));
}
};
using OptimizedPQ = std::priority_queue<int, std::vector<int, PoolAllocator<int>>>;
イテレータを活用した効率的な操作
// イテレータを使用した効率的な一括操作
template<typename T>
class PriorityQueueManager {
private:
std::priority_queue<T> pq;
public:
// 範囲による一括挿入
template<typename InputIt>
void bulk_push(InputIt first, InputIt last) {
// コンテナの容量を事前に確保
std::vector<T> temp(first, last);
for (const auto& item : temp) {
pq.push(item);
}
}
// 条件付き一括取り出し
template<typename Predicate>
std::vector<T> bulk_pop_if(Predicate pred, size_t max_items = -1) {
std::vector<T> result;
while (!pq.empty() && result.size() < max_items) {
if (pred(pq.top())) {
result.push_back(pq.top());
pq.pop();
} else {
break;
}
}
return result;
}
};
並列処理での安全な使用方法
#include <mutex>
#include <shared_mutex>
// スレッドセーフなPriority Queue実装
template<typename T>
class ThreadSafePriorityQueue {
private:
std::priority_queue<T> pq;
mutable std::shared_mutex mutex;
public:
void push(const T& value) {
std::unique_lock<std::shared_mutex> lock(mutex);
pq.push(value);
}
bool try_pop(T& value) {
std::unique_lock<std::shared_mutex> lock(mutex);
if (pq.empty()) return false;
value = pq.top();
pq.pop();
return true;
}
// 読み取り専用操作の最適化
bool empty() const {
std::shared_lock<std::shared_mutex> lock(mutex);
return pq.empty();
}
size_t size() const {
std::shared_lock<std::shared_mutex> lock(mutex);
return pq.size();
}
};
キャパシティ管理によるパフォーマンス向上
template<typename T>
class CapacityManagedPQ {
private:
std::priority_queue<T> pq;
size_t max_capacity;
public:
explicit CapacityManagedPQ(size_t capacity) : max_capacity(capacity) {
// 内部コンテナのキャパシティを事前確保
std::vector<T> container;
container.reserve(capacity);
pq = std::priority_queue<T>(std::less<T>(), std::move(container));
}
bool push(const T& value) {
if (pq.size() >= max_capacity) {
// 最低優先度の要素と比較
if (value > pq.top()) {
pq.pop(); // 最低優先度の要素を削除
pq.push(value);
return true;
}
return false; // 挿入できなかった
}
pq.push(value);
return true;
}
};
例外安全性を確保する攻略テクニック
#include <exception>
template<typename T>
class ExceptionSafePQ {
private:
std::priority_queue<T> pq;
public:
// 例外安全な挿入操作
void safe_push(const T& value) noexcept(std::is_nothrow_copy_constructible_v<T>) {
try {
pq.push(value);
} catch (...) {
// 挿入に失敗しても状態は変化しない
handle_push_error();
}
}
// 例外安全な取り出し操作
std::optional<T> safe_pop() noexcept {
if (pq.empty()) return std::nullopt;
try {
T value = pq.top();
pq.pop();
return value;
} catch (...) {
// 状態を復元
handle_pop_error();
return std::nullopt;
}
}
};
デバッグとプロファイリングのベストプラクティス
template<typename T>
class DebugablePQ {
private:
std::priority_queue<T> pq;
std::string name;
// プロファイリング情報
struct ProfileInfo {
size_t push_count = 0;
size_t pop_count = 0;
size_t peek_count = 0;
} profile;
public:
explicit DebugablePQ(const std::string& debug_name) : name(debug_name) {}
void push(const T& value) {
#ifdef DEBUG
std::cout << name << ": Pushing value " << value << std::endl;
#endif
auto start = std::chrono::high_resolution_clock::now();
pq.push(value);
auto end = std::chrono::high_resolution_clock::now();
profile.push_count++;
#ifdef PROFILE
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << name << ": Push operation took " << duration.count() << "μs" << std::endl;
#endif
}
// その他のデバッグ機能
void print_statistics() const {
std::cout << "Statistics for " << name << ":\n"
<< "Total pushes: " << profile.push_count << "\n"
<< "Total pops: " << profile.pop_count << "\n"
<< "Total peeks: " << profile.peek_count << "\n"
<< "Current size: " << pq.size() << std::endl;
}
};
これらの最適化テクニックを適切に組み合わせることで、Priority Queueのパフォーマンスと信頼性を大幅に向上させることができます。次のセクションでは、これらのテクニックを実際のユースケースに適用する方法を見ていきます。
一般的なユースケースと実装パターン
ダイクストラ法での最短経路探索の実装
Priority Queueを使用したダイクストラ法の効率的な実装例を示します。
#include <queue>
#include <vector>
#include <limits>
#include <utility>
class Graph {
private:
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) {}
};
int V; // 頂点数
std::vector<std::vector<Edge>> adj; // 隣接リスト
public:
explicit Graph(int vertices) : V(vertices), adj(vertices) {}
void addEdge(int from, int to, int weight) {
adj[from].emplace_back(to, weight);
}
// ダイクストラ法による最短経路探索
std::vector<int> dijkstra(int start) {
// {距離, 頂点番号}のペアを格納するPriority Queue
std::priority_queue<
std::pair<int, int>,
std::vector<std::pair<int, int>>,
std::greater<std::pair<int, int>>
> pq;
// 最短距離を格納する配列
std::vector<int> dist(V, std::numeric_limits<int>::max());
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, v] = pq.top(); // C++17のstructured binding
pq.pop();
// より短い経路が既に見つかっている場合はスキップ
if (d > dist[v]) continue;
// 隣接頂点を探索
for (const auto& e : adj[v]) {
if (dist[e.to] > dist[v] + e.weight) {
dist[e.to] = dist[v] + e.weight;
pq.push({dist[e.to], e.to});
}
}
}
return dist;
}
};
// 使用例
void dijkstra_example() {
Graph g(6); // 6頂点のグラフ
// エッジの追加
g.addEdge(0, 1, 5);
g.addEdge(0, 2, 4);
g.addEdge(1, 2, 2);
g.addEdge(1, 3, 7);
g.addEdge(2, 3, 6);
g.addEdge(2, 4, 11);
g.addEdge(3, 4, 3);
g.addEdge(3, 5, 8);
g.addEdge(4, 5, 5);
auto distances = g.dijkstra(0);
// 頂点0からの最短距離が得られる
}
タスクスケジューラーの設計と実装
マルチタスク環境でのタスクスケジューラーの実装例を示します。
#include <queue>
#include <mutex>
#include <condition_variable>
#include <functional>
#include <chrono>
class TaskScheduler {
public:
struct Task {
int priority;
std::chrono::steady_clock::time_point scheduled_time;
std::function<void()> function;
// 優先順位の比較演算子
bool operator<(const Task& other) const {
if (scheduled_time != other.scheduled_time) {
return scheduled_time > other.scheduled_time;
}
return priority < other.priority;
}
};
private:
std::priority_queue<Task> tasks;
std::mutex mutex;
std::condition_variable cv;
bool running = true;
public:
// タスクの追加
void scheduleTask(
std::function<void()> task,
int priority,
std::chrono::steady_clock::time_point scheduled_time
) {
std::lock_guard<std::mutex> lock(mutex);
tasks.push({priority, scheduled_time, std::move(task)});
cv.notify_one();
}
// 即時実行タスクの追加
void addImmediateTask(std::function<void()> task, int priority) {
scheduleTask(
std::move(task),
priority,
std::chrono::steady_clock::now()
);
}
// スケジューラーの実行ループ
void run() {
while (running) {
std::unique_lock<std::mutex> lock(mutex);
if (tasks.empty()) {
cv.wait(lock, [this] { return !tasks.empty() || !running; });
if (!running) break;
}
auto now = std::chrono::steady_clock::now();
if (tasks.top().scheduled_time <= now) {
auto task = std::move(tasks.top());
tasks.pop();
lock.unlock();
// タスクの実行
try {
task.function();
} catch (const std::exception& e) {
// エラーハンドリング
std::cerr << "Task execution failed: " << e.what() << std::endl;
}
} else {
// 次のタスクの実行時刻まで待機
cv.wait_until(lock, tasks.top().scheduled_time);
}
}
}
// スケジューラーの停止
void stop() {
std::lock_guard<std::mutex> lock(mutex);
running = false;
cv.notify_all();
}
};
// 使用例
void scheduler_example() {
TaskScheduler scheduler;
// スケジューラーを別スレッドで実行
std::thread scheduler_thread([&scheduler] { scheduler.run(); });
// タスクの追加
scheduler.addImmediateTask(
[] { std::cout << "High priority task" << std::endl; },
10
);
auto future_time = std::chrono::steady_clock::now() + std::chrono::seconds(5);
scheduler.scheduleTask(
[] { std::cout << "Scheduled task" << std::endl; },
5,
future_time
);
// スケジューラーの停止
scheduler.stop();
scheduler_thread.join();
}
これらの実装例は、Priority Queueの実践的な使用方法を示しています。次のセクションでは、異なるデータ構造との性能比較を行い、最適な選択基準について見ていきます。
Priority Queueの性能比較と検討基準
他のキューイング構造との比較分析
Priority Queueと他のデータ構造を比較し、それぞれの特徴を解説します。
- 時間計算量の比較
| 操作 | Priority Queue | 通常のQueue | Sorted Vector | Binary Search Tree |
|---|---|---|---|---|
| 挿入 | O(log n) | O(1) | O(n) | O(log n) |
| 最優先要素の取得 | O(1) | O(1) | O(1) | O(log n) |
| 削除 | O(log n) | O(1) | O(n) | O(log n) |
| 検索 | O(n) | O(n) | O(log n) | O(log n) |
| メモリ使用量 | O(n) | O(n) | O(n) | O(n) |
// 各データ構造の実装例と性能比較
#include <queue>
#include <vector>
#include <set>
#include <chrono>
class DataStructureComparison {
private:
// 性能測定用のヘルパー関数
template<typename Func>
static long long measureTime(Func&& func) {
auto start = std::chrono::high_resolution_clock::now();
func();
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
}
public:
static void compareInsertionPerformance(int n) {
std::priority_queue<int> pq;
std::queue<int> q;
std::vector<int> sorted_vec;
std::multiset<int> bst;
// Priority Queue の挿入性能
auto pq_time = measureTime([&]() {
for (int i = 0; i < n; ++i) {
pq.push(i);
}
});
// 通常のQueue の挿入性能
auto q_time = measureTime([&]() {
for (int i = 0; i < n; ++i) {
q.push(i);
}
});
// ソート済みベクターの挿入性能
auto vec_time = measureTime([&]() {
for (int i = 0; i < n; ++i) {
auto pos = std::lower_bound(sorted_vec.begin(), sorted_vec.end(), i);
sorted_vec.insert(pos, i);
}
});
// Binary Search Tree の挿入性能
auto bst_time = measureTime([&]() {
for (int i = 0; i < n; ++i) {
bst.insert(i);
}
});
std::cout << "Insertion time comparison for " << n << " elements:\n"
<< "Priority Queue: " << pq_time << "μs\n"
<< "Normal Queue: " << q_time << "μs\n"
<< "Sorted Vector: " << vec_time << "μs\n"
<< "Binary Search Tree: " << bst_time << "μs\n";
}
};
ユースケース別の最適なデータ構造の選択
各ユースケースにおける最適なデータ構造の選択基準を解説します。
- Priority Queueが最適な場合
- 常に最高（または最低）優先度の要素にアクセスする必要がある
- 要素の挿入と削除が頻繁に発生する
- メモリ効率よりも操作の速度が重要
// Priority Queueが最適なユースケース例
class TaskScheduler {
private:
std::priority_queue<Task> tasks;
public:
void addTask(const Task& task) {
tasks.push(task); // O(log n)の挿入
}
Task getNextTask() {
Task next = tasks.top(); // O(1)で最優先タスクを取得
tasks.pop(); // O(log n)の削除
return next;
}
};
- 通常のQueueが最適な場合
- FIFO（First-In-First-Out）順序が必要
- すべての要素の優先度が同じ
- 最高速の挿入と削除が必要
// 通常のQueueが最適なユースケース例
class MessageQueue {
private:
std::queue<Message> messages;
public:
void enqueue(const Message& msg) {
messages.push(msg); // O(1)の挿入
}
Message dequeue() {
Message msg = messages.front(); // O(1)で先頭要素を取得
messages.pop(); // O(1)の削除
return msg;
}
};
- Sorted Vectorが最適な場合
- 要素の挿入頻度が低い
- 全要素のソート順序の維持が必要
- メモリ効率が重要
- 二分探索による高速な検索が必要
// Sorted Vectorが最適なユースケース例
class RankedLeaderboard {
private:
std::vector<Score> scores;
public:
void addScore(const Score& score) {
auto pos = std::lower_bound(scores.begin(), scores.end(), score);
scores.insert(pos, score); // O(n)の挿入
}
std::vector<Score> getTopN(int n) {
return std::vector<Score>(scores.end() - n, scores.end()); // O(n)でトップNを取得
}
};
- Binary Search Treeが最適な場合
- バランスの取れた検索、挿入、削除の性能が必要
- 要素の順序付けと範囲クエリが必要
- メモリ使用量と性能のバランスが重要
// Binary Search Treeが最適なユースケース例
class OrderBook {
private:
std::map<double, Order> orders; // price をキーとする注文書
public:
void addOrder(const Order& order) {
orders[order.price] = order; // O(log n)の挿入
}
std::vector<Order> getOrdersInRange(double minPrice, double maxPrice) {
std::vector<Order> result;
auto start = orders.lower_bound(minPrice);
auto end = orders.upper_bound(maxPrice);
for (auto it = start; it != end; ++it) {
result.push_back(it->second);
}
return result;
}
};
選択の際の主要な検討基準：
- 操作の頻度
- 挿入が頻繁 → Priority Queue or BST
- 削除が頻繁 → Priority Queue or Queue
- 検索が頻繁 → BST or Sorted Vector
- メモリ制約
- 厳しい制約あり → Sorted Vector
- 制約が緩い → Priority Queue or BST
- 実装の複雑さ
- シンプルさが重要 → Queue or Priority Queue
- 複雑な操作が必要 → BST
- 並行処理の要件
- スレッドセーフ性が必要 → 適切な同期機構付きのPriority Queue
- 単一スレッド → 任意のデータ構造
これらの比較と基準を踏まえて、アプリケーションの要件に最適なデータ構造を選択することが重要です。次のセクションでは、実装時の一般的な落とし穴と対策について見ていきます。
よくある実装の落とし穴と対策法
メモリリークを防ぐベストプラクティス
Priority Queueを使用する際によく発生するメモリ関連の問題と、その対策について解説します。
- スマートポインタの活用
// 問題のある実装
class BadImplementation {
private:
std::priority_queue<MyObject*> pq;
public:
~BadImplementation() {
// デストラクタでメモリ解放を忘れると
// メモリリークが発生
}
};
// 推奨される実装
class GoodImplementation {
private:
std::priority_queue<std::shared_ptr<MyObject>> pq;
// デストラクタで明示的な解放が不要
};
// カスタムデリータの使用例
struct CustomDeleter {
void operator()(MyObject* ptr) const {
// カスタムのクリーンアップ処理
ptr->cleanup();
delete ptr;
}
};
using SafePtr = std::unique_ptr<MyObject, CustomDeleter>;
std::priority_queue<SafePtr> safe_pq;
- RAII原則の適用
template<typename T>
class RAIIPriorityQueue {
private:
struct Resource {
T data;
std::function<void()> cleanup;
Resource(T&& d, std::function<void()> c)
: data(std::move(d)), cleanup(std::move(c)) {}
~Resource() {
if (cleanup) cleanup();
}
};
std::priority_queue<std::unique_ptr<Resource>> queue;
public:
void push(T data, std::function<void()> cleanup) {
queue.push(std::make_unique<Resource>(
std::move(data),
std::move(cleanup)
));
}
T pop() {
if (queue.empty()) throw std::runtime_error("Queue is empty");
auto resource = std::move(queue.top());
queue.pop();
return std::move(resource->data);
}
};
- メモリプール管理
template<typename T, size_t PoolSize = 1024>
class PooledPriorityQueue {
private:
struct MemoryPool {
std::array<T, PoolSize> pool;
std::vector<size_t> free_indices;
MemoryPool() {
free_indices.reserve(PoolSize);
for (size_t i = 0; i < PoolSize; ++i) {
free_indices.push_back(i);
}
}
};
MemoryPool pool;
std::priority_queue<std::pair<T*, int>> pq;
public:
void push(const T& value) {
if (pool.free_indices.empty()) {
throw std::runtime_error("Memory pool exhausted");
}
size_t index = pool.free_indices.back();
pool.free_indices.pop_back();
pool.pool[index] = value;
pq.push({&pool.pool[index], static_cast<int>(index)});
}
T pop() {
if (pq.empty()) {
throw std::runtime_error("Queue is empty");
}
auto [ptr, index] = pq.top();
pq.pop();
T value = *ptr;
pool.free_indices.push_back(index);
return value;
}
};
スレッドセーフな実装のポイント
マルチスレッド環境でのPriority Queue実装における注意点と対策を解説します。
- ロック機構の適切な実装
template<typename T>
class ThreadSafePriorityQueue {
private:
std::priority_queue<T> queue;
mutable std::mutex mutex;
std::condition_variable not_empty;
public:
void push(T value) {
std::unique_lock<std::mutex> lock(mutex);
queue.push(std::move(value));
lock.unlock();
not_empty.notify_one();
}
bool try_pop(T& value) {
std::lock_guard<std::mutex> lock(mutex);
if (queue.empty()) {
return false;
}
value = std::move(queue.top());
queue.pop();
return true;
}
// タイムアウト付きpop操作
bool pop_with_timeout(T& value, const std::chrono::milliseconds& timeout) {
std::unique_lock<std::mutex> lock(mutex);
if (!not_empty.wait_for(lock, timeout, [this] { return !queue.empty(); })) {
return false;
}
value = std::move(queue.top());
queue.pop();
return true;
}
};
- ロックフリー実装の例
template<typename T>
class LockFreePriorityQueue {
private:
struct Node {
T value;
std::atomic<Node*> next;
Node(const T& v) : value(v), next(nullptr) {}
};
std::atomic<Node*> head;
std::atomic<size_t> size;
public:
LockFreePriorityQueue() : head(nullptr), size(0) {}
void push(const T& value) {
Node* new_node = new Node(value);
Node* old_head = head.load(std::memory_order_relaxed);
do {
new_node->next = old_head;
} while (!head.compare_exchange_weak(
old_head,
new_node,
std::memory_order_release,
std::memory_order_relaxed
));
size.fetch_add(1, std::memory_order_relaxed);
}
bool try_pop(T& value) {
Node* old_head = head.load(std::memory_order_relaxed);
do {
if (!old_head) return false;
} while (!head.compare_exchange_weak(
old_head,
old_head->next,
std::memory_order_release,
std::memory_order_relaxed
));
value = old_head->value;
size.fetch_sub(1, std::memory_order_relaxed);
delete old_head;
return true;
}
};
- デッドロック防止テクニック
template<typename T>
class DeadlockFreePriorityQueue {
private:
std::priority_queue<T> queue;
std::mutex mutex;
std::condition_variable not_empty;
std::atomic<bool> is_locked{false};
public:
bool push_with_timeout(const T& value, const std::chrono::milliseconds& timeout) {
std::unique_lock<std::mutex> lock(mutex, std::defer_lock);
// タイムアウト付きでロック取得を試みる
if (!lock.try_lock_for(timeout)) {
return false;
}
queue.push(value);
not_empty.notify_one();
return true;
}
template<typename Rep, typename Period>
bool pop_with_timeout(T& value, const std::chrono::duration<Rep, Period>& timeout) {
std::unique_lock<std::mutex> lock(mutex);
// 条件変数のタイムアウト付き待機
if (!not_empty.wait_for(lock, timeout, [this] { return !queue.empty(); })) {
return false;
}
value = std::move(queue.top());
queue.pop();
return true;
}
// デッドロック検出機能
bool detect_potential_deadlock() const {
return is_locked.load(std::memory_order_relaxed);
}
};
これらの実装パターンと対策を適切に組み合わせることで、メモリ安全性とスレッド安全性を備えた堅牢なPriority Queueを実現できます。実装時には、アプリケーションの要件に応じて適切な方法を選択することが重要です。