C++で再帰型定義をエミュレートするにはどうすればよいですか？

Question

昨日私は以下のように頼んだquestion、便宜のためにここに再現しました。

「私は本当にこの（最低限にそれを簡素化）してやりたい私のプロジェクトの1つを、

struct Move 
{ 
    int src; 
    int dst; 
}; 

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

私はそれを行うことは可能ではないであろうことを想定していることを認めなければなりませんこれは直接MoveTree内のMoveTreeのベクトルが動いていると思っていましたが、とにかく試してみましたが、きれいに動作していますMicrosoft Visual Studio 2010 Expressを使用しています

これは移植可能ですか？私は心配することがありますか？ "

コミュニティからの回答は、いいえ、できませんでした。標準では禁止されているため、実際には機能しているということは、ただ運が良かったことを意味します。

私の新しい質問はです。どのようにして、法的なC++で必要とするシンプルな機能を実装することができますか？

Answer 1

ポインタと動的割り当てを使用する必要があります。スマートポインタを使用して、何も漏れないようにする必要があります。 boost::shared_ptrはタイプが不完全であることができますので、これは合法である：

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

（私はTBHについて0xのstd::shared_ptrを知らないが、それは同じである必要があります）。

Answer 2

私は上の手のC++標準のコピーを持っていないので、私は標準を確認することはできませんが、ここで問題です：

• クラスでも推移、自身の具体的なインスタンスを含めることはできません - 明らかな理由から、例えばstruct foo { foo x; }は不正です。より一般的には、メンバ関数の本体を除いて、メンバのいずれかの構造体のサイズを参照することはできません。
• クラスは、自分自身へのポインタを含めることができます - struct foo { foo *x; }を

完全に罰金そこで質問がされている、std::vectorは、直接的または間接的にsizeof(MoveTree)に依存（メンバ関数以外の）メンバーを定義していますか？

明らかに、std::vectorは、MoveTreeという静的メンバーを持つことはできません。これは、空のベクターがMoveTreeコンストラクタを呼び出すことを意味するためです。しかしながら、1要素ベクトルのために最適化されたchar inlineStorage[sizeof(MoveTree)]を有するstd :: 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()))); 

Answer 3

あなたは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()); 

は今、コンテナは、ポインタを所有している、あなたはでそれを得ます例えば、

このオブジェクトは、コンテナが破棄されたときに破棄されます。

Answer 4

あなたは、いくつかの重い、コメントを追加し、その後、他の回答（例えば猫プラスプラスの）内のソリューションのいずれかを使用、または単にあなたの元の溶液を使用し、でテンプレートパラメータとして任意のテンプレートを不完全な型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を手動で実装する必要があります。 MoveTreeImplも不完全であるため、std::scoped_ptr<MoveTreeImpl>からのヘルプは表示されません。

アクセサー機能にはどのような署名がありますか？アクセサーからstd::vector<MoveTree>&を返すことはできますか？私はこれについてはわかりません - MoveTreeを直接使用するテンプレートを避けようとしています。それはデータメンバではありませんので、これは、異なる場合がありますが、私はよく分からない:)

編集：

もう少し読んで、他のユーザーからの応答を取得し、それはこのくらいですナンセンスは不要です。制限があるのは標準コンテナのみです。あなたはstd:scoped_ptr<MoveTreeImpl>でpimplを実装することができます。アクセサー関数からはstd::vector<MoveTree>&が返されると思いますが、どちらも問題ありません。

Answer 5

ベクターの型にポインタ（またはスマートポインタ）を使用すると、これは移植可能になります。これは、定義を必要としない宣言だけで、型へのポインタが完全であるためです。

タイプを管理する必要がある場合は、削除を処理できるスマートポインタを使用します。

オリジナル回答to this question。