持有泛型类型的实例 - C++

问题描述：

我有一个tree_node类和一个tree类。持有泛型类型的实例 - C++

template<typename T> 
class tree_node 
{ 
public: 
    tree_node(const std::string& key_, const T& value_) 
     : key(key_), value(value_) 
    { 
    } 
private: 
    T value; 
    std::string key; 
}; 

template<typename T> 
class tree 
{ 
public: 
    tree() : root(new tree_node<T>("", ???)) { } 
private: 
    tree_node<T>* root; 
};

tree_node创建时预计的T一个实例。我如何在???的地方通过它？我可以说T()，但它只有在T有一个无参数的构造函数时才起作用。 tree_node我无法使用无参数的构造函数，因为如果T没有无参数的构造函数，它将不会编译。

我正在寻找一种方法来设计tree_node，它可以正确包含所有类型，包括指针类型。

编辑

尝试各种方法后，我发现boost::optional在这种情况下有帮助。我可以将T value分成boost::optional<T> value。这将解决空构造问题。所以我可以有tree_node的另一个构造函数超载，它只需要一个key。这可以由根节点使用。这是正确的方法吗？

谢谢..

默认构造函数将root设置为NULL而不是？ – UncleBens 2010-02-16 17:20:09

根本不？你有没有必要在需要时创建根？ – falstro 2010-02-16 17:20:16

@UncleBens：根应该始终可用，以便我可以追加子元素。问题是，root并不真正拥有任何价值。 @roe：即使我懒洋洋地创作，我会传递什么样的价值？ – 2010-02-16 17:23:46

答

初始根值应该为零。如果你推新节点，你显然知道价值。

template<typename T> 
class tree 
{ 
public: 
    tree() : root(0) { } 
    void push (const std::string& key, const T & t) { 
     if (root == 0) { 
     root = new tree_node<T>(key, t); 
     } else { 
     // Make complex tree 
     } 
    } 
private: 
    tree_node<T>* root; 
};

添加

如果使用后缀树，你应该做两种类型的顶点：

enum NodeType { EMPTY_NODE, VALUE_NODE }; 

class base_tree_node 
{ 
public: 
    base_tree_node() :parent(0), left(0), right(0) {} 

    virtual NodeType gettype() = 0; 

protected: 
    base_tree_node* parent; 
    base_tree_node* left; 
    base_tree_node* right; 
}; 

class empty_tree_node : base_tree_node 
{ 
    virtual NodeType gettype() { return EMPTY_NODE; } 
} 

template<typename T> 
class tree_node : base_tree_node 
{ 
public: 
    tree_node(const std::string& key_, const T& value_) 
     : key(key_), value(value_) 
    { 
    } 

    virtual NodeType gettype() { return VALUE_NODE; } 

private: 
    T value; 
    std::string key; 
};

谢谢。但在我的情况下，root应该只保留空值。所有添加的项目都将追加到此根目录或附加到此根目录的其他子项目。 – 2010-02-16 17:25:49

@Appu：为什么？通常，所有的树节点都应该包含实际的数据，并且根指针（不是根节点）应该指向层次结构的顶部。假设一棵二叉树，如果根节点是空的，那么内容将被添加到哪里？对？这没有任何意义。 – 2010-02-16 17:39:58

那么，我正在做的是'trie'（后缀树）。在那里，根将是空的。 – 2010-02-16 17:48:23

答

tree(const T & t) : root(new tree_node<T>("", t)) { }

那么，所以来电者必须做'虚拟假人（..）;树 t（dummy）'？ – 2010-02-16 17:30:40

@Appu如果限制树始终至少有一个带有值的节点，那么将该值传递给树的构造函数是有道理的。 – 2010-02-16 17:44:44

@Appu No - tree t（foo（..））; – 2010-02-16 18:08:45

答

我曾经做过一个链表（只是为了好玩），这需要一个不意味着保存任何数据的哨兵节点，我有以下结构：

struct BaseNode 
{ 
    BaseNode* next; 
    BaseNode(BaseNode* next): next(next) {} 
}; 

template <class T> 
struct Node: public BaseNode 
{ 
    T data; 
    Node(const T& data, BaseNode* next): BaseNode(next), data(data) {} 
}; 

template <class T> 
struct List 
{ 
    BaseNode* head; 
    List(): head(new BaseNode(0)) {} 
    void add(const T& value) 
    { 
     Node<T>* new_node = new Node<T>(value, head->next); 
     head->next = new_node; 
    } 
    T& get_first() 
    { 
     assert(head->next); 
     return static_cast<Node<T>*>(head->next)->data; 
    } 
    //... 
};

该课程本身必须确保它获得必要的施放权，并且不会试图将头或根本身投射到Node<T>。

答

树节点应该有（或是）一个子节点的集合。树应该具有（或者是）根节点的集合。这两个集合应该是相同的类型。很简单：

template <class T> 
class NodeCollection 
{ 
    std::vector<Node<T> *> nodes; 

public: 
    // any operations on collection of nodes 
    // copy ctor and destructor a must! 
}; 

template <class T> 
class Node : public NodeCollection<T> 
{ 
    T value; 

public: 
    // ctor 
    // access to value 
}; 

template <class T> 
class Tree : public NodeCollection<T> 
{ 
public: 
    // ctor 
};

这样的Tree和Node共享的定义实际上是在NodeCollection，所以Tree不需要随身携带一个虚拟值。

持有泛型类型的实例 - C++

相关推荐