stack | Programming Place Plus　C++編【標準ライブラリ】　第１０章

C++編で扱っている C++ は 2003年に登場した C++03 という、とても古いバージョンのものです。C++ はその後、C++11 -> C++14 -> C++17 -> C++20 -> C++23 と更新されています。
なかでも C++11 での更新は非常に大きなものであり、これから C++ の学習を始めるのなら、C++11 よりも古いバージョンを対象にするべきではありません。特に事情がないなら、新しい C++ を学んでください。当サイトでは、C++14 をベースにした新C++編を作成中です。

この章の概要 🔗

この章の概要です。

stack
サイズ
生成と初期化
破棄
代入
要素のアクセス
追加
削除
練習問題
参考リンク
更新履歴

stack 🔗

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

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

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

テンプレート仮引数 T は、格納する要素の型です。

テンプレート仮引数 Container は、要素を格納するために内部で使用するコンテナを指定します。デフォルトでは、deque（第７章）が使用されます。Container には、vector（第５章）や list（第６章）のような他のコンテナを指定できます。

指定できるコンテナの種類には条件があり、push_backメンバ関数、pop_backメンバ関数、backメンバ関数を持っている必要があります。結果的に、標準の STLコンテナとしては、vector、list、deque のいずれかから選択することになります。

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

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

サイズ 🔗

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

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

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

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

#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コンテナの場合、コンストラクタからアロケータ（第３２章）を指定できますが、コンテナアダプタにはありません。コンテナアダプタの場合、使用するアロケータは、内部で使用しているコンテナ次第で決まります。

破棄 🔗

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

仮想デストラクタ（【言語解説】第２７章）ではないので、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

要素のアクセス 🔗

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;
    }
}

実行結果：

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メンバ関数を呼び出す形で実装されます。

削除 🔗

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;
}

実行結果：

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

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

練習問題 🔗

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

解答ページはこちら。

参考リンク 🔗

『Exceptional C++』
- popメンバ関数が戻り値を返さない理由について、詳しい解説がある
Programming Place Plus　C++編　参考書籍
- 当サイトの参考書籍一覧ページ。C++ に関する書籍を多数紹介
Programming Place Plus　C++編　リンク集
- 当サイトの参考Webサイト集。C++ の全般的な学習に有益なサイトを紹介

更新履歴 🔗

’2021/9/30
- C++11 に関する記述を削除（C++11 は新C++編で対応する）

’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　clang の対応バージョンを 3.4 に更新。

’2015/10/11　新規作成。

前の章へ　（第９章　map と multimap）

次の章へ　（第１１章　queue）

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

Programming Place Plus のトップページへ

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー