c++ : std::stack のデータの保持の仕方がわからない。

Question

c++ の stack を自分で実装しようとして挙動を調べています。その過程で生まれた疑問です。

Q：stack は 値を保持する配列はどうやって宣言しているのでしょうか？　あわせて、push()の挙動はどうなるのでしょうか？

ソースコードを追ったのですが、わかりませんでした。

自分が、思うに、選択肢は２つだと思います

① 値を保持する配列の大きさを静的に設定-> push するたび、配列のお尻に一個追加。
（例えばこのサイト: https://www.cprogramming.com/tutorial/computersciencetheory/stackcode.html）

② 配列を動的に確保-> push するたび、大きさを一つ増やした配列を作り直して、値をコピー

実際のところはどうなのでしょうか？

①　の場合、stack インスタンスを宣言するたびに常に大きなメモリを確保しないといけないのでメモリがもったいないですよね。

でも

②　の場合は、値をコピーするたびに、配列の大きさ回コピーの処理をしないといけないので、以下のような処理がタイムアウトすると思いました。(実際はタイムアウトしません....)

#include <iostream>
#include <stack>

int main()
{
	std::stack<char> n;

	for (size_t i = 0; i < 10000000; i++)
	{
		n.push('a');
	}


}

どなたかお力を貸してくださいm(__)m

Answer 1

std::stack はデフォルトでは std::deque をベースにすることになっています。 一般的には std::deque はリングバッファを使いつつ、足りなくなれば伸ばすという戦略を取ることになるでしょう。 実体としては std::vector に近いはずです。

スタックのメモリ管理の戦略を考えるとすると、以下が考えられます。

• ある程度は余裕を持った大きさを確保しておいて、足りなくなれば倍 (1.5 倍程度が良いとする説もあります) に伸ばしたメモリをあらたに確保してコピー (再配置) する。 (構造が単純だが再配置のコストがまあまあ大きいという欠点がある。)
• 要素をひとつ追加するたびにノードのメモリを確保してリンクリストとしてつなげていく。 (プログラムとしては一番簡単だと思われるが局所性に劣るのでキャッシュのヒット率が低い可能性がある。)
• ある程度の大きさのメモリ領域 (チャンク) を単位として、足りなくなれば新しいチャンクを確保してリンクリストでつなげていく。 (上の二通りの方法の間を取った感じ。 管理が多少煩雑で面倒かも。)

Answer 2

配列で実装する場合、両者の中間の、「実際に入っているデータよりある程度大きな領域を確保する」というようなアルゴリズムが多いです。

「足りなくなったら容量を2倍に増やす」ようにしておけば、データが2倍に増えるまではコピーは起きません。

Comments

[yoshiki_iwasa]

ありがとうございます！

なるほど、それの実装に関してググるとしたらなんて検索したらいいですかね??
具体的に名前がついてるアルゴリズムなんでしょうか？

[yumetodo]

libstdc++やlibc++は倍々ゲームで確保する戦略で、msvcのSTLは1.5倍を採用しているようです。

Answer 3

Q：stack は 値を保持する配列はどうやって宣言しているのでしょうか？

「cpprefjp - C++日本語リファレンス」によれば、デフォルトでは配列ではなく deque が使われていますね。

stack は、所定のメンバ関数を持つコンテナのオブジェクトを内部実装として用いており、標準のコンテナ、もしくは独自に実装したコンテナを指定することができる。 このコンテナに必要な要件は、以下のメンバ関数を持つことである。
back()
push_back()
pop_back()
emplace_back() (C++11)
この要件を満たすものとしては vector 、deque 、list があり、デフォルトでは deque が使用される。

Comments

[yoshiki_iwasa]

あ、そうみたいですね！
ありがとうございます！！
今、自分もdeque の実装を調べているところです。
もし、deque の内部挙動しってるよ〜　って人いたら教えてください m(_ _)m

[yumetodo]

dequeはシンプルに言うとstd::vector<std::array<T, N>*>です。ある程度の大きさのブロックごとに分けて管理することで要素数変化時のコピー数を減らしています。一方でデータがメモリー上で連続する保証がないので、要素アクセス速度はvectorよりも遅くなります。

[lehshell]

イメージするのは双方向リストですが、双方向に成長する動的配列の実装もあるようです。
push() と pop() だけであれば単方向で実装すればいいのでは？

[yumetodo]

それはlistとforward_listじゃないですかねぇ。
参考資料:
https://qiita.com/h_hiro_/items/a83a8fd2391d4a3f0e1c
https://kikairoya.hatenablog.com/entry/20100718/1279465696

[yoshiki_iwasa]

@yuemoto @lehshell

おふたりともありがとうございます〜！

ちなみに、お二人はそういった知識をどこから得ましたか？？
やっぱりソースコードを読むんですかね？　書籍でも、webサイトでも参考になるソースがあったら後学のためにぜひ教えていただきたいです（^^）

[yumetodo]

自分はQiitaのC++タグがついた記事を原則全部読むとかTwitterで強い人とFF関係になることをしているのであんまり参考にならないかなと。

[lehshell]

deque の実装に関しては規格上の規定はない認識です。不毛な話はしたくありません。
https://cpprefjp.github.io/reference/deque/deque.html
には
vector と同様の機能を提供するが、シーケンスの終端だけでなく先頭への効率的な挿入・削除を共に提供する。vector とは異なる欠点として deque は連続した位置のストレージに全ての要素を持つことを保証していないため、ポインタ演算を介しての安全なアクセスの可能性を排除する。
とあります。
「push() と pop() だけであれば単方向で実装すればいいのでは？」は元の stack の実装についての話です。

[lehshell]

私は「cpprefjp - C++日本語リファレンス」と規格書ですね。Webも調べますがエビデンスの提示のないものが多い上に C や C++ は間違いも多い。

[yoshiki_iwasa]

おふたりとも教えてくれてありがとうございました！
またお願いします〜

[yumetodo]

規格書は大事ですね。cpprefjpは私も執筆に少しですが加わってます。誤字脱字、内容のわかりにくい点ありましたらお気軽にissue/PRを立ててください。

[yoshiki_iwasa]

@yumetodo
え　書いてる側の方なんですか笑
ありがとうございます。すごい助かってます。