6

我需要选择一个容器来保存指向我定义的类型的指针 ( Particle)。我正在使用预分配的粒子Object Pool（其中包含在 std::vector 上预分配的对象）。

我的粒子发射器在需要发射时向粒子池询问粒子（以避免游戏中的粒子分配）。当一个粒子过期时，它会返回到粒子对象池。

如您所见，当我遍历我的粒子参考容器（需要选择一个）以更新它时，我将不得不检查哪些粒子已过期（lifetime <= 0.0）并将它们返回到粒子池，过期的粒子可能是在容器中的任何位置。

我一直在考虑使用std::list，原因如下：

列表（AFAIK）在开始时提供恒定时间插入，并在任何点提供恒定时间删除（假设您已经迭代到该点）。

欢迎对我的系统提出任何建议或改进，以便更好地适应您的容器建议。

编辑：

为了更好地解释自己：

发射器中粒子的寿命并不完全相同，它取决于一个范围，例如 5.0 秒 +-（0.0 到 0.5）。这是为了给粒子一个随机元素，在固定时间内看起来比所有的都好。

算法伪代码：

    // Assume typedef std::container_type<Particle *> ParticleContainer

void update(float delta)
{   
    ParticleContainer::iterator particle = m_particles.begin();   

    for(; particle != m_particles.end(); ++particle)
    {
        updateParticle(*particle, delta);         //Update the particle

        if ( (*particle)->lifeTime <= 0.0 )
        {
            ParticlePool.markAsFree(*particle);   //Mark Particle as free in the object Pool
            m_particles.remove(*particle);        //Remove the Particle from my own ParticleContainer
        }   
    }
}
4

5 回答 5

12

我不完全遵循您的算法，但std::vector需要提供摊销常数 time push_back。迭代时它也可能具有更好的参考局部性。

如果顺序无关紧要，删除任何项目也是一个常数时间操作：

template <typename T>
void remove(std::vector<T> &v, size_t i)
{
    std::swap(v[i], v.back());
    v.pop_back();
}
于 2011-03-10T19:25:29.690 回答
5

为什么不使用优先队列？这样您就不必遍历所有活动粒子。

编辑：再想一想：我不确定这是否真的有效，具体取决于您的算法（我承认我并不完全理解。）如果您在条目位于容器中时更改该生命周期值，则队列可能根本不起作用。

但是，如果您不更改该值（例如，您在插入粒子时设置了粒子的过期时间，然后仅根据当前时间检查第一个条目），我仍然认为这是您的最佳选择。（请注意，优先级队列只是一个std::vector默认在内部使用的适配器。）

edit2：关于您的编辑。我建议不要为每个粒子存储一个“生命周期”值（它会不断减少，直到它不再是正数），而是存储一个时间戳，表示应该何时移除粒子。初始化粒子时，只需计算粒子何时到期（通过将您的随机“生命周期”添加到当前时间）。这个值不会在你的粒子的生命周期内改变。在判断是否移除粒子时，只要检查当前时间是否大于过期时间戳即可。

于 2011-03-10T19:29:15.957 回答
0

假设您不需要直接索引 ( operator[]) 并且您通常只是在容器上进行迭代，这list听起来很好。您甚至可以使用splice在恒定时间内移动列表节点而无需内存分配或释放。

于 2011-03-10T19:24:47.317 回答
0

听起来像是std::list要走的路。这是假设您肯定要在从中间删除对象的同时遍历列表。请注意，当您从中间移除时，大多数其他容器将使迭代器无效；std::list才不是。补充建议：

  • 如果你关心空间（很多），你可以试试Boost.Intrusive
  • 如果您愿意使用非标准容器，请slist尝试（单链表；gcc 支持这一点）——它将节省空间，在删除元素时为您节省一些（小）运行时成本，因为您正在减少必须更新的指针。这与 a 进行比较std::list，它是双重链接的。
于 2011-03-10T19:27:18.313 回答
0

我不完全理解，但是；

  • 一组粒子指针也可以证明是值得的任务。插入日志(n) 删除日志(n)

  • 如果您主要是迭代局部性可能会产生很大的影响（我不确定 stl 列表在这方面的效率如何，但 stl 向量在这方面肯定更好）并且值得标记而不是删除

于 2011-03-10T19:32:27.127 回答