どのSTLコンテナが私のニーズに最も適していますか？私は基本的に10要素幅のコンテナを持っており、最も古い要素を使用push_backしながら（約100万回）新しい要素を継続的に使用しています。pop_front
私は現在std::deque、タスクにaを使用していますがstd::list、自分自身を再割り当てする必要がないため、aの方が効率的かどうか疑問に思っていました（または、std::dequeaをstd::vector？と間違えている可能性があります）。それとも、私のニーズに合ったさらに効率的なコンテナはありますか？
PSランダムアクセスは必要ありません
無数の答えがあるので、あなたは混乱するかもしれませんが、要約すると：
を使用しstd::queueます。この理由は単純です。それはFIFO構造です。FIFOが必要な場合は、を使用しstd::queueます。
それはあなたの意図を他の誰か、そしてあなた自身にさえ明確にします。Astd::listまたはstd::dequeしません。リストはどこにでも挿入および削除できますが、これはFIFO構造が想定していることではなく、dequeどちらの端からも追加および削除できます。これもFIFO構造では実行できません。
これが、を使用する必要がある理由ですqueue。
さて、あなたはパフォーマンスについて尋ねました。まず、この重要な経験則を常に覚えておいてください。最初に優れたコード、最後にパフォーマンスです。
この理由は単純です。清潔さと優雅さの前にパフォーマンスを追求する人々は、ほとんどの場合、最後に終わります。彼らのコードは、本当に何も得られないようにするために良いものをすべて放棄したので、どろどろになります。
読みやすい優れたコードを最初に作成することで、パフォーマンスの問題のほとんどが解決します。そして、後でパフォーマンスが不足していることに気付いた場合は、プロファイラーをすてきでクリーンなコードに追加して、問題がどこにあるかを簡単に見つけることができます。
とはいえ、これstd::queueは単なるアダプターです。安全なインターフェースを提供しますが、内部で別のコンテナーを使用します。この基礎となるコンテナを選択できます。これにより、かなりの柔軟性が得られます。
では、どの基盤コンテナを使用する必要がありますか？私たちはそれを知ってstd::listおり、std::deque両方とも必要な機能（、、、および）を提供しますpush_back()。pop_front()ではfront()、どのように決定するのでしょうか。
まず、メモリの割り当て（および割り当て解除）は、OSに出て何かをするように依頼する必要があるため、一般的には簡単なことではないことを理解してください。Alistは、何かが追加されるたびにメモリを割り当て、それがなくなると割り当てを解除する必要があります。
deque一方、Aはチャンクで割り当てます。割り当ての頻度は。より少なくなりlistます。これをリストと考えてください。ただし、各メモリチャンクは複数のノードを保持できます。（もちろん、それがどのように機能するかを実際に学ぶことをお勧めします。）
したがって、それだけではdeque、メモリをあまり処理しないため、パフォーマンスが向上するはずです。一定のサイズのデータを処理しているという事実と相まって、データを最初に通過した後に割り当てる必要はおそらくないでしょうが、リストは常に割り当てと割り当て解除を行います。
次に理解すべきことは、キャッシュのパフォーマンスです。RAMへの出力は遅いため、CPUが本当に必要な場合は、メモリのチャンクをキャッシュに戻すことで、この時間を最大限に活用します。はメモリチャンクに割り当てるため、dequeこのコンテナ内の要素にアクセスすると、CPUがコンテナの残りの部分も元に戻す可能性があります。dequeこれで、データがキャッシュにあるため、へのそれ以降のアクセスが高速になります。
これは、データが一度に1つずつ割り当てられるリストとは異なります。これは、データがメモリ内のいたるところに分散する可能性があり、キャッシュのパフォーマンスが低下することを意味します。
したがって、それを考慮すると、adequeがより良い選択であるはずです。これが、を使用する場合のデフォルトのコンテナである理由ですqueue。とはいえ、これはまだ（非常に）知識に基づいた推測にすぎません。確実に知るには、deque一方のテストともう一方のテストでこのコードをプロファイリングする必要があります。list
ただし、覚えておいてください。コードをクリーンなインターフェイスで動作させてから、パフォーマンスについて心配してください。
listJohnは、またはをラップするdequeとパフォーマンスが低下するという懸念を提起します。繰り返しになりますが、彼も私も、自分でプロファイリングしなくても確実に言うことができますが、コンパイラーが行う呼び出しをインライン化する可能性がありqueueます。つまり、と言うとqueue.push()、実際にはqueue.container.push_back()、関数呼び出しを完全にスキップして、と言うだけです。
繰り返しになりますが、これは知識に基づいた推測にすぎqueueませんが、基礎となるコンテナをrawで使用する場合と比較した場合、を使用してもパフォーマンスが低下することはありません。前に言ったように、queueそれはきれいで、使いやすく、安全であり、それが本当に問題のプロファイルとテストになる場合は、を使用してください。
チェックアウトstd::queue。基になるコンテナタイプをラップし、デフォルトのコンテナはですstd::deque。
パフォーマンスが本当に重要な場合は、Boost循環バッファライブラリを確認してください。
最も古い要素を使用しながら（約100万回）、継続的に
push_back新しい要素を作成します。pop_front
コンピューティングでは、100万は実際には大きな数ではありません。他の人が示唆しているようにstd::queue、最初の解決策としてを使用してください。万が一、速度が遅すぎる場合は、プロファイラーを使用してボトルネックを特定し（推測しないでください）、同じインターフェイスを備えた別のコンテナーを使用して再実装します。
どうしてstd::queue？それが持っているのはpush_backとpop_frontです。
を使用しますが、2つの標準クラスstd::queueのパフォーマンスのトレードオフに注意してください。Container
デフォルトでstd::queueは、は。の上にあるアダプタですstd::deque。通常、これにより、多数のエントリを含む少数のキューがある場合に良好なパフォーマンスが得られます。これは、おそらく一般的なケースです。
ただし、 std::dequeの実装を知らないでください。具体的には：
"... dequesは通常、最小メモリコストが大きく、1つの要素のみを保持するdequeは、完全な内部配列を割り当てる必要があります（たとえば、64ビットlibstdc ++のオブジェクトサイズの8倍、オブジェクトサイズの16倍または4096バイトのいずれか大きい方） 、64ビットlibc ++の場合）。」
それを相殺するために、キューエントリがキューに入れたいもの、つまりサイズが適度に小さいと仮定すると、それぞれが30,000エントリを含む4つのキューがある場合、std::deque実装が選択のオプションになります。逆に、それぞれが4つのエントリを含む30,000のキューがある場合、そのシナリオではオーバーヘッドをstd::list償却することは決してないため、実装が最適になる可能性が高くなります。std::deque
キャッシュがどのように重要であるか、Stroustrupがリンクリストをどのように嫌うかなどについて多くの意見を読むことができます。これらはすべて、特定の条件下で当てはまります。std::deque2番目のシナリオでは、デフォルトの実装が実行される可能性は非常に低いため、ブラインドフェイスでそれを受け入れないでください。使用状況を評価して測定します。
このケースは非常に単純なので、自分で作成することができます。これは、STLの使用に多くのスペースが必要なマイクロコントローラーの状況でうまく機能するものです。割り込みハンドラからメインループにデータとシグナルを渡すのに最適な方法です。
// FIFO with circular buffer
#define fifo_size 4
class Fifo {
uint8_t buff[fifo_size];
int writePtr = 0;
int readPtr = 0;
public:
void put(uint8_t val) {
buff[writePtr%fifo_size] = val;
writePtr++;
}
uint8_t get() {
uint8_t val = NULL;
if(readPtr < writePtr) {
val = buff[readPtr%fifo_size];
readPtr++;
// reset pointers to avoid overflow
if(readPtr > fifo_size) {
writePtr = writePtr%fifo_size;
readPtr = readPtr%fifo_size;
}
}
return val;
}
int count() { return (writePtr - readPtr);}
};