如何在C++中模擬遞歸類型定義？

昨天我問了以下question，轉載這裏爲了方便;如何在C++中模擬遞歸類型定義？

「對於我的項目，我真正想要做的就是這一點（它簡化到最低限度）之一;

struct Move 
{ 
    int src; 
    int dst; 
}; 

struct MoveTree 
{ 
    Move move; 
    std::vector<MoveTree> variation; 
};

我必須承認，我認爲這是不可能做到這個直接的，我認爲MoveTree中的MoveTree矢量將是過時的，但我仍然嘗試了它，它運行得非常漂亮，我使用的是Microsoft Visual Studio 2010 Express。我有什麼可擔心的嗎？「

基本上來自社區的答案是否定的，我無法做到這一點，標準禁止它，所以它的工作原理意味着我只是幸運。

所以我的新問題是。我如何在合法的C++中實現我想要的簡單功能，而不會增加一堆令人討厭的複雜性和痛苦？

來源

2011-06-29 Bill Forster

你也可以使用[recursive_wrapper]（http://www.boost.org/doc/libs/1_46_0/doc/html/boost/recursive_wrapper.html），如果和'vector'一起使用，效率很低，由於高堆流量。 –

你爲什麼要刪除@Johannes的答案？這是一種不同於@Cat Plus Plus的方法，它具有一些優點和缺點：優點是您可以提供對矢量的引用並保持用戶代碼基本不變，缺點是對矢量增長的處理成本更高。 –

@David，因爲我覺得recursive_wrapper在這裏不太好用.- –

您將需要使用指針和動態分配。你應該使用智能指針，以確保你不會泄漏任何東西。 boost::shared_ptr允許的類型是不完整的，因此，這是合法的：

std::vector< boost::shared_ptr<MoveTree> > variation;

（我不知道0X std::shared_ptr TBH，但它應該是相同的）。

來源

2011-06-29 22:25:06

我認爲這仍然是未定義的，無論是理性還是非理性：請參閱 - http://stackoverflow.com/questions/6517231/are-c-遞歸類型定義可能在特定的我可以放一個vectort –

@ MerlynMorgan-Graham：使用指針絕對不是未定義的。 –

但它是一個指針？看到另一個問題的答案，並告訴我你可以使用一個不完整的類型作爲模板參數（限定符只能在內部用作指針）。標準中的措辭似乎相當絕對。或者，如果這是格式良好的，那麼我會認爲'std :: vector '也是格式良好的。 –

我沒有C++手頭標準的副本，所以我不能檢查標準的，但這裏的問題：

類不能包含自身的具體情況，甚至過渡地 - 例如，struct foo { foo x; }是非法的，原因很明顯。更一般地說，除了成員函數的主體外，你不能在任何成員中引用結構的大小。
類可以包含指向自己 - struct foo { foo *x; }是完全沒有

所以，問題是，並不限定std::vector（比成員函數其他）的任何成員，其直接或間接地依賴於sizeof(MoveTree)？

顯然，std::vector不能有一個靜態成員，它本身是MoveTree，因爲這意味着一個空的向量將調用MoveTree構造函數。然而，人們可以設想一個std :: vector，其中一個元素向量的對齊優化爲char inlineStorage[sizeof(MoveTree)]。撇開這是否會提高性能，手頭上的問題是如果標準允許實施採取這種方法。

這就是說，由於不同的原因，它仍然是一個糟糕的主意：因爲矢量在調整存儲大小時必須複製它們的元素，所以在vector中使用昂貴的拷貝構造函數是一個壞主意。這裏我們有一個類，它的拷貝構造函數必須遞歸地重新創建整個樹。這將是更好地使用智能指針類間接引用的子節點來避免這種開銷：

std::vector<boost::shared_ptr<MoveTree> > variation; 
// in C++0x: 
std::vector<std::shared_ptr<MoveTree> > variation; 
// in C++0x you can also use for lower overhead: 
std::vector<std::unique_ptr<MoveTree> > variation; 
// you must then use this pattern to push: 

variation.push_back(std::move(std::unique_ptr<MoveTree>(new MoveTree())));

來源

2011-06-29 22:26:07 bdonlan

嗯，我一直在使用我的代碼幾個月沒有問題。我並不太擔心表演。而這種「推動的模式」正是我希望避免的那種令人討厭的複雜性。仍然+1提供一些想法謝謝。 –

更具體地說，問題是標準禁止用不完整類型實例化任何標準容器。 –

您可以使用Boost Pointer Container Library。它類似於使用std :: vector，但容器擁有指針，所以它會銷燬對象。

你可以聲明它：

#include <boost/ptr_container/ptr_vector.hpp> 
struct MoveTree{ 
    Move move; 
    boost::ptr_vector<MoveTree> variation; 
};

現在，如果要添加新的元素，你可以使用：

variation.push_back(new MoveTree());

現在，容器擁有指針，你通過得到它參考，例如：

variation[i].move.src = ...

當容器被銷燬時，對象被銷燬。

來源

2011-06-29 22:37:46

我認爲這仍然是未定義的，無論是否合理，或者不是：請參閱 - http://stackoverflow.com/questions/6517231/are-c-recursive-type-definitions-possible-in-particular-can-i-put -a-vectort –

如果您可以使用完整的類型MoveTree在模板參數任何模板，然後使用其他答案的解決方案之一（如貓加上加的），或者簡單地使用你原來的解決方案，加上有些沉重評論，稍後再做你的懺悔。

如果你不能使用它作爲任何模板參數，但它仍然不完整，你可以使用pimpl idiom來解決這個問題。

通過實現類定義時，MoveTree類將是完整的：

struct Move 
{ 
    int src; 
    int dst; 
}; 

struct MoveTreeImpl; 

struct MoveTree 
{ 
    Move move; 

    // Todo: Implement RAII here for the impl 
    // Todo: Provide impl accessor functions here 

private: 
    MoveTreeImpl* impl; 
}; 

struct MoveTreeImpl 
{ 
    std::vector<MoveTree> variation; 
};

有毛部位來此解決方案：

既然你想避免任何直接實例不完整類型的模板，您必須手動實現RAII。您將不會從std::scoped_ptr<MoveTreeImpl>獲得幫助，因爲MoveTreeImpl也不完整。

你的存取函數有什麼特徵？你能從一個存取器返回一個std::vector<MoveTree>&嗎？我不確定這一點 - 我們試圖避免直接使用MoveTree的模板。這可能是不同的，因爲它不是一個數據成員，但我不知道:)

編輯：

讀多一點，並獲得來自其他用戶的響應，似乎這在很大程度上廢話是不必要的。只有標準容器有限制。你可以使用std:scoped_ptr<MoveTreeImpl>來實現pimpl，並且我認爲從訪問函數返回std::vector<MoveTree>&，兩者都沒有問題。

來源

2011-07-01 05:37:03

使用指針（或智能指針）指向Vector中的類型，這將是可移植的。這是因爲指向一個類型的指針是完整的，只是它聲明瞭你不需要定義。

struct Move 
    { 
     int src; 
     int dst; 
    }; 

struct MoveTree; 

struct MoveTree 
    { 
     Move move; 
     std::vector<MoveTree*> variation; 
    };

如果您需要管理的類型，然後使用智能指針，可以爲您處理刪除。

原始答覆to this question。

來源

2011-07-04 08:32:54

如何在C++中模擬遞歸類型定義？

回答

相關問題