c++ - C++中的缓慢递归析构函数调用

Question

我正在使用 C++ 来表示使用引用计数对象的大图。像这样的东西:

// Public class
class Pointer{
  public:
  // Constructors
  Pointer(...){ node = ...; node->counter++;}

  // Copy constructor
  Pointer(Pointer& const other){ node = other.node; node->counter++;}

  // Destructor
  ~Point(){ if(--node->counter==0) delete node;}

  // Other methods
  ...

  Node* node;
};

// Node base class
class Node{
  // Constructor
  Node():counter(0){}

  // Destructor
  virtual ~Node(){}

  // public:
  unsigned long counter;
};

// Node derived class
class NodeDerived : public Node{
  // Constructors and other methods
  ...

  // Destructor
  virtual ~NodeDerived(){ ... }

  // Children
  Pointer children[2];
};

因此有一个公共(public)类 Pointer，它包含一个指向多态类 Node 的指针。一些派生自 Node 的类将包含新的 Pointer 实例。请注意，多个 Pointer 实例可能指向同一个 Node 实例。

我使用此类构建具有数百万个实例的非常大的图，并且效果很好。当要删除图形时，问题就来了。使用默认的析构函数实现会导致堆栈溢出，因为在根节点的析构函数中，子节点的析构函数被调用，而在子节点的析构函数中，子节点的析构函数被调用等等。

我通过为上面的 NodeDerived 类实现析构函数来解决这个问题，该类通过使用堆栈来避免递归调用。这有效，但仍然很慢，我正在寻找一种方法来加快速度。是否有可能以某种方式避免声明析构函数 virtual 而不会导致内存泄漏？

Answer 1

如果您在销毁期间处理数百万个对象和堆栈溢出，那么您可能想要研究的是将指向所有节点对象的指针存储在某种类型的容器中，该容器不允许重复值并支持迭代，例如std::set 或 std::unordered_set。然后在图节点本身中，只存储指向连接的图节点的指针。在删除图时，不要递归遍历每个图节点的指针以删除节点......相反，只需转到包含指向整个图中节点集的指针的容器，并遍历容器，一个接一个地销毁每个节点。不需要递归，因为您不需要“跟随”每个图形节点的指针集来销毁图形节点连接到的所有节点。您也无需担心 std::shared_ptr 的空间和时间开销。