c++ - テンプレートを使用して、コンパイル時に複数の既知の型と既知の最大深度を持つツリーを堅牢に構築できますか?

Question

かなり最近、「リスト」のツリーを作成しようと思いつきました。つまり、各レベルがリストであるツリーであるため、バイナリツリーではありません。さらに、ツリーの各レベルを異なるタイプ、具体的には 4 つの異なるタイプ (レベルごとに 1 つずつ) にしたいと考えました。最後に、コンパイル時に 3 つの異なるテンプレートを使用してツリーの高さを修正できるかどうかを確認するつもりでした。

tree_middle、ツリーの中間レベルの場合、

template<typename a, typename b, typename c>
struct tree_middle
{
    tree_middle *m_prev;
    tree_middle *m_next;

    a *m_upper;

    b *m_node;

    c *m_lower;
};

tree_bottom は、ツリーの下部を示します。

template<typename a, typename b>
struct tree_bottom
{
    tree_bottom *m_prev;
    tree_bottom *m_next;

    a *m_upper;

    b *m_node;
};

ツリーのトップは tree_top です。

template<typename a, typename b>
struct tree_top
{
    tree_top *m_prev;
    tree_top *m_next;

    a *m_node;

    b *m_lower;
};

さまざまな実装をいじった後、基本的に、最後から 2 番目のツリーレベルを示す型を持ついくつかの回避策に頼りました。

template<typename a, typename b, typename c>
struct tree_prebottom
{
    tree_prebottom *m_prev;
    tree_prebottom *m_next;

    a *m_upper;

    b *m_node;

    tree_bottom<tree_prebottom, c> *m_lower;
};

さらに別のテンプレートを定義することで、3 つの異なるタイプの 3 つのレベルで固定されたツリーを作成できました。このテンプレートでは、three_tree が tree_top として機能することに注意してください。これは私が望んでいたものに近いです。

template<typename a, typename b, typename c>
struct three_tree
{
    three_tree *m_prev;
    three_tree *m_next;

    a *m_node;

    tree_prebottom<three_tree, b, c> *m_lower;
};

さらに一歩進んで、私が探していたタイプである four_tree を生成できるテンプレートにたどり着きました。しかし、ここでこのばかげた表示が行われていることに注意してください。ここでは、かなり大まかな意味で「一般的な」コードを書いていますが、同意しますか? それについて一般的な唯一のものは、実際には消費された型です。注: この部分は、four_tree にトップレベルへの適切なリンクがないことに気付いたときに編集されました。)

template<typename a, typename b, typename c, typename d>
struct tree_threebottom
{
    tree_threebottom *m_prev;
    tree_threebottom *m_next;

    a *m_upper;

    b *m_node;

    tree_prebottom<tree_threebottom, c, d> *m_lower;
};

template<typename a, typename b, typename c, typename d>
struct four_tree
{
    four_tree *m_prev;
    four_tree *m_next;

    a *m_node;

    tree_threebottom<four_tree, b, c, d> *m_lower;
};

問題は、これを行うためのより適切でエレガントな方法があるかどうかです。元の実装をしようとしたときに遭遇した障害は、テンプレートの型入力を指定しているときに、現在「入っている」型をパラメーターとして渡すことができないということでした。したがって、私のアプローチでは、一種の循環依存性のために完全な型を作成できないという問題がありました。2 レベルのツリーでさえ、tree_top と tree_bottom に限定すると、この問題に悩まされます。

template<typename a, typename b>
struct tree_bottom
{
    tree_bottom *m_prev;
    tree_bottom *m_next;

    a *m_upper;

    b *m_node;
};

template<typename a, typename b>
struct tree_top
{
    tree_top *m_prev;
    tree_top *m_next;

    a *m_node;

    b *m_lower;
};

テンプレートは、実際の型を定義しようとするまでは、それ自体で問題ありません。例えば

typedef tree_top< int, tree_bottom<tree_top<int, tree_bottom< /*see the problem?*/, short> > int_short_tree;

ツリーの実装はかなり単純化されていることに注意してください。ただし、ここで見つけたツリーテンプレートをエミュレートしようとしていました: http://archive.gamedev.net/archive/reference/programming/features/coretree2/index.html他の場所で実装されていますが、それらはすべて単一の型で構成されるツリーを想定しています。これに対する自然な反応は、「ポリモーフィズムを使用しないのはなぜですか?」となるかもしれません。私はLLVMプロジェクトなどでそのテクニックが実際に動作しているのを見てきました.私はそれに何の問題もありませんが、必要性を覆す型を静的に(コンパイル時に)構築できるかどうか知りたいと思っていました.ポリモーフィズムについては、私の特定のケースでは、関係するすべてのタイプを知っていて、ツリーの高さが固定 (4) であることを知っていたからです。

また、テンプレートと組み合わせた継承を使用して、より堅牢なソリューションを実現することも検討しましたが、ソリューションが存在する場合、解決策はわかりませんでした。5 レベル以上の木を含む、この種のタイプを手動で作成できるように思えます。ここでテンプレートシステムの制限に達したのでしょうか、それとも十分に賢くないのでしょうか?

c++ - テンプレートを使用して、コンパイル時に複数の既知の型と既知の最大深度を持つツリーを堅牢に構築できますか?

1 に答える 1

Related

Reference