1. 導入
C++の標準ライブラリ（STL）で提供されている std::stack や std::queue は、実はそれ自体が単独のコンテナではなく、既存のコンテナの機能をラップ（包み込む）してインターフェースを制限する「コンテナアダプタ」です。デフォルトの設定では std::deque がバックエンドとして使用されますが、目的やデータサイズによっては、このバックエンドを変更することで、プログラムのパフォーマンスを劇的に向上させることが可能です。今回は、なぜバックエンドの変更が重要なのか、そしてどのように使い分けるべきかを解説します。
2. 基礎知識
std::stack や std::queue は、内部で「どのコンテナを使ってデータを保持するか」をテンプレート引数で指定できます。デフォルトでは std::deque が選ばれますが、これはメモリをブロック単位で管理する特性があり、要素の追加・削除のバランスが良い汎用的なコンテナです。しかし、メモリの連続性やキャッシュ効率を追求する局面では、他のコンテナ（std::vector など）の方が適している場合があります。
3. 実装/解決策
std::stack は末尾への追加・削除のみを行うため、連続したメモリ領域を持つ std::vector をバックエンドに指定すると、メモリの局所性が高まり、CPUキャッシュのヒット率が向上します。これにより、小規模なデータを頻繁に扱うスタック処理では速度改善が期待できます。一方で、std::queue は先頭から要素を取り出す必要があるため、先頭要素の削除にコストがかかる std::vector を使うと、要素をずらす処理が発生し、計算量が O(N) になってしまいます。そのため、queue には deque や std::list を選ぶのが定石です。
4. サンプルプログラム
以下は、std::stack のバックエンドを std::vector に変更する例です。
include
include
include
int main() {
// テンプレートの第2引数にコンテナを指定することでバックエンドを変更
// std::vectorを使うことで、メモリ配置が連続的になりキャッシュ効率が上がります
std::stack
// データの投入
for (int i = 0; i < 5; ++i) {
fast_stack.push(i);
std::cout << "Stack push: " << i << std::endl;
}
// データの取り出し
while (!fast_stack.empty()) {
std::cout << "Stack pop: " << fast_stack.top() << std::endl;
fast_stack.pop();
}
return 0;
}
5. 応用・注意点
注意が必要なのは、コンテナの要件です。
バックエンドとして指定できるコンテナには制限があります。例えば、stack であれば push_back(), pop_back(), back() が実装されている必要があります。vector はこれらを満たしているため問題ありませんが、queue で vector を指定すると、内部で pop_front() が呼び出せないためコンパイルエラーとなります。
また、std::vector を指定した場合、再確保（リサイズ）時のコストに注意してください。要素数が予想される最大値を超えると、メモリの再確保と全要素のコピーが発生します。もし要素数が事前にわかっている場合は、reserve() を呼び出せるような独自ラッパーを作成するか、適切な初期容量を確保することを検討してください。現場では、デフォルトの deque で十分なケースも多いため、プロファイラでパフォーマンスを確認した上で最適化を行うのがベストです。
コメント