ポインタを使用しない再帰的なデータ構造

Question

CSの私の学士時代に、私は再帰的なデータ構造の使用を何度も経験しました。 C++では、私は常にちょうど私がC.

に単純化した例をどうなるのかのように、次のことができ、私のデータ構造の再帰的にするために、ポインタを使用して終了：

struct Tree{ 
    int data; 
    struct Tree *left, *right; 
}; 

しかし、ポインタを使用する傾向にあります危険な仕事であり、コードのデバッグとテストに多くの時間がかかります。これらの再帰については、C++で再帰的なデータ構造を定義する他の効率的な方法があるかどうかを知りたいと思います。他のプログラミング言語で

は、錆のように、私はそのようなことを見てきました：

struct Node { 
    children: Vec<Node>, 
    node_type: NodeType, 
} 

は、C++でこのような再帰的な構造を定義するより安全かつ快適な方法があります。 1つの可能性は、std :: Vectorを使用することですが、私はメソッドのパフォーマンスを認識していません。

Answer 1

錆の例では、子供のベクトルを使用しています。これも空にすることができます。

C++では、メンバ変数はオブジェクト、ポインタまたは参照（簡略化のため省略されている）にすることができます。

ノードオブジェクトを直接使用することはできません（これは無限ループでしょう）、あなたは、ポインタを使用したくないので、あなたのオプションは次のとおりです。

• は、バイナリツリーのためにかかわらず、（同様のベクターを使用あなたはしかし、（キーがenum CHILD_LEFT、CHILD_RIGHTすることができる）常に2つの要素）、

• はマップを使用するためのコードでそれを制限することができ、

• は、ポインタを使用して再考、または - これは、最も便利なタイプではありませんより良い：スマートポインタ（これは普通のunique_ptrsの良いユースケースのようです）。

Answer 2

ポインターが値ではなく使用されるのは、そのサイズが無限に再帰的になるため、structを決して定義できないからです。などパディングを無視

struct Tree{ 
    int data; 
    struct Tree left, right; 
}; 

は、あなたが

sizeof(Tree) == sizeof(int) + sizeof(Tree) + sizeof(Tree) 
//      ^data   ^left   ^right 

としてTreeの大きさに近づけることができますがTreeがTreeの2人のメンバーを持っているので、あなたはそれを見ることができ、そしてそれらのメンバー自身が2人のTreeメンバーを持っている、そしてそれら2つのTreeのメンバーを持っています....あなたはこれがどこに行くのか見ることができます。