迭代通过具有共同基类的对象在有名的记忆中

Question

我试图找出如何迭代在内存中连续共享公共基本父类的对象的容器(如std :: vector).

为了演示这个问题,让我们使用以下示例.

class Base
{
public:
    Base();
    virtual void doStuff() = 0;
};

class DerivedA : public Base
{
private:
    //specific A member variables
public:
    DerivedA();
    virtual void doStuff();
};

class DerivedB : public Base
{
private:
    //specific B member variables
public:
    DerivedB();
    virtual void doStuff();
};

现在,使用std :: vector进行迭代会将对象保留在连续的内存中,但是由于没有派生属性的空间,我们会遇到切片.

所以我们必须使用像这样的指针的多态技术

int main ()
{
    std::vector<Base*> container;
    container.push_back(new DerivedA());
    container.push_back(new DerivedB());

    for (std::vector<Base*>::iterator i = container.begin(); i!=container.end(); i++)
    {
        (*(*i)).doStuff();
    }
}

据我所知,应该可以正常工作,因为这些类已经实现了.

问题: 现在,向量包含连续内存中的指针,但这并不意味着它们指向的地址是.

因此,如果我希望能够随时在对象中删除和插入对象,则对象将遍布内存中的所有位置.

问题: 似乎每个人都建议使用std :: vector方式,但为什么它在内存中不能连续迭代(假设我们实际使用指针)并不被认为是有问题的？

我是否被迫采用复制面食方式？

int main ()
{

    std::vector<DerivedA> containerA;
    DerivedA a;
    containerA.push_back(a);

    std::vector<DerivedB> containerB;
    DerivedB b;
    containerB.push_back(b);

    for (std::vector<DerivedA>::iterator i = containerA.begin(); i!=container.end(); i++)
    {
        (*i).doStuff();
    }
    for (std::vector<DerivedB>::iterator i = containerB.begin(); i!=container.end(); i++)
    {
        (*i).doStuff();
    }
}

我猜可能没有一个真正的解决方案,因为在内存中保持各种大小的线性对象并没有真正意义,但如果有人能给我一些建议我会很感激.

Answer 1

让我们按顺序回答问题。

问：如何创建连续的异构容器？

答：你不能。

假设您使用了一些 placement new 恶作剧来在内存中排列对象，如下所示：

  [B ][DA  ][DB      ][B ][B ][DB      ][DA  ]

迭代机制如何知道迭代指针从一个对象到下一个对象前进多远？从第一个元素到第二个元素的字节数与第二个到第三个元素的字节数不同。

连续数组必须是同质的，因为所有元素从一个对象到下一个对象的距离都是相同的。您可能会尝试在每个对象中嵌入一个大小，但是您基本上拥有一个链接列表而不是一个数组（尽管具有良好的 局部性）。

这种推理导致了使用指针数组的想法，对此您提出了下一个问题：

问：为什么它不能连续迭代不被认为是有问题的

A：没有你想象的那么慢。

您关心的似乎是以下指向分散内存位置的指针的性能。但遵循这些指导方针的成本不太可能占主导地位。在有确凿的证据证明需要这些优化之前，不要沉迷于内存布局等微观优化。

问：我是否被迫以复制意大利面的方式来做？

答：不！

在这里，人们关心的似乎是可维护性而不是性能。在我看来，可维护性更为重要，并且尽早考虑是一件好事。

为了可维护性，您已经有了一个很好的解决方案：维护 的向量Base*。

如果你确实想使用多个向量，还有比复制粘贴更好的方法：使用模板函数，如下所示（未经测试）：

  [B ][DA  ][DB      ][B ][B ][DB      ][DA  ]

然后在每个容器上调用它：

template <class T>
void doStuffToVector(std::vector<T> &vec)
{
  for (std::vector<T>::iterator i = vec.begin(); i!=vec.end(); ++i) {
    (*i).doStuff();
  }
}

如果您唯一关心的是可维护性，那么指针向量或模板函数就足够了。

问：有什么建议吗？

答：首先，忽略性能，至少就恒定因素而言。专注于正确性和可维护性。

然后，衡量绩效。请注意，这个问题并不是以当前速度和期望速度的陈述开始的。您还没有需要解决的实际问题！

测量后，如果您认为速度太慢，请使用 分析器 找出慢点在哪里。他们几乎永远不会出现在你想象的地方。

举个例子：整个问题和答案都集中在迭代上，但没有人提出虚函数调用doStuff更有可能成为瓶颈这一点！虚函数调用是昂贵的，因为它们是间接控制流，这会给 管道带来重大问题；间接数据访问的成本要低得多，因为 数据缓存通常非常有效地快速满足数据访问请求。

问：（隐含）我将如何优化它？

答：经过仔细测量，你可能会发现这段代码（迭代本身，包括虚函数调度；而不是里面的内容doStuff）是一个瓶颈。这肯定意味着它至少要执行数十亿次迭代。

首先，研究将减少所需迭代次数的算法改进。

接下来，消除虚拟函数调用，例如通过嵌入对象类型的显式指示符并使用if或对其进行测试switch。这将使处理器的 分支预测器更加有效。

最后，是的，您可能希望将所有元素放入一个连续的数组中，以提高局部性并消除间接数据访问。这也意味着消除类层次结构，因此所有对象都是相同类型，要么将所有字段组合到一个类中和/或使用union. 这会损害你的程序的可维护性！有时这是编写高性能代码的成本之一，但实际上很少有必要。

Answer 2

std::vector<T>迭代器假设连续内存中的对象的类型为T，std::vector<T>::iterator::operator++被认为sizeof T是不变的 - 也就是说，它不会咨询特定实例的大小数据。

本质上，您可以将vector和vector::iterator视为指针上的薄外观T* m_data，这iterator++实际上只是一个基本的指针操作。

您可能需要使用自定义分配器并就地new准备数据，并附有索引、链接等。也许可以考虑类似http://www.boost.org/doc/libs/1_58_0/doc/html/侵入式/slist.html

另请参见boost::stable_vector