オブジェクトを作成して頻繁に殺すゲームをやっています。次のオブジェクトが常に前のオブジェクトよりも新しくなるように、オブジェクトのリストを線形にループできる必要があるため、オブジェクトのレンダリングは正しくなります (オーバーラップします)。また、近くのオブジェクトをすばやく見つけるために、各オブジェクトのポインターを四分木に格納できる必要もあります。
私の最初の考えは を使用するstd::listことでしたが、これまでにこのようなことをしたことがないので、これについての専門家の考えを探しています.
どの容器を使用すればよいですか?
編集:私は前から削除しているだけではありません:オブジェクトは任意の順序で削除できますが、常にリストの最後に追加されるため、最後の項目が最新です。
std::vectorは、自分が何をしているのかわからない場合に開始することをお勧めするコンテナーです。それがうまくいかないことがわかっている場合にのみ、他のものを選択する必要があります.
とはいえ、定期的にコンテナーの背面に追加し、前面から削除する場合は、おそらくstd::dequeが必要です。 [編集]しかし、それはあなたがしていることではないようです。
1 つは挿入順序を維持するため、もう 1 つはクアッドツリー用です。四分木の実装はインターネット上にたくさんあるので、ここでは他の 1 つに焦点を当てます。あなたが提案するようにstd::listを使用すると、削除操作自体が vector または deque よりも高速になります。また、要素が削除されたときに list が他の反復子を無効にしないため、反復子を格納できるという利点もあります。四分木内のオブジェクトは、挿入順序リストへの反復子を維持できます。四分木から要素を削除すると、リストからも O(1) 時間で削除できます。
いつものように、どのコンテナーを使用するかの決定はすべてトレードオフに関するものです。リストには、ベクトルよりもメモリ フットプリントが増加し、連続したメモリ レイアウトが失われます。データ セットが大きい場合、キャッシュの局所性がどれほど重要であるかに驚くかもしれません。確実に知る唯一の方法は、さまざまなコンテナーを試して、アプリケーションに最適なコンテナーを確認することです。
boost::stable_vectorは、削除\反復のニーズに合っている と思います。
そのため、アイテムが追加された順序でコンテナーを反復処理できるようにする必要がありますが、コンテナー内の任意のポイントからアイテムを削除できるようにする必要があります。単純なqueueものは明らかにそれをハックするつもりはありません。
幸いなことに、この作業を簡単に実行できるコンテナが 4 つあり、std::vector、std::list、std::dequeおよびstd::setです。標準的なコンテナの慣用句 (例: begin, end, erase,insertおよび程度は低いが , push_front, pop_back, front)backを使用する場合は、好きなコンテナを使用できます。この 8 つの操作で、std::vector、を切り替えることができ、最初の 4 つだけで も使用できます。コードを記述すれば、さまざまなコンテナー タイプを簡単に切り分けて変更し、少しプロファイリングを行って、パフォーマンスやメモリ オーバーヘッドなどを比較できます。std::liststd::dequestd::set
直感的にstd::listは、おそらく良い賭けであり、おそらくうまくいくでしょstd::setう. ただし、仮定を立てるのではなく、テンプレート ライブラリが提供する一般的なツールを使用して、後で操作する意味のあるパフォーマンス データが得られたら、プロファイリングして最適化してください。