コンテンツにスキップ

C++/標準ライブラリ/queue

リンクを追加
出典: フリー教科書『ウィキブックス（Wikibooks）』

C++標準ライブラリ::queueヘッダー[編集]

はじめに[編集]

本書では、C++標準ライブラリにおける<queue>ヘッダーについて解説します。<queue>ヘッダーは、先入れ先出し (FIFO) キューと呼ばれるデータ構造を扱うためのテンプレートを提供します。キューは、要素の挿入と削除を一定の順序で行うことができるデータ構造であり、タスクの管理やイベント処理など、様々な場面で利用されます。

本章では、キューの概念、標準ライブラリのstd::queueテンプレート、キュー操作関数、キューアダプタ、キューイテレータ、キューとスレッドについて解説します。これらの内容を理解することで、C++におけるキューの利用方法を習得することができます。

キューの定義[編集]

キューとは[編集]

キューは、先入れ先出し (FIFO) の原則に基づいて要素を処理するデータ構造です。FIFO の原則とは、「最初に挿入された要素が最初に削除される」という規則です。キューは、ベルトコンベアに例えられることがあり、ベルトコンベアに乗った要素は順番に処理されていきます。

キューの操作[編集]

キューには、以下の基本的な操作があります。

push
キューの末尾に要素を挿入します。
pop
キューの先頭から要素を削除し、返します。
empty
キューが空かどうかを調べます。
size
キューに含まれる要素数を返します。

キューの利点[編集]

キューには、以下の利点があります。

シンプル
構造と操作がシンプルで理解しやすい。
効率的
挿入と削除の操作が一定時間で行える。
汎用性
タスク管理、イベント処理など、様々な場面で利用できる。

キューと他のデータ構造の比較[編集]

キューは、他のデータ構造と比べて以下の特徴を持っています。

スタック
スタックは、先入れ後出し (LIFO) の原則に基づいて要素を処理するデータ構造です。キューとは異なり、最初に挿入された要素は最後に削除されます。
リスト
リストは、要素間の論理的な順序を持つデータ構造です。キューとは異なり、挿入と削除の操作がランダムに行えます。
ハッシュ表
ハッシュ表は、キーと値のペアを格納するデータ構造です。キューとは異なり、要素へのアクセスがキーに基づいて行えます。

標準ライブラリのstd::queueテンプレート[編集]

概要[編集]

標準ライブラリにおけるstd::queueテンプレートは、汎用キューと呼ばれるデータ構造を定義します。汎用キューは、要素型をテンプレートパラメータとして受け取り、その型に基づいてキューを構築します。

テンプレートパラメータ[編集]

std::queueテンプレートには、以下のテンプレートパラメータがあります。

ValueType
キューに格納される要素の型。

テンプレート特化[編集]

std::queueテンプレートは、以下のテンプレート特化が定義されています。

std
:deque<ValueType> : 要素型が std::deque である場合。
std
:list<ValueType> : 要素型が std::list である場合。

これらのテンプレート特化は、それぞれ異なるキュー実装を提供します。

キュー操作関数[編集]

push[編集]

要素をキューの末尾に挿入します。 

template <typename ValueType>
 void queue<ValueType>::push(const ValueType& value);

pop[編集]

キューの先頭から要素を削除し、返します。 

template <typename ValueType>
 ValueType queue<ValueType>::pop();

empty[編集]

キューが空かどうかを調べます。 

template <typename ValueType>
 bool queue<ValueType>::empty() const;

size[編集]

キューに含まれる要素数を返します。 

template <typename ValueType>
 std::size_t queue<ValueType>::size() const;

その他の操作関数[編集]

標準ライブラリは、以下の操作関数も提供しています。

front
キューの先頭の要素を参照します。
back
キューの末尾の要素を参照します。
swap
2つのキューの内容を交換します。

キューアダプタ[編集]

概要[編集]

キューアダプタは、標準ライブラリが提供するキュー実装を拡張するためのテンプレートクラスです。キューアダプタを用いることで、キューに独自の機能を追加したり、特定のニーズに合わせたキュー実装を作成することができます。

標準ライブラリのキューアダプタ[編集]

標準ライブラリは以下のキューアダプタを提供しています。

std
:queue : 汎用キューアダプタ。
std
:priority_queue : 優先度付きキューアダプタ。要素に優先度を割り当て、優先度が高い要素から処理されます。

キューアダプタの利用方法[編集]

キューアダプタを利用するには、以下の手順を行います。

  1. キューアダプタのテンプレートをインスタンス化します。
  2. インスタンス化されたキューアダプタを、通常のキューと同様に操作します。
