相关疑难解决方法(0)

我一直在阅读关于C++的书中的STL容器,特别是关于STL及其容器的部分.现在我明白了每一个都有自己的特定属性,而且我已经接近记住了所有这些...但我还没有掌握的是在哪种情况下使用它们.

解释是什么？示例代码是更受欢迎的.

该文件说std::list效率低下:

std :: list是一个非常低效的类,很少有用.它为插入其中的每个元素执行堆分配,因此具有极高的常数因子,特别是对于小数据类型.

评论:这让我感到惊讶.std::list是一个双向链表,所以尽管它的元件结构效率低下,它支持插入/删除在O(1)的时间复杂度,但这种功能在此引用的段落完全忽略.

我的问题:说我需要一个连续的小尺寸均匀元素的容器,这种容器应支持元素插入/为O删除(1)复杂性和不并不需要随机存取(虽然支持随机访问是好的,它不是必须的这里).我也不希望堆分配为每个元素的构造引入高常量因子,至少当元素的数量很小时.最后,只有在删除相应的元素时,迭代器才会失效.显然我需要一个自定义容器类,它可能(或可能不)是双向链表的变体.我该如何设计这个容器？

如果无法实现上述规范,那么也许我应该有一个自定义内存分配器,比如说,指针分配器？我知道std::list将分配器作为其第二个模板参数.

编辑:我知道从工程的角度来看,我不应该太关心这个问题 - 足够快就足够了.这只是一个假设的问题,所以我没有更详细的用例.随意放松一些要求!

编辑2:据我所知,O(1)复杂度的两种算法由于其常数因子的不同而具有完全不同的性能.

可能重复:
您何时更喜欢使用std :: list <T>而不是std :: vector <T>？

我刚观看了Bjarne Stroustrup对GoingNative'12演讲的录音.我有点困惑.

在本次演讲中,他特别讨论了vectorvs list问题,并建议在很多情况下vector即使你从中间插入和删除也要更快,因为编译器可以优化很多东西并且喜欢紧凑的结构.结论(据我所知)是:首先使用,vector然后再考虑是否需要其他东西.这听起来很合理,但考虑到第一次观察,我应该考虑哪些标准？我一直认为,如果你强烈插入/删除 - 使用列表.这里的一些主题也提出了类似的建议.看到

std :: vector与std :: list与std :: slist的相对表现？

和

STL中的向量与列表

现在根据Stroustrup我错了.

当然,我可以编写几个测试并试图弄清楚在每种特定情况下使用什么,但是有理论上的方法吗？

我需要选择一个容器来保存指向我定义的类型(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
        }   
    }
}

我制作了一个可爱的通用(即模板)List类来处理C++中的列表.原因是我发现这个std::list类在日常使用中非常难看,而且由于我经常使用列表,我需要一个新的.主要的改进是,我的班级,我可以用来[]从中获取物品.此外,还有待实现的是一个IComparer对事物进行排序的系统.

我正在使用这个List类OBJLoader,我的类加载Wavefront .obj文件并将它们转换为网格.OBJLoader包含指向以下"类型"的指针列表:3D位置,3D法线,uv纹理坐标,顶点,面和网格.顶点列表具有必须链接到所有3D位置,3D法线和uv纹理坐标列表中的某些对象的对象.面链接到顶点,网格链接到面.所以他们都是相互联系的.

为简单起见,让我们考虑一下,在某些情况下,只有两个指针列表:List<Person*>和List<Place*>.Personclass包含,其中包括字段List<Place*> placesVisited和Place类包含字段List<Person*> peopleThatVisited.所以我们有结构:

class Person
{
    ...
  public:
    Place* placeVisited;
    ...
};

class Place
{
    ...
  public:
    List<People*> peopleThatVisited;
};

现在我们有以下代码:

Person* psn1 = new Person();
Person* psn2 = new Person();

Place* plc1 = new Place();
Place* plc2 = new Place();
Place* plc2 = new Place();


// make some links between …