2011-10-15 57 views
1

難道是C++一個壞主意,做這樣的事情:在C++中有一個類型爲容器的字段是一個壞主意?

struct Node 
{ 
    string name; 
    vector<Node> children; 
}; 

我這麼問是因爲它看起來對我來說,調整children因任何原因有可能導致指數複製級聯。但另一方面,vector<Node*>有其自身的問題,並且諸如vector<shared_ptr<Node>>之類的內容在安全的情況下,具有較差的內存局部性(由於過多的間接指向),當您嘗試例如內存時,這會開始傷害。記憶中建立一棵巨大的樹。

因此,一般來說,在C++(03)中使用自己的類型的容器是不是一個好主意?是否有其他原因避免(或偏好)這種習慣用法,而不是使用指針容器?

+0

@Downvoter:小心點評? – Mehrdad

回答

2

在C++中有一個字段類型的容器是一個壞主意嗎?

作爲一般規則並不差。它真的歸結於上下文。

在這種情況下,與非平凡調整大小操作和級聯(假設這將是一個問題)相比,共享指針的間接值不應該是顯着的。

如果您可以在填充矢量或複製瑣碎之前保留適當的大小,那麼這裏沒有什麼可擔心的。

如果它真的很大,你可以建立一個外部存儲節點,它處理(並可能共享)節點。然後你的大小調整將是微不足道的,因爲你的children都將是指針。

根據節點的尺寸,這樣的:

struct Node 
{ 
    string name; 
    shared_pointer<vector<Node> > children; 
}; 

可以比共享節點更好。這實際上取決於大小,深度,調整的頻率。一個容器並不壞,但是你必須知道你的程序將如何執行以選擇最佳策略(即使在你知道最快的情況下,分析也可以在這裏起作用)。

如果你知道你有很多物品和大量的尺寸要做,那麼一個快速的外部商店將是一個不錯的選擇;賈爾夫的回答爲此提出了一個很好的策略。

如果您將有很多突變以及指向子列表元素的指針,您也可以在後備存儲上使用節點vectorlist s。

對這些更復雜的實現的支持也需要比您當前的設計更多的時間,但是如果您需要執行大量突變,則它們值得嘗試。簡單的實施和維護將成爲您原創設計的一項獎勵。

如果你的圖真的不會變得很大,另一種方法是使用自定義分配器,它可以引用節點的後備存儲,或者比默認分配器收縮的次數更少。

+1

+1感謝您的出色分析,這很有幫助! :) – Mehrdad

+0

@Mehrdad不客氣:) – justin

0

不會讓children指向一個節點向量幫助複製級聯?

2

取決於幾個因素:

  • 做你的編譯器支持移動語義(如果是的話,你有沒有加入移動構造函數/移動賦值操作符的Node類)
  • 有多大可能會調整向量?
  • 你的數據結構會變得多深?如果其中一個節點的矢量調整大小,那麼需要複製/移動多少節點的節點?

你說得對,它可能可能有這種效果,但只有當你的數據結構是深又寬,足爲級聯實際上是顯着的。

將移動語義添加到您的類將完全解決問題,但也可以修改數據結構。一種選擇可能是不將矢量存儲在節點內部。也許保留一個在所有節點之間共享的單個大向量,並讓每個節點存儲兩個指向屬於它的元素範圍的迭代器。

0

如果vectorstd::vector,那麼這個代碼有未定義的行爲[res.on.functions]狀態(與在C++ 03類似的措詞和C++ 11):

...特別地,該效果是在以下情況下未定義:...如果在實例化模板組件時使用了不完整類型作爲模板參數,除非該組件特別允許。

如果您想這樣做,請使用明確允許遞歸實例化的實現vector,例如boost::container::vector

相關問題