c++ - 通用四叉树

Question

我正在编写一个四叉树类作为图形库的一部分，但我遇到了设计问题。一个主要目标是允许库的用户使用他们自己的节点类型轻松扩展四叉树。每个节点都有一个指向其四个子节点中第一个的指针。我使用原型(prototype)模式在拆分时“克隆”父节点(库不知道其真实类型)四次。所以这是 Node 类:

class CNode {
  public:
    virtual CNode* clone();

  protected:
    CNode* pChilds;
}

库的用户现在可以定义自己的节点并添加遍历方法:

class MyNode : public CNode {
  public:
    virtual CNode* clone() {
      return new MyNode;
    }

    void myTraverse() {
      if(pChilds[0] != nullptr)
        static_cast<MyNode*>(pChilds[0])->traverse();
    }
}

可以看出，我必须执行从基类到派生类的转换。或者我可以制作所有与四叉树相关的类模板，但我真的不想那样做。我也不能使用 use boost。除了 boost::any 和类似的 RTTI 或动态转换解决方案都会变慢，因为四叉树是一个性能关键组件，必须尽可能快地运行!

有没有可能在添加一些类型安全的同时保持 static_cast 的速度？ (四叉树将只包含单一类型的节点)。

Answer 1

我知道您说过您不想使用模板，但这类事情正是模板的用途。通过使您的节点类成为虚拟类，您会在每次构造和销毁时强制执行额外的开销，并通过至少一个指针扩展节点结构的大小，这将降低缓存一致性。

此外，拒绝使用模板会导致您陷入 static_casts 和不安全代码的泥潭。请注意，例如，如果 pChilds 指向 MyNode 的数组并且 MyNode 有任何成员变量，那么下标运算符将无形地起作用适本地。