容量に上限があるキューを実現するためには、リングバッファを用いるのが最も効率的です。
しかし、ポインタの操作を含むコードを自分で書くのは間違いのもとです。効率を最優先する場合以外は、ライブラリを使うほうが良いです。
C++の場合、std::deque
*1を使うと以下の意味でそれほど効率が落ちることはありません。
- 挿入のたびにメモリ確保が走ることはない(
std::list
のような連結リストではこの要件を満たせない) - 挿入または削除のたびに要素の移動が発生することはない(
std::vector
には効率の良いpop_front
が存在せず、erase(vec.begin())
などとするとこの要件を満たせない)
正しく実装されたリングバッファと比べて、劣る点は以下の点です。
- かなり多くのメモリを要求する(libstdc++の実装では、少なくとも8192バイト*2必要です)
- TLBをたくさん占有する(非常に小さいリングバッファであれば一つのページ内に収まります。一方、
std::deque
で作った場合、デフォルトのアロケータはページ境界を無視して4096バイト取るため、四つのページを使用することが多いです) - キャッシュヒットしにくい(大きな領域を事実上使い捨てていくことになるためです)
*1:std::queueとしないほうが、デバッグの時に中身を出力できて楽です。
*2:https://ja.cppreference.com/w/cpp/container/deque によれば一つのチャンクが4096バイトで、リングバッファを運用するためには二チャンク必要なためです。実際計測してみるとそうなっています。