c++ - 替代模板变量？

Question

我正在构建二叉搜索树。作为普通人，我希望所有类型都能够充当树中节点的键。

所以我想到了以下内容:

class foo
{
private:
    template<class T>
    struct node
    {
        T key;
        node* left;
        node* right;
    };

    node<>* _root;  //point of interest
public:
    //.....
    template<class T>
    void insert(const T& key);
};

当我将节点插入树中时，我可以根据key的类型创建节点对象，但我不知道如何声明_root以这种方式(当在空树上使用 insert 时，我可以轻松地为 _root 选择类型)。

我相信 C++14 的模板变量可以帮到我，但遗憾的是 MSVC 的编译器尚未实现该功能。

问题如何以最通用的方式声明_root？过去人们是怎么做到的？

Answer 1

只存储节点不是问题:

class foo
{
    struct node
    {
        virtual ~node() {}
        node * left;
        node * right;
    }

    template<typename T>
    struct key_node: node
    {
        T key;
        ~value_node() {}
    }

    node *root;
};

当您想访问节点内的键值时就会出现问题(因为您需要以某种方式存储类型信息)。

或者，您可以使用 boost::any 代替 T 模板:

class foo
{
    struct node
    {
        boost::any key;
        node * left;
        node * right;
    }

    node *root;
};

...并使用 boost::any 的接口(interface)来获取它们键的值(但即使在这里，您也可能需要有关存储在 any 中的类型的信息，然后才能以通用方式访问它)。