std::vector是否适合频繁调整大小？

Question

我正在创建一个游戏，其中有小的“粒子”。它们的数量非常频繁地变化（每几秒钟一次），我想知道最好的存储它们的方式是什么。对于这个问题，std::vector 或 std::deque 哪一个更好呢？

如果在容器中保留永远不会被使用的空间（我有上限），这样做是否可以？

- HemoGoblin

---

请提供更多关于使用方法的信息。 - Kiril Kirov

如果你只删除向量的最后一个项目，通常速度会相当快。你能给出最大粒子数吗？ - stefan

让你的代码模块化，这样就可以轻松更换容器类型并进行性能分析。 - Kerrek SB

谢谢您的建议！最大数量通常为100-150，因此我将使用向量并为其保留空间。 - HemoGoblin

Answer 1

如果顺序不重要（我认为它确实不重要），您可以在向量中将一个粒子替换为另一个粒子，而不是删除它。

std::vector<Particle> particles;

当您删除索引i处的粒子时 - 只需使用最后一个粒子填充空白空间：

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

如果使用指针向量，您甚至可以使其更快。

- Andrew

---

我很好奇：你为什么使用resize(..)而不是pop_back()？pop_back()有什么缺点吗？ - stefan

@stefan 这还是有点奇怪。为什么你要使用赋值而不是 swap 呢？ - pmr

我认为使用指针向量并不能提高速度。使用指针向量会失去内存连续的优势。这取决于粒子的实际情况以及所涉及的计算类型。 - Adrien

@Adrien：实际上这取决于粒子的大小。但是只有在简单的解决方案不够快时，你才必须尝试这样的优化。而且可能这种优化会更慢。 - Andrew

在C++11中，你可以写成particles[i] = std::move(particles.back())，获得两全其美的效果。当然，这意味着你的代码依赖于C++11。 - Steve Jessop

Answer 2

如果您为向量保留足够的空间，使用resize是不错的选择，因为它不需要复制向量的内容。

另一方面，在大规模序列中，deque相对于自动管理容量的向量可以更有效地增长，因为它避免了大量的重新分配。

- BЈовић

Answer 3

关键在于使用。如果您的向量未排序，并且您实际上正在删除该粒子，则在向量中查找它的复杂度为O(n)，并且整个向量将被复制，以便数据保持连续。对于双端队列，仍需要O(n)来查找，但是删除操作很简单。但是，如果您正在进行迭代操作

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

您可以毫不费力地完成此操作，但是如果要插入新粒子，则需要通过迭代每个粒子以找到您可以替换的第一个“死”粒子（O(n)），或者在单独的std :: list中跟踪该信息。

为了有效地回答问题，我们需要知道您是否需要索引到特定的粒子（“给我列表中的第1000个粒子”）？另外，您是否按某个ID查找（“查找具有id = 421932的粒子”）？ 如果是前者，则vector会以常数时间执行，而后者将由std :: unordered_set（hash_set的c ++ x11版本，在boost pre x11中有类似选项）以常数时间执行，std :: set则需要logn时间。

- Rollie