1

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

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我也看到了类似的其他地方的实现，但它们都假定由单一类型组成的树。对此的自然反应可能是“为什么不使用多态性？”。我也看到了这种技术的实际应用，例如在 LLVM 项目中，虽然我对此没有任何问题，但我很想知道我是否可以静态（在编译时）构造一个颠覆需要的类型对于多态性，因为在我的特定情况下，我知道所涉及的所有类型，并且我知道树有一个固定的高度（四）。

我还考虑过将继承与模板结合使用来实现更健壮的解决方案，但该解决方案让我无法理解，如果它存在的话。在我看来，我可以手动创建这种类型，包括 5 级或更多级别的树。我在这里遇到了模板系统的限制，还是不够聪明？

4

1 回答 1

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}; }
于 2013-04-13T20:58:56.633 回答