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）），或者在单独的标准::列表。

我们需要知道一件事才能有效地回答——你是否需要索引到一个特定的粒子（“给我列表中的第 1000 个粒子”）？另外，您是否曾经通过某个 ID 查找（“查找 id=421932 的粒子”）？如果是前者，vector 会在恒定时间内执行，而后者将由 std::unordered_set（c++ x11 版本的 hash_set，boost pre x11 中的类似选项）在恒定时间内执行，而 logn 时间由 std::set 执行。

于 2012-07-11T08:33:11.293 回答