通用四叉树

我正在编写一个四叉树类作为图形库的一部分，我正面临一个设计问题。主要目标是允许库的用户使用他们自己的节点类型轻松扩展四叉树。每个节点都有一个指向其四个孩子中第一个孩子的指针。我使用原型模式在分割时克隆父节点（它的真实类型对库是未知的）四次。因此，这里的节点类：通用四叉树

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(); 
    } 
}

可以看到我所要做的从铸造基类到派生类。或者，我可以制作所有四叉树相关的类模板，但我真的不想这样做。我也不能使用使用提升。除了boost ::任何和RTTI或动态转换类似的解决方案，由于四叉树是一个性能关键组件，并且必须尽可能快地运行，所以速度会变慢！

在添加某种类型安全性的同时，是否有任何可以保持static_cast的速度？（四叉树只会包含单一类型的节点）。

来源

2013-09-30 user2830627

我标记了你的问题[C++]。如果这是不正确的，随时恢复并添加一个不同的语言标签。 –

并澄清你的问题：如何调用'myTraverse'成员函数？它是否被图书馆称为？如果是这样，图书馆如何知道它，因为它没有在基类中定义？ –

澄清：'myTraverse'从MyNode已知的地方被调用，所以这不是问题 – user2830627

既然你说

四叉树将只包含一个单一类型

的节点，那么你可以使用这个假设来优化你的代码。如在，你可以假设在MyNode::myTraverse()的身体this的孩子都将是MyNode，你可以安全static_cast任何孩子到MyNode s。

但是，如果代码中的错误违反了您的数据结构的不变性，那么您可能会担心会发生什么，因为它可能只保存一种类型的元素。这是条件编译可以派上用场的地方。假设符号DEBUG在调试定义构建：

#ifdef DEBUG 
#define my_cast dynamic_cast 
#else 
#define my_cast static_cast 
#endif 

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

这会给你一个static_cast的速度在你的发布版本和dynamic_cast在调试运行时类型检查版本，在速度不是作为很多问题。如果你违反了你的发布版本中的结构不变性，你也可能会在你的调试版本中这样做，并且你的调试版本可能会崩溃（它实际上是未定义的行为，但大多数平台会崩溃当你解引用一个空指针）与访问冲突异常/段错误。

或者，你可以用dynamic_cast暂时坚持，一旦你准备好释放和/或你做测试这表明使用dynamic_cast代替static_cast导致不可接受的性能命中切换到static_cast。

编辑：由于您正在创建一个库，请确保它是非常对您的用户清楚，clone()必须返回一个具有相同类型的对象与一些示例。这是您无法确定其他程序员不会犯错误的情况之一，您只需要相信他们可以阅读注释或文档。

来源

2013-09-30 11:05:58

这是一个很棒的主意，谢谢。我想我会坚持。 – user2830627

你还没有讨论节点的生命周期，但你可能还需要一个公共的虚拟析构函数...... – Useless

你是对的，我只是忽略了一切不在问题范围内的东西。我已经有了节点生命周期管理的解决方案。 – user2830627

我知道你说过你不想使用模板，但这种事情正好是模板的用途。通过将您的节点类设为虚拟类，可以在每个构建和销毁中强制额外开销，并且至少通过一个指针扩展节点结构的大小，这将降低缓存一致性。

此外，拒绝使用模板将导致您陷入了和不安全的代码的泥潭。请注意，例如，如果pChilds指向MyNode的数组，并且MyNode有任何成员变量，则下标操作符将无法正常工作。

来源

2013-09-30 14:32:34 Sneftel

嗯，也许你是对的。我的自定义节点类声明会看起来像这样？ “class MyNode：public CNode {...}” – user2830627

是的，最有可能的。容器节点是CRTP的主要用途之一。 – Sneftel

回答

相关问题