RSS
Programming Place Plus トップページ -- C++編
この章の概要です。
queue は、コンテナアダプタの一種で、その名の通り、キュー（アルゴリズムとデータ構造編【データ構造】第６章）を提供します。使用するには、<queue> という名前の標準ヘッダをインクルードする必要があります。
queue は、次のように定義されています。
namespace std {
template <typename T, typename Container = deque<T> >
class queue {
};
}テンプレート仮引数 T は、格納する要素の型です。
テンプレート仮引数 Container は、要素を格納するために内部で使用するコンテナを指定します。デフォルトでは、deque（第７章）が使用されます。Container には、vector（第５章） や list（第６章） のような他のコンテナを指定できます。
指定できるコンテナの種類には条件があり、push_backメンバ関数、pop_frontメンバ関数、backメンバ関数、frontメンバ関数を持っている必要があります。結果的に、標準の STLコンテナとしては、list、deque のいずれかから選択することになります。
C++11 の場合、emplace_backメンバ関数も必要です。C++11 の list、deque には、このメンバ関数が追加されているので、条件は満たしています。
なお、使用しているコンテナの型は、container_type という名前で型別名が与えられています。
queue の中に実際に存在している要素数が「サイズ」です。
現在の「サイズ」を知るには、sizeメンバ関数を使います。また、「サイズ」が 0 かどうかは、emptyメンバ関数で調べられます。空かどうかを知りたい場合は、効率面から、emptyメンバ関数を優先した方が良いです。
これらの関数は、内部で使用されているコンテナの同名関数を呼び出すように実装されます。C++03 時点の list においては、sizeメンバ関数の効率が悪い可能性があります（第６章参照）。
使用例としては、次のようになります。
#include <iostream>
#include <queue>
typedef std::queue<int> IntQueue;
int main()
{
IntQueue iQueue;
for (int i = 0; i < 5; ++i) {
iQueue.push(i);
}
std::cout << iQueue.size() << "\n"
<< std::boolalpha << iQueue.empty() << std::endl;
}実行結果
5
falsequeue には、複数のコンストラクタが定義されているので、さまざまな方法でインスタンス化できます。
#include <queue>
typedef std::queue<int> IntQueue;
int main()
{
IntQueue::container_type c;
IntQueue iQueue1; // 空
IntQueue iQueue2(c); // 内部で使用しているコンテナと同種のコンテナからコピー
IntQueue iQueue3(iQueue2); // 他の queue からコピー
}iQueue2 の例では、内部で使用しているコンテナと同種のコンテナを使って、要素をコピーして生成します。内部で使用するコンテナの型は、std::queue<>::container_type で得られます。
STLコンテナの場合、コンストラクタからアロケータ（第３２章）を指定できますが、コンテナアダプタにはありません。コンテナアダプタの場合、使用するアロケータは、内部で使用しているコンテナ次第で決まります。
C++11 で、コンストラクタ周りは強化されています。
まず、ムーブコンストラクタが追加されています。
IntQueue::container_type c;
IntQueue iQueue4(std::move(c)); // 内部で使用しているコンテナと同種のコンテナからムーブ
IntQueue iQueue5(std::move(iQueue4)); // 他の queue からムーブまた、アロケータを指定できるようになりました。
IntQueue iQueue6(alloc); // 要素は空
IntQueue iQueue7(c, alloc); // 内部で使用しているコンテナと同種のコンテナからコピー
IntQueue iQueue8(std::move(c), alloc); // 内部で使用しているコンテナと同種のコンテナからムーブ
IntQueue iQueue9(iQueue8, alloc); // 他の queue からコピー
IntQueue iQueue10(std::move(iQueue8), alloc); // 他の queue からムーブデストラクタでは、queue（が内部で使用しているコンテナ）が確保した領域が破棄されます。
仮想デストラクタ（【言語解説】第２７章）ではないので、queue を継承して使用することは不適切であることに注意してください。
queue は、テンプレート実引数が同一であれば、代入演算子を使ってコピーできます。
#include <iostream>
#include <queue>
typedef std::queue<int> IntQueue;
int main()
{
IntQueue iQueue, iQueue2;
for (int i = 0; i < 5; ++i) {
iQueue.push(i);
}
iQueue2 = iQueue;
std::cout << iQueue.size() << "\n"
<< iQueue2.size() << "\n"
<< std::boolalpha << (iQueue == iQueue2) << std::endl;
}実行結果
5
5
trueC++11 では、ムーブ代入演算子が追加されています。
#include <iostream>
#include <queue>
typedef std::queue<int> IntQueue;
int main()
{
IntQueue iQueue, iQueue2;
for (int i = 0; i < 5; ++i) {
iQueue.push(i);
}
iQueue2 = std::move(iQueue);
std::cout << iQueue.size() << "\n"
<< iQueue2.size() << "\n"
<< std::boolalpha << (iQueue == iQueue2) << std::endl;
}実行結果
0
5
falsequeue は、最初に追加された要素か、最後に追加した要素に対してだけアクセスできるように設計されています。前者は frontメンバ関数、後者は backメンバ関数を使用します。
#include <iostream>
#include <queue>
typedef std::queue<int> IntQueue;
int main()
{
IntQueue iQueue;
for (int i = 0; i < 5; ++i) {
iQueue.push(i);
}
std::cout << iQueue.front() << "\n"
<< iQueue.back() << std::endl;
std::cout << iQueue.size() << std::endl;
}実行結果
0
4
5frontメンバ関数は最初に追加された要素の、backメンバ関数は最後に追加された要素の参照を返します。constメンバ関数版と、非constメンバ関数版とがオーバーロードされているので、読み書きのいずれにも使用できます。
参照で返されることから分かるように、ヌルを知ることはできませんから、空の queue に対する frontメンバ関数、backメンバ関数の呼び出しは、未定義の動作になることに注意してください。
上記のサンプルプログラムの sizeメンバ関数の結果の出力からも分かるように、frontメンバ関数や backメンバ関数は、queue から要素を取り出すわけではありません。要素を取り出したいのであれば、popメンバ関数を使う必要があります。
なお、frontメンバ関数や backメンバ関数は、内部で使用しているコンテナの同名のメンバ関数を呼び出す形で実装されます。
queue への要素の追加には、pushメンバ関数を使用します。キュー構造なので、挿入先の位置は確定しており、選択の余地はありません。
#include <iostream>
#include <queue>
typedef std::queue<int> IntQueue;
int main()
{
IntQueue iQueue;
for (int i = 0; i < 5; ++i) {
iQueue.push(i);
}
std::cout << iQueue.size() << "\n"
<< std::boolalpha << iQueue.empty() << std::endl;
}実行結果
5
falseなお、pushメンバ関数は、内部で使用しているコンテナの push_backメンバ関数を呼び出す形で実装されます。
C++11 では、移動による要素の追加ができるようになっています。
iQueue.push(std::move(value));pushメンバ関数は、queue の外で挿入するオブジェクトを作り、それをコピー（または移動）する必要があります。これは、少なくとも一時オブジェクトを生成するコストが掛かるため（コピーの場合は、さらにコピーのコスト）、使い方によっては非効率さがあります。
C++11 では、emplaceメンバ関数を使うと、要素のコンストラクタに渡す引数だけを指定し、メンバ関数内でオブジェクトを作らせるという方法が使えます。
iQueue.push(MyClass(10, "abc")); // 一時オブジェクトを作ってコピー
iQueue.emplace(10, "abc"); // コンストラクタの引数だけ指定し、関数内で生成emplaceメンバ関数は、内部で使用しているコンテナの emplace_backメンバ関数を呼び出す形で実装されます。
queue から要素を削除するには、popメンバ関数を使用します。キュー構造ですから、必ず、最初に追加された要素が削除されます。queue が空の場合に使用すると、未定義の動作となるので注意してください。
#include <iostream>
#include <queue>
typedef std::queue<int> IntQueue;
int main()
{
IntQueue iQueue;
for (int i = 0; i < 5; ++i) {
iQueue.push(i);
}
while (!iQueue.empty()) {
iQueue.pop();
}
std::cout << iQueue.size() << std::endl;
}実行結果
0popメンバ関数の戻り値は void であり、何も返しません。もし、要素の値を知る必要があるのなら、先に frontメンバ関数を使用するようにします。
#include <iostream>
#include <queue>
typedef std::queue<int> IntQueue;
int main()
{
IntQueue iQueue;
for (int i = 0; i < 5; ++i) {
iQueue.push(i);
}
while (!iQueue.empty()) {
std::cout << iQueue.front() << "を取り除きます" << std::endl;
iQueue.pop();
}
}実行結果
0を取り除きます
1を取り除きます
2を取り除きます
3を取り除きます
4を取り除きますpopメンバ関数が要素を返さないのは、例外安全（【言語解説】第３１章）を保証するためです。もし、popメンバ関数が戻り値を返すとすれば、それは格納されている要素の「コピー」になります（格納されている要素は削除したい訳だから）が、これを呼び出し元が受け取るまでの課程で例外が発生すると、削除してしまった要素が完全に失われてしまいます。
なお、popメンバ関数は、内部で使用しているコンテナの pop_frontメンバ関数を呼び出す形で実装されます。
問題① queue が内部で使用するコンテナとして、vector を選択できませんが、その理由を説明してください。また、選択できたとして、適切な選択となり得るでしょうか？
------------------------------------------------------------------------
'2018/1/5 コンパイラの対応状況について、対応している場合は明記しない方針にした。
'2017/7/30 clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。
'2017/3/25 VisualC++ 2017 に対応。
'2016/10/15 clang の対応バージョンを 3.7 に更新。
'2015/10/12 新規作成。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| Twitter でツイート | Twitter をフォロー | LINE で送る |
|
RSS
|
管理者情報 | プライバシーポリシー |