// std::queueアダプタの利用例
 std::queue<int> q;
 q.push(1);
 q.push(2);
 q.push(3);
 
 while (!q.empty()) {
   int value = q.pop();
   std::cout << value << " ";
 }

キューイテレータ[編集]

概要[編集]

キューイテレータは、キュー内の要素を順にたどることができるイテレータです。キューイテレータを用いることで、キュー内の要素をループ処理したり、特定の要素にアクセスしたりすることができます。

キューイテレータの種類[編集]

キューイテレータには、以下の種類があります。

const_iterator
読み取り専用のイテレータ。キュー内の要素を参照することはできますが、変更することはできません。
iterator
読み書き可能なイテレータ。キュー内の要素を参照したり、変更したりすることができます。

キューイテレータの利用方法[編集]

キューイテレータを利用するには、以下の手順を行います。

  1. キューの begin() メンバ関数によって、キューの先頭のイテレータを取得します。
  2. イテレータを ++ 演算子によってインクリメントすることで、次の要素へ移動します。
  3. イテレータがキューの終端 (end()) に達するまで、2. の操作を繰り返します。
// キューイテレータの利用例
 std::queue<int> q;
 q.push(1);
 q.push(2);
 q.push(3);
 
 for (std::queue<int>::iterator it = q.begin(); it != q.end(); ++it) {
   std::cout << *it << " ";
 }

キューとスレッド[編集]

概要[編集]

キューは、マルチスレッドプログラミングにおいて、タスク間の同期と通信を行うために有用なデータ構造です。キューにタスクを格納することで、複数のスレッドがタスクを効率的に処理することができます。

スレッドセーフなキュー[編集]

複数のスレッドから安全にアクセスできるキューを、スレッドセーフなキューといいます。スレッドセーフなキューは、排他制御機構を用いて、データ競合を防止します。

キューとスレッドの利用例[編集]

以下は、キューとスレッドを用いたタスク処理の例です。

  1. メインスレッドは、タスクを生成してキューに格納します。
  2. ワーカースレッドは、キューからタスクを取り出して処理します。
#include <queue>
#include <thread>
 
 std::queue<int> q;
 
 void worker_thread() {
   while (true) {
     if (!q.empty()) {
       int task = q.pop();
       // タスクを処理
     } else {
       // キューが空の場合の処理
     }
   }
 }
 
 auto main() -> int {
   // タスクを生成してキューに格納
   q.push(1);
   q.push(2);
   q.push(3);
 
   // ワーカースレッドを起動
   std::thread worker(worker_thread);
 
   // メインスレッドの処理
   // ...
 
   worker.join();
 
   return 0;
 }

まとめ[編集]

本章では、C++標準ライブラリの<queue>ヘッダーについて解説しました。

<queue>ヘッダーは、先入れ先出し (FIFO) キューと呼ばれるデータ構造を扱うためのテンプレートを提供します。キューは、要素の挿入と削除を一定の順序で行うことができるデータ構造であり、タスク管理、イベント処理など、様々な場面で利用されます。

本章では、以下の内容を解説しました。

  • キューの概念
  • 標準ライブラリのstd::queueテンプレート
  • キュー操作関数
  • キューアダプタ
  • キューイテレータ
  • キューとスレッド

これらの内容を理解することで、C++におけるキューの利用方法を習得することができます。

今後の学習[編集]

本章で学んだ内容を活かして、以下の点について学習を深めていきましょう。

  • 標準ライブラリが提供するその他のキュー関連テンプレート (例: std::priority_queue)
  • キューを用いた具体的なアプリケーション (例: タスクスケジューラ、パイプライン処理)
  • スレッドセーフなキューの実装方法
  • キューとその他のデータ構造の組み合わせ

これらの学習を通して、C++におけるキューの活用範囲を広げ、より高度なプログラミングスキルを習得することができます。

附録[編集]

練習問題[編集]

  1. 以下のコードを実行し、結果を説明してください。 
    #include <queue>
 
 auto main() -> int {
   std::queue<int> q;
 
   q.push(1);
   q.push(2);
   q.push(3);
 
   while (!q.empty()) {
     int value = q.pop();
     std::cout << value << " ";
   }
 
   return 0;
 }
  2. キューを用いて、タスクを生成して処理するプログラムを作成してください。タスクは、1から10までの整数を順に表示する処理とします。
  3. 2つのキューを用いて、タスク間の優先度を設定するプログラムを作成してください。高優先度のタスクは、低優先度のタスクよりも先に処理されるようにします。


print C++
queue 		ranges
"https://ja.wikibooks.org/w/index.php?title=C%2B%2B/標準ライブラリ/queue&oldid=249716" より作成