我正在编写一个四叉树类作为图形库的一部分,并且面临设计问题。
一个主要目标是允许库的用户使用自己的节点类型轻松扩展四叉树。每个节点都有一个指向其四个子节点中第一个子节点的指针。拆分时,我使用原型(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。除此之外,使用RTTI或动态转换的boost::any和类似解决方案都将变慢,因为四叉树是性能至关重要的组件,必须尽快运行!

在增加某些类型安全性的同时,是否可以维持static_cast的速度? (四叉树将仅包含单一类型的节点)。

最佳答案

我知道您说过您不想使用模板,但是这种事情正是模板的用途。通过使节点类成为虚拟类,您将在每次构造和销毁上增加额外的开销,并通过至少一个指针扩展节点结构的大小,这将减少缓存的一致性。

另外,拒绝使用模板会使您陷入static_casts和不安全代码的困惑之中。请注意,例如,如果pChilds指向MyNode数组,并且MyNode具有任何成员变量,则下标运算符将无形地无法正常工作。

关于c++ - 通用四叉树,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/19091961/

10-13 06:59