Holding a generic type's instance - C++

Question

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<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..

Answer 1

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

Answer 2

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

Answer 3

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>.

Answer 4

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.