什么是STL容器来执行元素之间的移除？

我需要选择一个容器来容纳指向我定义的类型的指针（Particle）。我正在使用预先分配的粒子Object Pool（其中包含预先分配在std :: vector上的对象）。什么是STL容器来执行元素之间的移除？

我的粒子发射器在粒子池需要发射时要求粒子池（为了避免游戏中的粒子分配）。当一个粒子到期时，它返回到粒子对象池。你可以看到，当我迭代我的粒子参考容器（需要选择一个）来更新它时，我将不得不检查哪些粒子已经过期（lifetime <= 0.0）并将它们返回给粒子池，过期的颗粒可能在容器中的任何位置。

我一直在思考如何使用std::list，这里的原因：

名单（据我所知）提供了在开始一定时间的插入和恒定时间去除在任何时候（假设你已经迭代到这一点）。

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

EDIT：

为了解释自己好一点：

颗粒在发射极的寿命时间是不完全相同，这取决于一个范围，例如，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 
     } 
    } 
}

来源

2011-03-10 Goles

对于顺序容器，总是从'std :: vector'开始。然后配置文件，如果容器操作是一个问题，请尝试另一个容器。 [通常你会发现自己坚持'std :: vector'。]（http://stackoverflow.com/questions/5056973/when-do-you-prefer-using-stdlistt-instead-of-stdvectort/5057001#5057001 ） – sbi 2011-03-10 19:34:05

“恒定时间”和std :: list的问题是常数很大！对于std :: vector，时间是可变的，但很小。你的选择！ :-) – 2011-03-10 19:53:43

我并不完全按照你的算法，但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(); 
}

来源

2011-03-10 19:25:29

我认为正确的术语是_amortized常量time_，但是，是的，从'std :: vector'开始，并且只有在使用另一个容器时分析后才会有所改进。 [但是，我怀疑你会经常发现。]（http://stackoverflow.com/questions/5056973/when-do-you-prefer-using-stdlistt-instead-of-stdvectort/5057001#5057001） – sbi 2011-03-10 19:35:49

更好的会是使用'std :: swap（v [i]，v.back（））; v.pop_back（）;'，因为'swap'是非抛出的，常量时间和便宜的（对于'swap'的所有非白痴实现）。 – GManNickG 2011-03-10 20:12:33

嘿，我编辑了我的文章。在一个元素上调整矢量大小的成本是多少？当然，这比删除其中的元素要好，但如果我经常这样做，那么你认为性能会受到太多影响吗？（我将不得不介绍） – Goles 2011-03-10 20:15:57

假设你不需要直接索引（operator[]）和你只是正常遍历容器，list听起来就好了。您甚至可以使用splice在不进行内存分配或取消分配的情况下以恒定时间移动列表节点。

来源

2011-03-10 19:24:47

嘿，在那里，我编辑了我的帖子，如果你认为你的回复仍然适用，那将会很棒:)。 – Goles 2011-03-10 20:17:03

听起来就像std::list是要走的路。这是假设你肯定想在从中间移除对象的同时迭代列表。请注意，当您从中间移除时，大多数其他容器会使迭代器失效; std::list没有。其它建议：

如果你关心空间（很多），你可以尝试Boost.Intrusive
如果你愿意使用非标准集装箱，给slist（单链表，GCC支持）一试 - 它将节省空间，在删除元素时节省一些（小）运行时成本，因为您正在减少必须更新的指针数量。这与双重链接的std::list相比较。

来源

2011-03-10 19:27:18 phooji

为什么不使用priority queue？这样你就不必遍历所有活动的粒子。

编辑：第二个想法：我不太确定这实际上可以工作，这取决于您的算法（我承认并没有完全理解）。如果您在更改生命周期值在容器中，队列可能根本不起作用。但是，如果你不改变这个值（例如你设置了插入它们时粒子过期的时间，然后只检查第一个入口与当前时间），我仍然认为这是你最好的选择。（请注意，优先队列只是默认内部使用std::vector的适配器。）

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

来源

2011-03-10 19:29:15 user634618

+1：也是一个好主意 – phooji 2011-03-10 19:31:07

我编辑了我的帖子，生命周期值不会改变，但对于所有的粒子它不一样。粒子寿命取决于随机的“范围”值，例如：5.0秒+ - 范围（0.0,0.5）（其中范围给出了给定参数之间的随机数） – Goles 2011-03-10 20:14:11

是的，但看起来您可以确定“过期日期“，只需将您的（随机）生命周期添加到当前时间，然后存储结果。（到期日期在初始化之后不会改变，直到粒子从容器中移出）。优先级队列将确保内部的所有粒子都是弱有序的，所以您只需弹出条目，直到最后的“到期日期”为止。 – user634618 2011-03-10 20:25:12

我完全不理解，但;

一组粒子指针可以证明它也是值得的。插入日志（n）删除日志（n）
如果你大多数迭代本地化可能会有很大的影响（我不知道stl列表在这方面效率如何，但stl向量肯定是更好的），它可能是值得标记而不是删除

来源

2011-03-10 19:32:27

什么是STL容器来执行元素之间的移除？

回答

相关问题