我正在编写一个四叉树类作为图形库的一部分,我面临一个设计问题。 主要目标是允许库的用户使用自己的节点类型轻松扩展四叉树。每个节点都有一个指向其四个子节点中的第一个的指针。当父节点被分割时,我使用原型(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();
}
}
可以看出,我必须从基类到派生类进行强制转换。或者,我可以制作所有四叉树相关的类模板,但我真的不想这样做。 我也不能使用boost。除此之外,任何带有 RTTI 或动态转换的类似解决方案都会变慢,因为四叉树是性能关键组件,必须尽可能快地运行!
是否有可能在添加一些类型安全性的同时保持 static_cast 的速度? (四叉树仅包含单一类型的节点)。
最佳答案
我知道您说过您不想使用模板,但这种事情正是模板的用途。通过使节点类成为虚拟类,您会在每次构造和销毁上强制增加额外的开销,并通过至少一个指针扩展节点结构的大小,这将降低缓存一致性。
此外,拒绝使用模板将导致您陷入 static_casts
和不安全代码的泥潭。请注意,例如,如果 pChilds
指向 MyNode
数组,并且 MyNode
有任何成员变量,则下标运算符将无形中不起作用适本地。
关于c++ - 通用四叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19091961/