[解決済み] FIFOに使用するSTLコンテナはどれですか？

質問

どのSTLコンテナが私のニーズに最も合うでしょうか？私は基本的に10要素幅のコンテナを持っており、その中に継続的に push_back 新しい要素を追加しながら pop_front は最も古い要素になります（約100万回）。

現在、私が使っているのは std::deque を使っていますが、このタスクに std::list の方が、再割り当てする必要がないので、より効率的なのではないかと思いました。 std::deque を std::vector ?). それとも、私のニーズに対してさらに効率的なコンテナがあるのでしょうか？

追伸：私はランダムアクセスを必要としません。

どのように解決するのですか？

回答が無数にあるため、混乱するかもしれませんが、要約します。

を使う。 std::queue . この理由は簡単で、FIFO構造だからです。FIFOが必要な場合は std::queue .

他の誰に対しても、そして自分自身に対しても、その意図を明確にすることができます。A std::list または std::deque はそうではありません。リストはどこにでも挿入したり削除したりできますが、これはFIFO構造が想定していることではありませんし、また deque はどちらかの端から追加と削除を行うことができ、これも FIFO 構造体ができないことです。

このため queue .

さて、パフォーマンスについて質問されました。まず、この重要な経験則を常に覚えておいてください。 良いコードが最初で、パフォーマンスは最後。

その理由は簡単で、きれいさや優雅さよりもパフォーマンスを優先する人は、ほとんどの場合、最後に終わるからです。彼らのコードは、本当に何も得られないために、良いものをすべて放棄したため、ドロドロになったのです。

最初に良質で読みやすいコードを書くことで、パフォーマンスの問題のほとんどは自ずと解決されるでしょう。そして、後でパフォーマンスが不足していることに気づいた場合、素晴らしくきれいなコードにプロファイラーを追加して、問題がどこにあるのかを見つけるのは簡単です。

以上のことから std::queue は単なるアダプタに過ぎません。これは安全なインターフェイスを提供しますが、内部では別のコンテナを使用します。この基礎となるコンテナを選択することができ、これによってかなりの柔軟性を得ることができます。

では、どの基礎となるコンテナを使えばいいのでしょうか？私たちが知っているのは std::list と std::deque はどちらも必要な機能を備えています ( push_back() , pop_front() そして front() など）、ではどうやって決めればいいのでしょうか？

まず、メモリの割り当て（および解放）は、一般に、OSに出かけていって何かをしてもらうことになるため、すぐにできることではないことを理解してください。A list は、何かが追加されるたびにメモリを割り当て、それがなくなると割り当てを解除しなければなりません。

A deque はチャンクで割り当てます。これは list . リストと同じように考えてください。しかし、各メモリチャンクは複数のノードを保持することができます。(もちろん、私が提案するのは がどのように動作するのかを本当に学ぶことをお勧めします。 .)

ということで、これだけでは deque の方が性能が良いはずです。なぜなら、それほど頻繁にメモリを処理する必要がないからです。一定の大きさのデータを扱うという事実もあり、リストが常に割り当てと解放を繰り返すのに対し、データを最初に通過した後はおそらく割り当てる必要はないでしょう。

理解すべき 2 つ目の点は キャッシュのパフォーマンス . RAM に出力するのは遅いので、CPU は本当に必要なときに、メモリの塊をキャッシュに戻してこの時間を最大限に活用します。なぜなら deque はメモリチャンクで割り当てられるので、このコンテナ内の要素にアクセスすると、CPU はコンテナの残りの要素も持ち帰ることになります。これで、これ以上 deque へのさらなるアクセスは、データがキャッシュにあるため、高速になります。

これは、データが一度に一つずつ割り当てられるリストとは異なります。つまり、データがメモリ内のあちこちに散らばってしまう可能性があり、キャッシュの性能が悪くなります。

ということを考えると deque の方が良い選択であるはずです。を使用する際のデフォルトのコンテナであるのはこのためです。 queue . とはいえ、これはまだ（非常に）経験的な推測に過ぎません。 deque を1つのテストに、そして list を使用すると、本当に確実です。

しかし、覚えておいてほしいのは、きれいなインターフェイスでコードを動作させ、それからパフォーマンスを心配することです。

Johnは list または deque を使用すると、パフォーマンスが低下します。もう一度言いますが、彼も私も自分でプロファイリングしてみないと確かなことは言えませんが、コンパイラは queue が行う呼び出しをコンパイラがインライン化する可能性があります。つまり、あなたが queue.push() と言ったとき、それは本当にただ queue.container.push_back() と表示され、関数呼び出しは完全にスキップされます。

もう一度言いますが、これは経験則による推測に過ぎませんが、このように queue を使用しても、基盤となるコンテナをそのまま使用する場合と比較して、パフォーマンスが低下することはありません。前にも言ったように queue を使用します。これはクリーンで使いやすく安全だからです。