c++ - 我能否在编译时使用模板稳健地构造一棵具有多种已知类型和已知最大深度的树？

Question

我最近突然想到要尝试创建一个“列表”树。也就是说，每个级别都是一个列表的树，所以它不是二叉树。此外，我想尝试使树的每一层都有不同的类型，特别是四种不同的类型——每一层一种。最后，我打算看看是否可以在编译时通过使用三个不同的模板来固定树的高度。

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;
};

在尝试了不同的实现之后，我基本上采用了一些变通方法，其中我有一个表示倒数第二个树级别的类型:

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;
};

通过定义另一个模板，我可以创建一个固定在三个级别、具有三种不同类型的树。请注意，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;
};

问题是，有没有更好更优雅的方法来做到这一点？我在尝试执行原始实现时遇到的障碍是，当您为模板指定类型输入时，您无法将您目前“输入”的类型作为参数传递。因此，由于某种循环依赖性，我的方法无法创建完整的类型。如果您只是将自己限制在 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我在其他地方也看到过类似的实现，但它们都假设一棵树由单一类型组成。对此的自然 react 可能是，“那为什么不使用多态性呢？”。我也看到了这种技术的实际应用，比如在 LLVM 项目中，虽然我对此没有任何问题，但我很想知道我是否可以静态地(在编译时)构造一个颠覆需求的类型对于多态性，因为在我的特殊情况下，我知道所有涉及的类型，而且我知道树的高度是固定的(四)。

我还考虑过结合使用继承和模板来实现更强大的解决方案，但我没有找到解决方案(如果存在的话)。在我看来，我可以手动创建此类类型，包括 5 层或更多层的树。我是不是遇到了模板系统的限制，还是不够聪明？

Answer 1

我想我知道您想要什么以及如何实现它。不过，我认为它不太适合 SO 格式。

首先，创建和使用树的语法:

int main()
{
    // We want a tree with 4 levels.
    // The node type of the 0th level should be `int`,
    // of the 1st level `double` and so on.
    // (0th level = tree root)
    // And we initialize the root node with the `int` 42.
    auto my_tree = make_tree_root < int, double, char, float, int > (42);

    // add children and navigate through the tree
    my_tree.add_child(1.23);
    my_tree.add_child(4.56);
    my_tree.get_child(1).add_child('x');
    my_tree.get_child(1).get_child(0).add_child(1.2f);

    my_tree.print();
}

现在后台一片困惑。请注意，它更像是一个概念验证，它有很多缺陷，没有评论可能是一种祝福。尤其是用于减少代码复制的多重继承带来的问题多于解决的问题。

#include <cstddef>
#include <iostream>    
#include <vector>

template < typename... TP >
struct type_vector
{
private:
    template < std::size_t t_count, typename TT, typename... TTP >
    struct access_elem { using value = typename access_elem < t_count-1, TTP... > :: value; }; 
        template < typename TT, typename... TTP >
        struct access_elem < 0, TT, TTP... > { using value = TT; };

public:
    template < std::size_t t_id >
    using elem = typename access_elem < t_id, TP... > :: value;
};


template < typename, std::size_t, std::size_t >
struct tree_node;

template < typename T_type_vector, std::size_t t_level, std::size_t t_maxLevel >
struct tree_all_base
{
    using node = typename T_type_vector::template elem < t_level >;

protected:
    node m_node;

public:
    explicit tree_all_base(node p) : m_node(p) {}

    void change_node(node);
    node get_node() const { return m_node; }

    void print() const
    {
        std::cout << "node: " << m_node << std::endl;
    }
};

