3

小さな「パーティクル」があるゲームを作成しています。それらの数は非常に頻繁に (数秒ごとに) 変化しており、それらを保存する最良の方法は何だろうと考えています。これは良いですstd::vectorかstd::deque？

決して使用されない (上限がある) スペースを (そのコンテナー内に) 予約しても大丈夫ですか?

4

3 に答える 3

7

パーティクルを削除する代わりに、順序が問題にならない場合は、ベクター内の他のパーティクルに置き換えることができます (問題はないと思います)。

std::vector<Particle> particles;

インデックスでパーティクルを削除するiと、空のスペースを最後のスペースで埋めるだけです:

particles[i] = particles.back();
particles.pop_back();

ポインターのベクトルを使用すると、さらに高速化できます。

于 2012-07-11T08:13:24.913 に答える
2

ベクトルに十分なスペースを確保する場合、ベクトルのコンテンツをコピーする必要がないため、サイズ変更は悪くありません。

一方、デキューは、大規模な再割り当てが回避されるため、特に大規模なシーケンスで、容量が自動的に管理されるベクターよりも効率的に拡張できます。

于 2012-07-11T08:11:42.110 に答える
2

それは本当に使い方次第です。ベクトルがソートされていない場合、実際にその粒子を削除している場合、ベクトル内でそれを見つけるのに O(n) の複雑さがあり、データが連続したままになるようにベクトル全体がコピーされます。両端キューを使用すると、見つけるのにまだ O(n) かかりますが、削除は簡単です。ただし、次のように繰り返している場合

foreach (particle in particles)
{
    if(particle.update() == END_OF_LIFE)
    {
        particle.alive = false;
    }
    else
    {
        particle.draw();
    }
}

大きなオーバーヘッドなしでそれを行うことができますが、新しい粒子を挿入するには、各粒子を繰り返し処理して、置き換えることができる最初の「死んだ」粒子を見つける (O(n)) か、その情報を別のファイルで追跡する必要があります。 std::リスト。

効果的に答えるために知っておくべきことが 1 つあります。特定の粒子にインデックスを付ける必要がありますか (「リストの 1000 番目の粒子を教えてください」)。また、何らかの ID で検索したことはありますか (「id=421932 のパーティクルを検索」)。前者の場合、ベクトルは一定時間で実行されますが、後者は std::unordered_set (hash_set の c++ x11 バージョン、boost pre x11 の同様のオプション) および std::set によるログイン時間によって一定時間で実行されます。

于 2012-07-11T08:33:11.293 に答える