c++ - 什么样的容器适合 "The Powder Toy"风格的沙箱？

Question

基本上我正在制作一款类似于 The Powder Toy 的游戏。在一个给定的帧中，世界最多可以有 256,000 个粒子。在我旧的 Javascript 实现中，我遍历了每个像素，这导致了严重的延迟，因为即使只有大约 20,000 个粒子处于事件状态，256,000 个像素也需要经过很多。我决定改用一个装满所有当前事件粒子的容器，但随后遇到了一个问题，即在特定坐标处查询容器中的粒子也是处理器密集型的。因此我想出了一个简单的解决方案，我应该将所有粒子保存在一个查找表(二维数组)中，还有一个堆( active 粒子数组)，并在使用查找表作为引用的同时迭代堆。对堆所做的任何事情都会对查找表完成，反之亦然。这在 Javascript 中运行良好，但现在因为我需要将我的程序移植到 C++，所以我很难找到一个好的容器来容纳堆。 vector 的添加和删除速度非常慢，我无法通过引用从 vector 中轻松删除对象。

我应该使用哪个容器，如果有更好的方法来处理粉末玩具中的颗粒，那是什么？提前致谢，对于那些不熟悉 The Powder Toy 的人，这是一张图片。

注意每个像素都有一个粒子，类似的构建在我的电脑上运行得非常快。我想知道他们是怎么做到的...

Answer 1

vector 可以很好地解决这类问题。它们提供连续存储，因此可以更好地使用缓存。

尝试通过构造函数或使用 std::vector::reserve() 预先分配适当的 vector 容量。否则，每当您的 vector 大小超过当前容量时，都会触发已分配存储空间的自动重新分配。

您还可以尝试使用 std::swap() 然后使用 std::vector::pop_back() 从 vector 中删除元素，如下所示:

std::swap(vect.back(), vect[1]);
vect.pop_back();

代替:

std::vector::erase()

std::vector::pop_back() 和std::swap() 的复杂度都是常量，std::vector::erase() 是线性的。

但是如果您需要保留元素的顺序，swap - pop 方法就没有用了。