オブジェクトの「リスト」があり、そこからオブジェクトをランダムな位置に取得して、このリストの前にプッシュします。この種の操作のみが実行されます。したがって、リストの最後にすばやくアクセスする必要はありません。他の場所へのアクセスは、その先頭と平均的なアクセスだけです。
これに最適なコンテナはどれですか？を考えていたのですが、操作が効率的でないstd::vectorことを読みました。で、フロントへのアクセスが早いということでinsert思いついたのですが、特定位置方式の効率はどうですか？std::dequeerase
助けてくれてありがとう。
ガイドラインを提供することはできますが、決定的な答えはありません。コレクションとオブジェクトのサイズに大きく依存するため、自分でベンチマークする必要があります。
std::vectorより多くのデータをコピーする必要がありますが、より良いランダム アクセス時間 (O(1) と O(n) の場合std::list) とキャッシュの局所性が支配するため、より高速になります。std::list、ランダムなオブジェクトを選択するには O(n) が必要ですが、多くの大きなオブジェクトのコピーは非常に遅いため、挿入ははるかに高速になるため、高速になります。しかし、これら 2 つのシナリオの境界線が正確にどこにあるのかは、私にはわかりません。
さらに、挿入の代わりに要素を交換することで問題を解決できる場合、これは非常に簡単です。常に . を使用してstd::vectorください。
この回答に基づいて: https://stackoverflow.com/a/471481/1284631 (また、これに基づいて: https://stackoverflow.com/a/471461/1284631 )、リストを作成します。追加、反復、挿入、および削除は安価です。
PS: これは、ランダムな位置がインデックス ベースであるかどうかによって異なります (つまり、数値的にどの位置を知っているか、またはリストを反復処理してそのプロパティをテストすることにより、前面に移動するオブジェクトが得られるかどうか)。
したがって、リストを反復せずに位置がわかっている場合は、ベクトルを使用します。位置がコレクションを反復する必要がある場合は、リストに進みます。