Holding a generic type's instance - C++

I have a tree_node class and a tree class.

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开发者_Python百科<T>* root;
};

tree_node expects an instance of T when creating. How can I pass it in the ??? place? I can say T(), but it will work only if T has a parameterless constructor. I can't have a parameterless constructor for tree_node as it won't compile if T doesn't have a parameterless constructor.

I am looking for a way to design tree_node which can hold all types correctly including pointer types.

Edit

After trying various methods, I found that boost::optional is helpful in this case. I can make the T value into boost::optional<T> value. This will solve the empty constructor issue. So I can have another constructor overload of tree_node which just takes a key. This can be used by the root node. Is this the correct way to go?

Thanks..

Init root value should be zero. If you push new node you obviously know value.

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

Add

If you use suffix tree you should make two types of vertices:

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

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

I have once done a linked list (just for fun) which needed a sentinel node not meant to hold any data, and I had the following structure:

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

The class itself must make sure it gets necessary casts right and doesn't try to cast head or root itself to Node<T>.

A tree node should have (or be) a collection of child nodes. A tree should have (or be) a collection of root nodes. Both those collections should be the same type. Very simply:

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

This way the shared definition of Tree and Node is actually in NodeCollection, and so Tree doesn't need to carry a dummy value.