要約

std::stackを使うときは内部データ構造にstd::vectorを指定した方が良いことが多いので、必ず一考すること。

本文

STLに入っているstd::stackでは内部で用いるデータ構造を指定することができる。何も指定しなければstd::dequeになるが、パフォーマンスを気にする場合は注意しなければならない。

std::dequeのパフォーマンス特性は次のページが詳しい。

C++ benchmark – std::vector VS std::list VS std::deque
そろそろstd::dequeについて語ろうか

std::dequeの実装は処理系定義だが、unrolled linked listのような実装がなされていると考えればよい。そのため、std::vectorとstd::listの中間くらいの性能をしている。std::vectorの弱点であるランダムな位置への挿入・削除はstd::dequeではある程度緩和される。しかし、std::stackの内部実装として用いる場合は末尾への挿入・削除しか行われないため、この利点は生かされない。

std::stackにstd::vectorを用いたときにパフォーマンス上の問題が生じるとすれば主に以下の２つが原因である。

pushにより要素数がかなり大きくなる
要素のムーブ（あるいはコピー）のコストが高い

これらの点を勘案してプロファイリングをしながらstd::stackに使うデータ構造を決めていけばよい。上で挙げたベンチマークでは要素サイズが4KiBのときでもstd::vectorとstd::dequeの末尾挿入がトントンであるから、ほとんどの場合はstd::vectorが良い選択になると思われる。

参考