このページでは、C++標準ライブラリの中から、キュー(待ち行列)と呼ばれるデータ構造を実装した機能を取り上げます。標準ライブラリには、キューの亜種といえるものがほかにもあるので、それらも併せて紹介します。
このページの解説は C++14 をベースとしています。
以下は目次です。要点だけをさっと確認したい方は、「まとめ」をご覧ください。
前のページではスタックと呼ばれる、後入れ先出し📘 (LIFO: Last-In First-Out))の特性を持ったデータ構造が登場しました。このページでは、スタックとセットで語られることが多いデータ構造であるキュー📘 (queue) を取り上げます。
キューの構造は順番待ちで人が並ぶ様子で例えられ、待ち行列と呼ばれることがあります。つまり、先に列に並んだ人から用を済ませて列を抜けるということであり、人をデータ(要素)だとみなせば、先に追加されたデータから先に取り出される構造であるといえます。この特性は先入れ先出し📘(FIFO: First-In First-Out)と呼ばれます。
キューは配列を使って実装できますが、C++ の標準ライブラリにある std::queue を使うのが簡単です(このあと取り上げます)。
配列を使ってキューを実装する方法については、アルゴリズムとデータ構造編でも解説しています。じつは、スタックを実現することと比べて少し厄介であることが分かります。
std::queue[1] はキューを実装したクラスで、<queue> をインクルードすると使用できます。
【上級】正確にはクラステンプレートです。
キューというデータ構造にとって最低限必要な機能は、データを追加する操作と、取り出す操作です。この2つの操作にはそれぞれ、エンキュー📘 (enqueue) と、デキュー📘 (dequeue) という呼び名があります。ただし、std::queue のメンバ関数は、標準ライブラリのほかのクラスに合わせて、エンキューには push、デキューには pop という名前を使っています。
キューは先入れ先出しのデータ構造なので、デキューで取り出されるデータは、キューにあるデータのうちの一番古いものです。
std::queue は std::stack と同じく、型名に <int>
のような記述を付けて、要素の型を指定します。
std::queue<int> queue1 {}; // 空のキュー
std::queue<int> queue2 {queue1}; // ほかのキューからコピー
エンキューは pushメンバ関数で行います。
.push(100); queue1
【C++23】push_rangeメンバ関数が追加され、Range(C++20 の機能)を指定した方法でまとめて追加できるようになっています[2]。
デキューは popメンバ関数で行います。エンキューされた一番古いデータが削除されますが、その値が返ってくることはなく、戻り値は void です。
.pop(); queue1
デキューで削除される値が必要なら、先に frontメンバ関数を使って受け取っておく必要があります。frontメンバ関数が返すものは、std::queue の内側にあるデータへの参照なので、コピーを受け取らないと危険です。
auto v = queue1.front(); // int& が返される。参照のまま受け取ると、pop で削除されるので危険
.pop(); queue1
std::queue が空の状態で popメンバ関数、frontメンバ関数を呼び出してはいけません。
【上級】std::queue は実装にほかのコンテナを用いており(テンプレートパラメータにより取り換えできる)、popメンバ関数は内部コンテナの pop_frontメンバ関数を、frontメンバ関数は内部コンテナの frontメンバ関数を呼び出すことで実現されます。そのため、std::queue が空の場合の動作も、それぞれの関数がどのように実装されているかに左右されることになります。デフォルトで用いられるコンテナは std::deque であり、この場合(C++標準のほかのコンテナに取り換えた場合も結局は同様に)は未定義の動作です[3]。
空かどうかは emptyメンバ関数を使って調べられます。
if (!queue1.empty()) {
.pop(); // 安全
queue1}
sizeメンバ関数を使って、現在格納されているデータの個数を調べることもできます。
auto size = queue1.size();
前のページで bucketコマンドを実装するためにスタック(std::stack)を使いました。実はこのときのコードを単純にキュー(std::queue)に置き換えても、bucketコマンドを実現できます。
#include <queue>
#include <tuple>
namespace paint_script {
void Canvas::bucket_drawing(int x, int y, Pen& pen)
{
if (!is_inside(x, y)) {
return;
}
const Color target_color {get_pixel(x, y)};
if (is_equal_color(target_color, pen.get_color())) {
return;
}
std::queue<std::pair<int, int>> pixel_queue {};
// すでに確認済みのピクセルかどうかを管理する二次元配列
std::vector<std::vector<bool>> visited(m_width, std::vector<bool>(m_height, false));
// 起点のピクセルを登録
.push({x, y});
pixel_queue[x][y] = true;
visited
// 4方向に座標を移動させるための配列
constexpr int dx[] {0, 0, -1, 1};
constexpr int dy[] {-1, 1, 0, 0};
// キューが空になるまで繰り返すループ(再帰呼び出しをしない)
while (!pixel_queue.empty()) {
// キューから1つ取り出す
std::tie(x, y) = pixel_queue.front();
.pop();
pixel_queue
// 取り出された座標のピクセルを塗る
(x, y, pen);
paint_dot
// 上下左右のピクセルが target_color と一致するなら、その座標情報をキューに入れる。
// キャンバスの端を越えないようにチェック。
for (int i {0}; i < 4; ++i) {
int nx {x + dx[i]};
int ny {y + dy[i]};
if (is_inside(nx, ny) && is_equal_color(target_color, get_pixel(nx, ny)) && !visited[nx][ny]) {
.push({nx, ny});
pixel_queue[nx][ny] = true;
visited}
}
}
}
}
スタックを使った実装では、スタックに新しく追加された座標から先に取り出されることになるので、起点となった座標から一番遠いところ(深いところ)まで一気に進むことになります。そのため、このような方法を深さ優先探索 (DFS: Depth-First Search) と呼びます。
一方、キューを使った実装では、キューに追加された座標が順番どおりに取り出されることになるので、起点に近いところから始めて、同じ距離の範囲を調べ尽くしたら、1つ範囲を広げる(1段階遠いところへ進む)という動作になります。このような方法は、幅優先探索 (BFS: Breadth-First Search) と呼ばれます。
paint_dotメンバ関数を呼び出しているところで、座標を出力させてみると、起きていることが分かりやすいでしょう。ついでに、スタックやキューに入っているデータの個数も出力します。
// 取り出された座標のピクセルを塗る
(x, y, pen);
paint_dotstd::cout << x << ", " << y << ": " << pixel_queue.size() << "\n"; // pixel_queue はスタック版では pixel_stack
以下のようにコマンドを実行して、小さめの円の内側を塗りつぶしてみます。
100 100 5
circle 100 100
bucket .bmp save test
スタックを用いた深さ優先探索の場合は次のように出力されます。一度、X座標や Y座標が原点(100,100)から一番遠いところまで突き進んでから、周辺を探す様子が分かります。
100, 100: 0
101, 100: 3
102, 100: 5
103, 100: 7
104, 100: 9
104, 101: 10
104, 102: 10
103, 102: 10
102, 102: 11
101, 102: 12
100, 102: 13
99, 102: 14
98, 102: 16
97, 102: 18
96, 102: 20
96, 101: 20
96, 100: 20
97, 100: 21
98, 100: 22
98, 99: 22
99, 99: 23
99, 98: 23
100, 98: 24
101, 98: 25
102, 98: 26
103, 98: 27
104, 98: 28
103, 97: 27
102, 97: 26
102, 96: 26
101, 96: 26
100, 96: 26
99, 96: 26
98, 96: 26
98, 97: 26
97, 97: 26
97, 98: 26
96, 98: 26
101, 97: 25
100, 97: 24
99, 97: 23
98, 98: 22
97, 99: 21
96, 99: 20
97, 103: 19
97, 101: 18
98, 103: 17
98, 104: 17
99, 104: 17
100, 104: 17
101, 104: 17
102, 104: 17
98, 101: 16
99, 103: 15
99, 101: 14
100, 103: 13
101, 103: 12
102, 103: 11
103, 103: 10
104, 99: 9
103, 101: 8
103, 99: 7
102, 101: 6
102, 99: 5
101, 101: 4
101, 99: 3
99, 100: 2
100, 101: 1
100, 99: 0
キューを用いた幅優先探索の場合は次のように出力されます。原点(100,100)の周辺を、少しずつ距離を広げながら調べていく様子が分かります。
100, 100: 0
100, 99: 3
100, 101: 5
99, 100: 7
101, 100: 7
100, 98: 7
99, 99: 9
101, 99: 9
100, 102: 9
99, 101: 11
101, 101: 11
98, 100: 11
102, 100: 11
100, 97: 11
99, 98: 13
101, 98: 13
98, 99: 13
102, 99: 13
100, 103: 13
99, 102: 15
101, 102: 15
98, 101: 15
102, 101: 15
97, 100: 15
103, 100: 15
100, 96: 15
99, 97: 16
101, 97: 16
98, 98: 16
102, 98: 16
97, 99: 16
103, 99: 16
100, 104: 16
99, 103: 17
101, 103: 17
98, 102: 17
102, 102: 17
97, 101: 17
103, 101: 17
96, 100: 17
104, 100: 16
99, 96: 15
101, 96: 15
98, 97: 15
102, 97: 15
97, 98: 15
103, 98: 15
96, 99: 15
104, 99: 14
99, 104: 13
101, 104: 13
98, 103: 13
102, 103: 13
97, 102: 13
103, 102: 13
96, 101: 13
104, 101: 12
98, 96: 11
102, 96: 10
97, 97: 9
103, 97: 8
96, 98: 7
104, 98: 6
98, 104: 5
102, 104: 4
97, 103: 3
103, 103: 2
96, 102: 1
104, 102: 0
bucketコマンドの実装に用いる場合、どちらの方法を使っても同じ結果を得られます。しかし、メモリ使用量の増減の仕方には違いがあります。
スタックを使う深さ優先探索では、一気に一番遠いところまで進むので、その距離が長ければ長いほど多くのメモリを使うことになります。また、起点に近いところに戻ってくるまでにかなり長い処理過程を踏むことになるため、メモリ使用量が落ち着くまでの時間がかかることになります。さきほどの実行結果では、スタック内の要素の個数はどんどん増えていき、28個まで増えたあと、徐々に減っています。
一方、幅優先探索では、1つ遠い距離に処理が進むときには、前の距離の座標情報はもうキューから取り出されているので、メモリ使用量が一気に大きくなることは避けられます。さきほどの実行結果では、キュー内の要素の個数の増え方は緩やかで、一番多いときでも 17個で済んでいます。
ただし、std::stack や std::queue の通常の実装では、格納しているデータ数が減っても確保済みのメモリ領域を解放しません。
あとで取り上げるように、内部実装を取り換えることで挙動を変えられる可能性はあります。
std::queue が登場したついでに、std::priority_queue[4] も取り上げておきます。
std::priority_queue は優先度付きキュー (priority queue) というデータ構造を表現したものです。優先度付きキューの各要素にはそれぞれ優先度が設定され、デキューの際には一番優先度が高い要素から取り出されるというデータ構造です。したがって、キューの一種ですが先入れ先出しではありません。
std::priority_queue を使用するには、<queue> をインクルードします。
優先度付きキューについては、アルゴリズムとデータ構造編でも解説しています。
std::priority_queue は std::queue と同じく、型名に <int>
のような記述を付けて、要素の型を指定します。
std::priority_queue<int> queue1 {}; // 空の優先度付きキュー
std::priority_queue<int> queue2 {queue1}; // ほかの優先度付きキューからコピー
エンキューは pushメンバ関数で行います。
.push(100); queue1
【C++23】push_rangeメンバ関数が追加され、Range(C++20 の機能)を指定した方法でまとめて追加できるようになっています[5]。
デキューは popメンバ関数で行います。優先度がもっとも高いデータが削除されますが、その値が返ってくることはなく、戻り値は void です。
.pop(); queue1
デキューで削除される値が必要なら、先に topメンバ関数を使って受け取っておく必要があります(std::queue は frontメンバ関数でしたが、こちらは topメンバ関数です)。topメンバ関数が返すものは、std::priority_queue の内側にあるデータへの参照なので、コピーを受け取らないと危険です。
auto v = queue1.top(); // int& が返される。参照のまま受け取ると、pop で削除されるので危険
.pop(); queue1
std::priority_queue が空の状態で popメンバ関数、topメンバ関数を呼び出してはいけません。
【上級】std::priority_queue は実装にほかのコンテナを用いており(テンプレートパラメータにより取り換えできる)、popメンバ関数は内部コンテナの pop_backメンバ関数を、topメンバ関数は内部コンテナの frontメンバ関数を呼び出すことで実現されます。そのため、std::priority_queue が空の場合の動作も、それぞれの関数がどのように実装されているかに左右されることになります。デフォルトで用いられるコンテナは std::vector であり、この場合(C++標準のほかのコンテナに取り換えた場合も結局は同様に)は未定義の動作です[6]。
空かどうかは emptyメンバ関数を使って調べられます。
if (!queue1.empty()) {
.pop(); // 安全
queue1}
sizeメンバ関数を使って、現在格納されているデータの個数を調べることもできます。
auto size = queue1.size();
優先度付きキューの要素に設定される優先度は、デフォルトでは要素の値の降順です。次のプログラムで確認できます。
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> prio_queue {};
.push(3);
prio_queue.push(2);
prio_queue.push(4);
prio_queue.push(0);
prio_queue.push(1);
prio_queue
while (!prio_queue.empty()) {
auto v = prio_queue.top();
.pop();
prio_queuestd::cout << v << "\n";
}
}
実行結果:
4
3
2
1
0
3
、2
、4
、0
、1
の順番に追加されたデータが、4
、3
、2
、1
、0
の順番で取り出されました。一番大きな値を持った要素が一番高い優先度を持ったためです。
【上級】追加されたデータが降順になって出てきたわけなので、動作としてはソート📘(「要素を整列する」のページを参照)を実現できているといえます。ただし、あとで取り上げるように、std::priority_queue の内部はデフォルトでは std::vector なので、データを多数追加するときに、メモリの再割り当てを起こす可能性がありますし、実行速度が十分かどうかは状況によります。
優先度が降順に設定されるのは、std::priority_queue の変数を宣言するときに隠されている(省略している)指定の効果によるものです。すべての指定をきちんと書くと次のようになります。
std::priority_queue<int, std::vector<int>, std::less<int>> prio_queue {};
std::priority_queue
の <>
の内側には最大で3つの指定を記述しますが、必須なのは1つ目の「要素の型」だけです。2つ目の std::vector<int>
は、優先度付きキューを実現するために内部で使われているデータ構造の指定です(この話題はあとで改めて取り上げます)。3つ目のところにある std::less<int>
が優先度の指示です。
std::less は関数オブジェクト(「シャッフルと乱数」のページを参照)の型で、std::less を指定することが優先度を降順に設定することを意味します。もし、昇順であることを望むのなら、次のサンプルプログラムのように std::greater を指定します。std::less や std::greater は <functional> で宣言されています。
#include <functional>
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> prio_queue {};
.push(3);
prio_queue.push(2);
prio_queue.push(4);
prio_queue.push(0);
prio_queue.push(1);
prio_queue
while (!prio_queue.empty()) {
auto v = prio_queue.top();
.pop();
prio_queuestd::cout << v << "\n";
}
}
実行結果:
0
1
2
3
4
要素の型が int の場合の優先度は分かりやすいですが、要素が std::string とか std::vector<int> のような型だったらどうなるのでしょうか。std::less や std::greater の operator()
が鍵になります。それぞれ次のように定義されています(要素の型を T と表現します)。
namespace std {
struct less {
bool operator()(const T& x, const T& y) const
{
return x < y;
}
}
struct greater {
bool operator()(const T& x, const T& y) const
{
return x > y;
}
}
}
2つの要素の値を <
または >
で比較して返しているだけです。std::priority_queue にエンキューするとき、この比較が行われ、内部実装で使われているデータ構造(デフォルトでは std::vector でした)の適切な位置に配置されます。つまり、<
や >
で比較可能なものなのであれば、std::priority_queue の要素の型は何でも問題ないということになります。std::string や std::vector には <
も >
も使えますから、std::priority_queue の要素として使って問題ありません。
【上級】自作のクラス型を要素として使う場合など、<
や >
がないのでコンパイルエラーになってしまいます。この場合は <
や >
の演算子オーバーロードをおこなうことで対応できます。
ここまでに、データ構造を表現できる標準ライブラリの機能として、std::vector((伸縮できる)配列)、std::stack(スタック)、std::queue(キュー)、std::priority_queue(優先度付きキュー)の4種類が登場しました(std::string もありますが、これは文字に特化した配列といえます)。C++ では、std::vector と、まだ解説していないいくつかのクラスをまとめてコンテナ (container) と呼び、std::stack、std::queue、std::priority_queue をまとめてコンテナアダプタ (container adapter) と呼びます。
コンテナとコンテナアダプタを呼び分けているのは、コンテナアダプタの実現のために内部的にコンテナを使うという関係性があるためです。デフォルトでは、std::stack や std::queue の実現には std::deque が、std::priority_queue の実現には std::vector が使われています。std::deque はこのあとで取り上げるコンテナの一種です。
「デフォルトでは」と書いたように、コンテナアダプタが使う内部コンテナの種類を切り替えられます(ただし、あとで説明しますが、必要な条件を満たしているコンテナしか選べません)。内部コンテナの違いによって、おもにデータの追加や削除の処理効率やメモリ効率が変わる可能性があるため、徹底的な最適化が必要な場面では切り替える価値があるかもしれません。とはいえほとんどのケースでは、デフォルトで選ばれている内部コンテナのままで問題ないはずです。
あるコンテナアダプタの内部コンテナとして選択できるコンテナは、コンテナアダプタが必要としている機能を持ったものに限られます。たとえば、std::queue を実装するためには、先頭から要素を取り出すことと、末尾に要素を追加することを効率的に行えるコンテナが必要です。そこで std::queue は内部コンテナとして使うコンテナに、front、back、push_back、pop_front、emplace_back(未解説)の各メンバ関数があることを要求します。std::vector には pop_front がないため、std::queue の内部コンテナとしては使用できないということになります。
まとめると以下のようになります。
コンテナアダプタ | 内部コンテナに必要な条件 | 条件を満たせる標準のコンテナ |
---|---|---|
std::stack | back、push_back、pop_back、emplace_back のすべてをもつ | std::deque (デフォルト)、std::vector、std::list |
std::queue | front、back、push_back、pop_front、emplace_back のすべてをもつ | std::deque (デフォルト)、std::list |
std::priority_queue | ランダムアクセスイテレータ、front、push_back、pop_back、emplace_back のすべてをもつ | std::vector (デフォルト)、std::deque |
ランダムアクセスイテレータ (random access iterator) とは、イテレータを機能で分類した呼び名の1つで、添字を使ってランダムアクセス📘が可能なイテレータということです。std::vector や std::string のイテレータはランダムアクセスイテレータであるといえます。
std::list は、連結リストと呼ばれるデータ構造を実装するコンテナです。連結リストについては、アルゴリズムとデータ構造編の【データ構造】第3章・第4章 で解説しています。連結リストにはいくつか分類がありますが、std::list は双方向線形リストを実装したものです。
【上級】内部コンテナが std::vector や std::deque の場合、確保済みのメモリが足らなくなると再割り当てと移動が必要になるため、不意に極端な速度低下を起こす可能性があります。内部コンテナに std::list を使うと、要素が追加されるたびにメモリを確保するので、こうした不意に起こる速度低下を防げます。
【上級】「内部コンテナに必要な条件」が満たさなければならない条件であって、「条件を満たせる標準のコンテナ」はその条件を満たせている標準のコンテナの一覧です。標準のコンテナから選ばなければならないわけではなく「内部コンテナに必要な条件」を満たしていれば内部コンテナとして使用できます。
内部コンテナを変更するには、コンテナアダプタの型を記述するときに <>
の内側に指定を追加するだけです。内部で使うものが変わるだけなので、コンテナアダプタの使い方自体には変化はありません。
std::stack<int, std::vector<int>> stack {}; // 要素が int、内部コンテナが std::vector<int> なスタック
std::queue<int, std::list<int>> queue {}; // 要素が int、内部コンテナが std::list<int> なキュー
std::priority_queue<int, std::deque<int>> prio_queue {}; // 要素が int、内部コンテナが std::deque<int> な優先度付きキュー
さきほどの内部コンテナの一覧の中に std::deque[7] が登場しました。std::deque は、両端キュー(二重終端キュー) (double-ended queue) と呼ばれるキューの一種を実装したコンテナです。両端キューは、先頭と末尾のどちら側に対してでも要素の出し入れが可能なキューです。
std::deque は「デック」のように発音します。「デキュー」と呼ばれるケースもありますが、キューにデータを追加することもデキュー (dequeue) と呼ぶことに気を付けてください。
std::deque の機能は std::vector とよく似ており、ほとんど同じ使い方ができます。<deque> をインクルードして使用します。
std::deque は両端キューなので、先頭と末尾のいずれに対しても要素の追加・削除・参照を効率よく行えます(std::vector は後続の要素をずらす非効率さがあるため、先頭へ要素を追加・削除する関数が省かれています)。添字によるアクセスや、イテレータによる走査も可能です。
std::deque は std::vector と同様、割り当てていたメモリが不足すると、自動的に再割り当てを行います(「要素を追加する」のページを参照)。内部構造の違いから、std::deque の場合は、すべての要素を再配置しなおすほどの大規模な処理が避けられるようになっており、std::vector より効率的です。
まるで万能なようですが、std::deque の要素はメモリ上で連続して並ぶ保証がない点が欠点として挙げられます。たとえば要素を指し示すポインタを得て、ポインタ演算をおこなうことは危険が伴います。また、内部構造が複雑なので、各種操作が全体的に std::vector よりもやや遅くなる傾向があります。
使い方は std::vector とほぼ同じなので、違いがある部分だけを取り上げます。まず、要素の追加には push_backメンバ関数と insertメンバ関数のほか、先頭に追加する push_frontメンバ関数が使えます。
std::deque<int> deq {0, 1, 2};
.push_front(-1); // 先頭に、値が -1 の要素を追加 deq
要素を取り除くには、pop_backメンバ関数、eraseメンバ関数、clearメンバ関数のほか、先頭の要素を取り除く pop_frontメンバ関数が使えます。
std::deque<int> deq {0, 1, 2};
.pop_front(); // 先頭の要素を取り除く。戻り値はなし deq
「容量」と「要素数」の考え方自体はありますが(「要素を追加する」のページを参照)、容量を問い合わせる capacityメンバ関数や、一定の容量でメモリを確保させる reserveメンバ関数はありません。容量を切り詰める shrink_to_fitメンバ関数は存在します(「要素を取り除く」のページを参照)。
std::vector で要素を追加するときや、要素を削除するときに、既存の要素を指し示していたイテレータや参照、ポインタが無効になる仕様がありました(「要素を追加する」「要素を取り除く」のページを参照)。std::deque でも、要素の追加や削除によって無効になることがありますが、そのルールは複雑です。無効にならないケースをうまく活用しようとするのでなければ、基本的につねに無効になると考えていたほうが安全です。
まず要素を追加する場合をまとめると次のようになります[8]。
追加する位置 | 無効になるもの |
---|---|
先頭や末尾 | 要素を指しているすべてのイテレータ |
途中 | 要素を指しているすべてのイテレータと参照・ポインタ |
要素を削除する場合は次のようになります[9]。2つのイテレータを使ってまとめて削除できるため、削除に巻き込まれる要素によって違いがあります。
削除する位置 | 無効になるもの |
---|---|
末尾 | past-the-end イテレータ、要素を指しているすべてのイテレータ、削除された要素への参照とポインタ |
先頭を削除し、末尾の要素を削除しない場合 | 削除された要素を指しているイテレータと参照・ポインタ |
先頭と末尾のいずれも巻き込まない場合 | past-the-end イテレータ、要素を指しているすべてのイテレータと参照・ポインタ |
新C++編の【本編】の各ページには、末尾に練習問題があります。ページ内で学んだ知識を確認する簡単な問題から、これまでに学んだ知識を組み合わせなければならない問題、あるいは更なる自力での調査や模索が必要になるような高難易度な問題をいくつか掲載しています。
a.empty() shall be false
が挙げられている。front() についても、begin() で得たイテレータに *
による間接参照をおこなう実装であるから、要素が空のコンテナに対しては未定義の動作であるa.empty() shall be false
が挙げられている。front() についても、begin() で得たイテレータに *
による間接参照をおこなう実装であるから、要素が空のコンテナに対しては未定義の動作である
問題の難易度について。
★は、すべての方が取り組める入門レベルの問題です。
★★は、自力でプログラミングができるようなるために、入門者の方であっても取り組んでほしい問題です。
★★★は、本格的にプログラマーを目指す人のための問題です。
6個のデータ 4, 3, 5, 3, 7, 6
を std::stack、std::queue、std::priority_queue のそれぞれに追加し、その後1つずつ取り出すと、どのような順序で取り出されますか?
標準入力から整数を1つずつ入力させ、そのつど最新5件の平均値を出力するプログラムを、std::deque を使って作成してください。
プログラムを終了させる方法は適当に決めて構いません。
標準入力から整数を1つずつ入力させ、そのつど最新5件の中で一番小さな値を出力するプログラムを、std::priority_queue を使って作成してください。
プログラムを終了させる方法は適当に決めて構いません。
はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
X で ポスト/フォロー | LINE で送る | noteで書く |
![]() |
管理者情報 | プライバシーポリシー |