通过连续内存实现多态性

Question

实际上我没有遇到 "problem"，因为我的代码确实有效。我只是好奇我的实现是否合理且没有风险。

我一直在做一个使用 C++ 的项目，在这个项目中，我首先解析一个文件，然后相应地构建一个有向无环图结构。根据节点的类型，每个节点可能有 0~2 个外邻居。对于不同类型的节点，需要一些打印和访问的函数，我决定用多态来实现。

我的第一个尝试是用节点存储指向其外邻居的指针来实现它。

class Base{
public:
  Base(){}
  virtual ~Base(){}
  virtual foo()=0;
  // ...
protected:
  unsigned _index;
}

class Derived1: public Base{
public:
  foo(){ /*Do something here...*/ }
private:
  Base* _out1;
}

class Derived2: public Base{
public:
  foo(){ /*Do something different here...*/ }
private:
  Base* _out1;
  Base* _out2;
}

int main(){
  std::vector<Base*> _nodeList;
  for(/*during parsing*/){
    if(someCondition){
      _nodeList.pushback(new Derived1);
    }
    // ...
  }
}

由于在构建节点时可能还没有定义节点的外邻，所以我必须添加一些技巧，首先记住外邻的id，并在完成所有节点的构建后将它们连接起来。

但是，由于节点的数量是根据要解析的文件确定的，并且以后不会增长，我认为最好连续存储所有节点，并且每个节点存储其外邻节点的索引而不是指针。这让我可以跳过连接部分，也为其他部分带来了一些小好处。

我现在的版本如下：

// Something like this
class Base{
public:
  Base(){}
  virtual ~Base(){}
  virtual foo()=0;
  // ...
protected:
  unsigned _index;
  unsigned _out1;
  unsigned _out2;
}

class Derived1: public Base{
public:
  foo(){ /*Do something here...*/ }
}

class Derived2: public Base{
public:
  foo(){ /*Do something a little bit different here...*/ }
}

int main(){
  // EDITED!!
  // Base* _nodeList = new DefaultNode[max_num];
  Base* _nodeList = new Derived2[max_num];
  for(/*during parsing*/){
    if(someCondition){
      // EDITED!!
      // _nodeList[i] = Derived1;
      new(_nodeList+i) Derived1();
    }
    // ...
  }
}

我的问题

将不同 class 的对象存储在 newed 数组中是否有任何风险，因为它们都具有相同的大小并且可以使用虚拟对象销毁析构函数？
我一直听说应该避免使用 new[]。我确实找到了一些方法，可以使用带有类型标签的 vector of union 来实现我想要的效果，但对我来说似乎有点脏。有没有办法在 std::vector?
仅仅为了利用虚函数的便利而使用多态是一种坏习惯吗？这么说我的意思是如果每个对象占用的内存对于每个派生 class 已经相同，那么它们可能会合并为一个单独的 class 存储它自己的类型，并且每个成员函数可以只根据自己的类型行事。我选择不这样做，因为在每个成员函数中都有巨大的 switch 结构对我来说也很脏。
这种情况选择连续内存好吗？有什么理由表明这样的选择可能有害吗？

编辑：

原来我犯了很多错误，比如一次问太多问题。我想我会首先关注多态性和 placement new 部分。下面是一个可测试的程序，我所说的“将不同派生的对象 classes 存储在一个新的数组中，它在我的笔记本电脑上的行为如下所示。

#include <iostream>

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

class Derived1: public Base{
public:
  Derived1(){}
  void printType(){ std::cout << "Derived 1." << std::endl; }
};

class Derived2: public Base{
public:
  Derived2(){}
  void printType(){ std::cout << "Derived 2." << std::endl; }
};

int main(){
  Base* p = new Derived1[5];
  new(p+2) Derived2();
  for(unsigned i = 0; i < 5; ++i){
    (p+i)->printType();
  }
}

结果：

Derived 1.
Derived 1.
Derived 2.
Derived 1.
Derived 1.

再次感谢所有的反馈和建议。

Answer 1

Are there any risks to store objects of different class in an newed array, given that they are all of the same size and can be destructed using a virtual destructor?

这不是你的第二个命题：

Base* _nodeList = new DefaultNode[max_num];

_nodeList 是 DefaultNote 的数组，没有别的！尝试在其中存储一些东西，如 _nodeList[i] = ... 将 永远不会 改变存储对象的性质（注意 _nodeList[i] = Derived1; 不是 C++）。如果你想要多态性，你需要通过指针或引用来保留对象。那么第一个解就是正确的：std::vector<Base*> _nodeList;.

I've always heard that the use of new[] should be avoided. I did found some approaches that achieve what I want using vector of union with a type tag, but it seems somewhat dirty to me. Is there a way to achieve polymorphism while storing data in a std::vector?

应避免使用 new[] 是无意义的。如前所述，如果您需要多态性，那么 std::vector<Base*> _nodeList; 是完美的，因为这意味着您可以在 _nodeList 中存储 class 为 Base 或任何对象的地址

的子类型

Is the practice of using polymorphism merely to make use of the convenience of virtual functions consider a bad habit? By saying so I mean if the memory taken by each object is already the same for each derived class, then they may be merged into one single class that store its own type, and each member function can just behave according to its own type. I chose not to do so since it also looks dirty to me to have huge switch structure in each member function.

子类型多态性是虚函数的使用。为什么是坏习惯？如果你不使用虚函数就意味着你在自己构造多态性，这可能是一件非常糟糕的事情。

现在，如果你的派生 classes 就像你的例子中提出的那样，我可以建议你不要使用 subclasses 而只使用 ctor 重载...

Is it good to choose contiguous memory in this case? Are there any reasons that such choice may be harmful?

我不确定是否真的理解您担心的原因。 Contiguous memory是没有害处的。。。这道题至少没说清楚。

Answer 2

问题是通常您不能在向量或数组中分配不同的多态类 - 只能分配指向它们的指针。所以你不能让它连续。

在您的情况下，使用多态性很可能是个坏主意。由于大量虚拟调用的问题和分支预测失败，这将导致内存碎片不良和性能下降。不过，如果节点不多，或者您在代码中不经常使用它，那么它不会影响程序的整体性能。

为避免这种情况，只需将节点的数据（并使其成为普通结构）存储在一个向量中，并利用单独的类来实现这些 foo() 功能。

示例：

std::vector<NodeData> nodes;
class Method1
{
   public:
   static void Process(NodeData& node);
   ...
}

class Method2
{
   public:
   static void Process(NodeData& node);
   ...
}

然后您可以进行一次切换以选择要应用的方法，或者将节点的数据存储在多个向量中，以便每个向量标识要使用的方法。

通过连续内存实现多态性

Achieve polymorphism with contiguous memory

c++

polymorphism

new-operator

stdvector

我的问题