要約
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
を用いたときにパフォーマンス上の問題が生じるとすれば主に以下の2つが原因である。
-
push
により要素数がかなり大きくなる - 要素のムーブ(あるいはコピー)のコストが高い
これらの点を勘案してプロファイリングをしながらstd::stack
に使うデータ構造を決めていけばよい。上で挙げたベンチマークでは要素サイズが4KiBのときでもstd::vector
とstd::deque
の末尾挿入がトントンであるから、ほとんどの場合はstd::vector
が良い選択になると思われる。