什么STL容器可以在中间执行元素删除操作？

Question

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

我的粒子发射器在需要发射时向粒子池请求粒子（以避免游戏中的粒子分配）。当粒子过期时，它将返回到 Particle 对象池。

正如您所看到的，当我迭代通过粒子参考容器（需要选择一个）以进行更新时，我必须检查哪些粒子已过期（lifetime <= 0.0）并将其返回到粒子池，过期的粒子可能在容器中的任何位置。

我一直在思考使用 std::list，以下是原因：

列表（据我所知）提供了在开头插入和在任何点上删除的常数时间（假设您已经迭代到该点）。

欢迎就如何更好地适应您的容器建议提出任何建议或改进。

编辑：

为了更好地解释自己：

发射器中粒子的寿命不完全相同，它取决于一个范围，例如，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
        }   
    }
}

- Goles

---

对于顺序容器，始终使用std::vector。然后进行性能测试，如果容器操作成为问题，请尝试其他容器。通常情况下，您会发现自己仍然坚持使用std::vector。 - sbi

“constant time”和std::list的问题在于常数很大！使用std::vector，时间是可变的，但较小。你来选择吧! :-) - Bo Persson

Answer 1

我并不完全明白你的算法，但是要使用 std::vector 容器，此容器提供了平摊常数时间的 push_back 操作，并且在迭代时可能具有更好的引用局部性。

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

template <typename T>
void remove(std::vector<T> &v, size_t i)
{
    std::swap(v[i], v.back());
    v.pop_back();
}

- Fred Foo

---

我认为正确的术语是分摊常数时间，但是，在使用另一个容器时仅在剖析显示改进时才开始尝试。[然而，我怀疑你不会经常发现这种情况。] (https://dev59.com/i2445IYBdhLWcg3wE2Je#5057001) - sbi

更好的做法是使用std::swap(v[i], v.back()); v.pop_back();，因为swap是非抛出异常、常数时间和廉价的（对于所有非愚蠢的swap实现）。 - GManNickG

嗨，我编辑了我的帖子。调整向量中一个元素的大小的成本是多少？当然，这比在中间删除一个元素要好，但是如果我经常这样做，你认为性能会受到太大影响吗？（我必须进行分析） - Goles

@Mr.Gando，添加单个元素需要平摊常数时间。在典型实现中，重新分配会将向量的容量加倍，因此仅在元素数量增加一倍时才需要重新分配。 - Fred Foo

太棒了！我一直在寻找一种快速、高效（常数时间）的随机访问删除元素的方法。谢谢！ - Joel

Answer 2

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

编辑：再想一想：我不确定这实际上是否有效，这取决于您的算法（我承认我没有完全理解）。如果在容器中存在条目时更改了寿命值，则队列可能根本无法工作。

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

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

- user634618

---

我编辑了我的帖子，生命周期值没有改变，但对于所有粒子来说并不相同。粒子的寿命确实取决于随机的“范围”值，例如：5.0秒+-范围（0.0，0.5）（其中范围在给定参数之间给出一个随机数）。 - Goles

是的，但似乎您可以在插入时确定“过期日期”，只需将（随机）寿命添加到当前时间，然后存储结果即可。（在粒子从容器中移除之前，过期日期不会更改）。优先队列将确保容器内的所有粒子弱有序，因此您只需要弹出条目，直到顶部的“过期日期”在未来即可。 - user634618

Answer 3

假设您不需要直接索引（operator[]），而只是通常地迭代容器，那么使用list就足够了。您甚至可以使用splice在常数时间内移动列表节点，而无需进行任何内存分配或释放。

- Mark B

---

嗨，我编辑了我的帖子，如果你认为你的回复仍然适用，那就太好了 :)。 - Goles

Answer 4

听起来像是要使用std::list。这是在您确定要在移除对象时迭代列表的情况下。请注意，大多数其他容器在从中间删除时会使迭代器失效； std::list则不会。其他建议包括：

• 如果您非常关心空间，请尝试Boost.Intrusive
• 如果您愿意使用非标准容器，请尝试slist（单向链表；gcc支持此功能）- 它将节省空间，并且当您减少需要更新的指针数量时将为您节省一些（小）运行时间成本。与双向链接的std::list相比。

- phooji

Answer 5

我并没有完全理解，但;

• 一组粒子指针也可能证明其任务的价值。插入log(n)移除log(n)

• 如果您大多数情况下是迭代，那么局部性可能会产生很大的影响（我不确定STL列表在这方面的效率如何，但STL向量肯定更好），而且标记而不是删除可能会更有价值。

- Ronny Brendel