私のアプリケーションでは、STD ベクトルを使用しています。最後にベクトルに挿入していますが、ベクトルからランダムに消去します。つまり、要素は途中、前からどこでも消去できます。これらの 2 つは唯一の要件です。1) 最後に挿入 2) どこからでも消去します。
消去はデータのシフトを行うため、STD Listを使用する必要があります。または、何らかの理由でコードに Vector を保持しますか??
コメントをお願いします。Vector がより良いオプションである場合、ここにリストする方が良いでしょうか?
std::vectoroverを使用する主な理由の 1 つstd::listは、キャッシュの局所性です。この点で、リストはひどいものです。リストの要素は、記憶の中で断片化される可能性がある (そして通常は断片化されている) からです。これにより、パフォーマンスが大幅に低下します。
std::vectorほぼ常に使用することをお勧めする人もいます。パフォーマンスの観点からは、挿入や削除の複雑さよりもキャッシュの局所性の方が重要な場合がよくあります。
このチート シートを参照してください。結論はリストになります。
リストは、一定時間内の任意の既知の位置での削除をサポートします。
その位置を見つけるには、ベクトルを変更するのと同じように線形時間がかかります。
リストの唯一の利点は、(ほぼ) 同じ位置で繰り返し消去 (または挿入) する場合です。
多かれ少なかれ無作為に消去している場合、ベクトルのより良いメモリ局所性が最終的に勝つ可能性があります。
確認する唯一の方法は、測定して比較することです。
それは多くの要因と、データをどのように使用しているかによって異なります。
1 つの要因: コレクションの順序を維持する消去が必要ですか? または、順序の変化に耐えることができますか？
その他の要因: コレクションにはどのようなデータが含まれていますか? (数値: 整数/浮動小数点数) || || ポインタ || オブジェクト
秩序を保っていない
データが基本的な数値またはポインターである場合は、引き続き使用vectorできます。1 つの要素を削除するには、ベクトルの最後の要素を削除された位置にコピーしてから、pop_back(). これにより、すべてのデータの移動を回避できます。
オブジェクトを使用する場合、コピーする必要があるオブジェクトが小さい場合でも、同じ方法を使用できます。
秩序を保つ
リストはここであなたの友達になるかもしれませんが、それでも、データのサイズ、リストのサイズなどに応じて、いくつかのテストが推奨されます