C++編【標準ライブラリ】 第10章 stack

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

stack

stack は、 コンテナアダプタの一種で、その名の通り、 スタック(アルゴリズムとデータ構造編【データ構造】第5章)を提供します。
使用するには、stack という名前の標準ヘッダをインクルードする必要があります。

stack は、次のように定義されています。

namespace std {
	template <typename T, typename Container = deque<T> >
	class stack {
	};
}

テンプレートパラメータ T は、格納する要素の型です。

テンプレートパラメータ Container は、要素を格納するために内部で使用するコンテナを指定します。 デフォルトでは、deque(第7章)が使用されます。 Container には、vector(第5章) や list(第6章) のような他のコンテナを指定することができます。
指定できるコンテナの種類には条件があり、 push_backメンバ関数、pop_backメンバ関数、backメンバ関数を持っている必要があります。 結果的に、標準の STLコンテナとしては、vector、list、deque のいずれかから選択することになります。

C++11 の場合、emplace_backメンバ関数も必要です。 C++11 の vector、list、deque には、このメンバ関数が追加されているので、条件は満たしています。

使用するコンテナに list を選択する理由はあまり無いと思いますが、 vector は、deque よりも高速でメモリ使用量も少なく済む可能性があり、価値があるかも知れません。 ただし、vector は容量が足りなくなったときに、非常に処理負荷の大きい、メモリ再確保&コピーが行われるので注意が必要です(第5章

なお、使用しているコンテナの型は、container_type という名前で型別名が与えられています。

サイズ

stack の中に実際に存在している要素数が「サイズ」です。

現在の「サイズ」を知るには、sizeメンバ関数を使います。 また、「サイズ」が 0 かどうかは、emptyメンバ関数で調べられます。
空かどうかを知りたい場合は、効率面から、emptyメンバ関数を優先した方が良いです。

これらの関数は、内部で使用されているコンテナの同名関数を呼び出すように実装されます。 C++03 時点の list においては、sizeメンバ関数の効率が悪い可能性があります(第6章参照)。

使用例としては、次のようになります。

#include <iostream>
#include <stack>

typedef std::stack<int> IntStack;

int main()
{
	IntStack iStack;

	for (int i = 0; i < 5; ++i) {
		iStack.push(i);
	}

	std::cout << iStack.size() << "\n"
	          << std::boolalpha << iStack.empty() << std::endl;
}

実行結果

5
false

生成と初期化

stack には、複数のコンストラクタが定義されているので、様々な方法でインスタンス化できます。

#include <stack>

typedef std::stack<int> IntStack;

int main()
{
	IntStack::container_type c;

	IntStack iStack1;           // 空
	IntStack iStack2(c);        // 内部で使用しているコンテナと同種のコンテナからコピー
	IntStack iStack3(iStack2);  // 他の stack からコピー
}

iStack2 の例では、内部で使用しているコンテナと同種のコンテナを使って、要素をコピーして生成します。 内部で使用するコンテナの型は、std::stack<>::container_type で得られます。

STLコンテナの場合、コンストラクタからアロケータ(第32章)を指定できますが、コンテナアダプタにはありません。 コンテナアダプタの場合、使用するアロケータは、内部で使用しているコンテナ次第で決まります。

C++11 (生成と初期化)

C++11 で、コンストラクタ周りは強化されています。

まず、ムーブコンストラクタが追加されています。

IntStack::container_type c;

IntStack iStack4(std::move(c));        // 内部で使用しているコンテナと同種のコンテナからムーブ
IntStack iStack5(std::move(iStack4));  // 他の stack からムーブ

また、アロケータを指定できるようになりました。

IntStack iStack6(alloc);                       // 要素は空
IntStack iStack7(c, alloc);                    // 内部で使用しているコンテナと同種のコンテナからコピー
IntStack iStack8(std::move(c), alloc);         // 内部で使用しているコンテナと同種のコンテナからムーブ
IntStack iStack9(iStack8, alloc);              // 他の stack からコピー
IntStack iStack10(std::move(iStack8), alloc);  // 他の stack からムーブ

いずれのパターンも、VisualC++ 2013/2015/2017、clang 3.7 は対応しています

破棄

デストラクタでは、stack(が内部で使用しているコンテナ)が確保した領域が破棄されます。

仮想デストラクタ(【言語解説】第27章)ではないので、 stack を継承して使用することは不適切であることに注意して下さい

代入

stack は、テンプレート引数が同一であれば、代入演算子を使ってコピーできます。

#include <iostream>
#include <stack>

typedef std::stack<int> IntStack;

int main()
{
	IntStack iStack, iStack2;

	for (int i = 0; i < 5; ++i) {
		iStack.push(i);
	}

	iStack2 = iStack;

	std::cout << iStack.size() << "\n"
	          << iStack2.size() << "\n"
			  << std::boolalpha << (iStack == iStack2) << std::endl;
}

実行結果

5
5
true

C++11 (ムーブ代入演算子)

C++11 では、ムーブ代入演算子が追加されています。

#include <iostream>
#include <stack>

typedef std::stack<int> IntStack;

int main()
{
	IntStack iStack, iStack2;

	for (int i = 0; i < 5; ++i) {
		iStack.push(i);
	}

	iStack2 = std::move(iStack);

	std::cout << iStack.size() << "\n"
	          << iStack2.size() << "\n"
			  << std::boolalpha << (iStack == iStack2) << std::endl;
}

実行結果

0
5
false

ムーブ代入演算子は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。

要素のアクセス

stack は、スタック構造なので、最後に追加した要素に対してだけアクセスできるように設計されています。 この用途には、topメンバ関数を使用します。

#include <iostream>
#include <stack>

typedef std::stack<int> IntStack;

int main()
{
	IntStack iStack;

	for (int i = 0; i < 5; ++i) {
		iStack.push(i);
	}

	const IntStack::size_type size = iStack.size();
	for (IntStack::size_type i = 0; i < size; ++i) {
		std::cout << iStack.top() << std::endl;
	}
}

実行結果

4
4
4
4
4

topメンバ関数は、stack に最後に追加された要素への参照を返します。 constメンバ関数版と、非constメンバ関数版とがオーバーロードされているので、読み書きのいずれにも使用できます。
参照で返されることから分かるように、ヌルを知ることはできませんから、 空の stack に対する topメンバ関数の呼び出しは、未定義の動作になることに注意して下さい

実行結果からも推測できるように、 topメンバ関数は、stack から要素を取り出すわけではありません。 要素を取り出したいのであれば、popメンバ関数を使う必要があります。

なお、topメンバ関数は、内部で使用しているコンテナの backメンバ関数を呼び出す形で実装されます

追加

stack への要素の追加には、pushメンバ関数を使用します。 スタック構造なので、挿入先の位置は確定しており、選択の余地はありません。

#include <iostream>
#include <stack>

typedef std::stack<int> IntStack;

int main()
{
	IntStack iStack;

	for (int i = 0; i < 5; ++i) {
		iStack.push(i);
	}

	std::cout << iStack.size() << "\n"
	          << std::boolalpha << iStack.empty() << std::endl;
}

実行結果

5
false

なお、pushメンバ関数は、内部で使用しているコンテナの push_backメンバ関数を呼び出す形で実装されます

C++11(移動による追加)

C++11 では、移動による要素の追加ができるようになっています。

iStack.push(std::move(value));

VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます

C++11(emplace)

pushメンバ関数は、stack の外で挿入するオブジェクトを作り、それをコピー(または移動)する必要があります。 これは、少なくとも一時オブジェクトを生成するコストが掛かるため(コピーの場合は、更にコピーのコスト)、 使い方によっては非効率さがあります。

C++11 では、emplaceメンバ関数を使うと、 要素のコンストラクタに渡す引数だけを指定し、メンバ関数内でオブジェクトを作らせるという方法が使えます。

iStack.push(MyClass(10, "abc"));  // 一時オブジェクトを作ってコピー
iStack.emplace(10, "abc");        // コンストラクタの引数だけ指定し、関数内で生成

emplaceメンバ関数は、内部で使用しているコンテナの emplace_backメンバ関数を呼び出す形で実装されます

emplaceメンバ関数は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます

削除

stack から要素を削除するには、popメンバ関数を使用します。 スタック構造ですから、必ず、最後に追加された要素が削除されます。 stack が空の場合に使用すると、未定義の動作となるので注意して下さい

#include <iostream>
#include <stack>

typedef std::stack<int> IntStack;

int main()
{
	IntStack iStack;

	for (int i = 0; i < 5; ++i) {
		iStack.push(i);
	}

	while (!iStack.empty()) {
		iStack.pop();
	}

	std::cout << iStack.size() << std::endl;
}

実行結果

0

popメンバ関数の戻り値は void であり、何も返しません。 もし、要素の値を知る必要があるのなら、先に topメンバ関数を使用するようにします。

#include <iostream>
#include <stack>

typedef std::stack<int> IntStack;

int main()
{
	IntStack iStack;

	for (int i = 0; i < 5; ++i) {
		iStack.push(i);
	}

	while (!iStack.empty()) {
		std::cout << iStack.top() << "を取り除きます" << std::endl;
		iStack.pop();
	}
}

実行結果

4を取り除きます
3を取り除きます
2を取り除きます
1を取り除きます
0を取り除きます

popメンバ関数が要素を返さないのは、例外安全(【言語解説】第31章)を保証するためです。 もし、popメンバ関数が戻り値を返すとすれば、それは格納されている要素の「コピー」になります(格納されている要素は削除したい訳だから)が、 これを呼び出し元が受け取るまでの課程で例外が発生すると、削除してしまった要素が完全に失われてしまいます。

なお、popメンバ関数は、内部で使用しているコンテナの pop_backメンバ関数を呼び出す形で実装されます


練習問題

問題@ stack には、vector や list などの STLコンテナが備えている clearメンバ関数に相当する機能がありません。 自作関数として実装して下さい。


解答ページはこちら

参考リンク

Exceptional C++
 -- popメンバ関数が戻り値を返さない理由について、詳しい解説がある。

更新履歴

'2017/3/25 VisualC++ 2017 に対応。

'2016/10/15 clang の対応バージョンを 3.7 に更新。

'2015/10/12 clang の対応バージョンを 3.4 に更新。

'2015/10/11 新規作成。



前の章へ

次の章へ

C++編のトップページへ

Programming Place Plus のトップページへ