通用四叉樹

我正在編寫一個四叉樹類作爲圖形庫的一部分，我正面臨一個設計問題。主要目標是允許庫的用戶使用他們自己的節點類型輕鬆擴展四叉樹。每個節點都有一個指向其四個孩子中第一個孩子的指針。我使用原型模式在分割時克隆父節點（它的真實類型對庫是未知的）四次。因此，這裏的節點類：通用四叉樹

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

回答

相關問題