template < typename T_type_vector, std::size_t t_level, std::size_t t_maxLevel >
struct tree_down_base
{
    using child = tree_node < T_type_vector, t_level+1, t_maxLevel >;

private:
    std::vector<child> m_children;

public:
    void add_child(typename child::node p)
    {
        using derived_type = tree_node < T_type_vector, t_level, t_maxLevel >;
        m_children.push_back( child{p, static_cast<derived_type*>(this)} );
    } 
    child const& get_child(std::size_t id) const { return m_children.at(id); }
    child& get_child(std::size_t id) { return m_children.at(id); }
    // further methods like `remove_child` etc

protected:
    void print() const
    {
        std::cout << "children: ";
        for(child const& c : m_children)
        {
            std::cout << c.get_node() << ", ";
        }
        std::cout << std::endl;
        for(child const& c : m_children)
        {
            c.print();
        }
        std::cout << std::endl;
    }
};

template < typename T_type_vector, std::size_t t_level, std::size_t t_maxLevel >
struct tree_up_base
    : public tree_all_base < T_type_vector, t_level, t_maxLevel >
{
    using tree_all_base_ = tree_all_base<T_type_vector,t_level,t_maxLevel>;
    using parent = tree_node < T_type_vector, t_level-1, t_maxLevel >;
    using node = typename tree_all_base_::node;

protected:
    parent* m_parent;

    tree_up_base(node p_node, parent* p)
        : tree_all_base_(p_node), m_parent(p)
    {}
};


template < typename T_type_vector, std::size_t t_level, std::size_t t_maxLevel >
struct tree_node
    : public tree_up_base  <T_type_vector, t_level, t_maxLevel>
    , public tree_down_base<T_type_vector, t_level, t_maxLevel>
{
    using node = typename tree_all_base<T_type_vector,t_level,t_maxLevel>::node;
private:
    /* inherit ctor....*/
    using tree_up_base_ = tree_up_base<T_type_vector,t_level,t_maxLevel>;
    using tree_down_base_ = tree_down_base<T_type_vector,t_level,t_maxLevel>;
    using tree_node_parent = tree_node<T_type_vector,t_level-1,t_maxLevel>;

    friend struct tree_down_base < T_type_vector, t_level-1, t_maxLevel >;
    tree_node(node p, tree_node_parent* pb) : tree_up_base_(p, pb) {}

public:
    void print() const
    {
        tree_up_base_::print();
        tree_down_base_::print();
    }
};
    // tree root specialization
    template < typename T_type_vector, std::size_t t_maxLevel >
    struct tree_node < T_type_vector, 0, t_maxLevel >
        : public tree_all_base <T_type_vector, 0, t_maxLevel>
        , public tree_down_base<T_type_vector, 0, t_maxLevel>
    {
    public:
        /* inherit ctor..... */
        using tree_all_base_ = tree_all_base<T_type_vector,0,t_maxLevel>;
        using tree_down_base_ = tree_down_base<T_type_vector,0,t_maxLevel>;
        using node = typename tree_all_base_ :: node;
        tree_node(node p) : tree_all_base_(p) {}

    public:
        void print() const
        {
            tree_all_base_::print();
            tree_down_base_::print();
        }
    };

    // tree leaf specialization
    template < typename T_type_vector, std::size_t t_maxLevel >
    struct tree_node < T_type_vector, t_maxLevel, t_maxLevel >
        : public tree_up_base <T_type_vector, t_maxLevel, t_maxLevel>
    {
    private:
        /* inherit ctor.... */
        using tree_up_base_ = tree_up_base<T_type_vector,t_maxLevel,t_maxLevel>;
        using node = typename tree_up_base_ :: node;
        using tree_node_parent = tree_node<T_type_vector,t_maxLevel-1,t_maxLevel>;

        friend struct tree_down_base < T_type_vector, t_maxLevel-1, t_maxLevel >;
        tree_node(node p, tree_node_parent* pb) : tree_up_base_(p, pb) {}
    };

template < typename... TP >
tree_node < type_vector<TP...>, 0, sizeof...(TP)-1 >
make_tree_root(typename type_vector<TP...>::template elem<0> node)
{ return {node}; }