1

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

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

  protected:
    CNode* pChilds;
}

库的用户现在可以定义自己的节点并添加 traverse 方法：

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 的速度？（四叉树将只包含单一类型的节点）。

4

2 回答 2

2

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

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

于 2013-09-30T14:32:34.117 回答
1

既然你说

四叉树将只包含单一类型的节点

那么您可以使用该假设来优化您的代码。如中，您可以假设s 的孩子都将成为您的身体MyNode::myTraverse()，并且您可以安全地任何孩子到s。thisMyNodestatic_castMyNode

但是，您可能会担心如果代码中的错误违反了数据结构的不变量，即它可能只包含一种类型的元素，会发生什么情况。这就是条件编译可以派上用场的地方。假设符号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或者，您可以暂时坚持使用，static_cast一旦您准备好发布和/或您已经完成测试，表明使用dynamic_cast而不是static_cast导致不可接受的性能损失时切换到。

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

于 2013-09-30T11:05:58.533 回答