大量のオブジェクト (弾丸など、絶えず変化するものなど) を保存し、インデックスで削除するにはどうすればよいですか? vector::erase はあまり効率的ではないと聞いたことがあります。
質問する
852 次
6 に答える
2
std::map(または C++11s )を使用するstd::unordered_mapと、これらのコンテナーは、挿入操作と消去操作のランタイムの複雑さをより適切に償却できます。std::listもオプションです (明らかなオプションですが、多くのゲーム シナリオでさらに重要なクイック ルックアップ/検索も可能になるため、最初に他のオプションについて言及しました)。
より高いレベルでは、C++ コンテナーと、一般的なランタイムの複雑さについて必ず読む必要があります。コンテナー構造の賢明な選択は、優れたパフォーマンスに不可欠です。
于 2012-07-10T15:51:07.670 に答える
1
(in) 有名な Alexandrescu は、寿命の短い動的な小さなオブジェクトが遅い new/free 演算子に関する主な問題を考慮し、カスタム アロケーターの使用を推奨しています。std::map はそのようなオブジェクトの多くを使用します (内部で赤黒ツリーを使用します)。そのため、事前に割り当てられたオブジェクトのプールを使用するか、std::map をカスタム アロケーター (おそらく Alexandresu の Loki ライブラリから取得したもの) で使用することをお勧めします。 )
于 2012-07-10T19:28:22.970 に答える
1
unordered_set<Bullet*>うまくいきます。次に、Bullet*どこでも a を使用するだけで、インデックス作成を忘れることができます。オブジェクトプールなどから割り当てるのが最適です。
または、標準が親切にインターフェイスを台無しにしたstd::unordered_map<Bullet*, std::unique_ptr<Bullet>>ため、代わりに例外の安全性などを改善する必要がある場合があります。
于 2012-07-10T15:53:52.843 に答える
0
vector::erase順序を維持するためにスペースを埋めるために次のすべての要素を移動する必要があるため、あまり効率的ではありません。ただし、順序を保持する必要はないようです。その場合、要素を最後の要素に置き換えてから最後の要素を削除することで、要素をより迅速に削除できます。
std::swap(bullets[index_to_remove], bullets.back());
bullets.pop_back();
于 2012-07-10T17:39:44.640 に答える
0
ベクトル内のインデックスで弾丸を識別している場合はerase、良い考えではありません。次のすべての要素のインデックスが変更されます。箇条書きがそのインデックスによって識別されるという事実は、選択をいくらか制限します。その場合の最善の解決策は、おそらく単純にエントリを無効としてマークし、後で再利用することです。無効なインデックスのリストを保持するか ( で簡単に実行できますstd::vector)、新しいインデックスを作成するたびにベクターをスキャンするだけです。銃弾。さまざまな種類の弾丸がある場合 (ゲームが進化するにつれて、おそらくそうなるでしょう)、ベクトルにポインターを保持しながら、弾丸を動的に割り当てる必要があります。null ポインターは、invalid の適切な選択です。
于 2012-07-10T16:23:58.840 に答える
0
ゲーム エンジン プログラミングに関する非常に限られた中古の知識から、動的メモリ割り当ては可能な限り避けています。したがって、unordered_setまたははlist、頻繁に削除される「大量」の主要なノーになります。
編集：@James Kanzeの回答を読んだ後、削除された弾丸を最後の要素と交換するという@Cameronの提案は、ライブの弾丸のインデックスを変更するため機能しないことに気付きました。ジェームズの提案、またはおそらくビットベクトルを使用して、死んだ弾丸をマークする必要があると思います。
箇条書きを配列にコンパクトに保つと、キャッシュのパフォーマンスも向上します。ハッシュ テーブルは の赤黒木よりもうまくキャッシュstd::mapできますが、インデックスで箇条書きを既に参照している場合、なぜハッシュのオーバーヘッドが発生するのでしょうか?
于 2012-07-10T16:08:42.900 に答える