C++: Separate Classes for branch and leaf nodes?

Question

I am making a tree (essentially a prefix tree, but for numbers not strings), which is built from sorted list of tuples of numbers ( (1,1,2), (1,2,5), (2,1,0) etc...), each one associated with a single scalar value (int or double most likely). As it is built only once and then iterated over/searched several times, I plan to use std::vectors to hold the children of each node. To search the tree, I just need to call std::lower_bound to do a binary search on each node's _children vector, which will contain std::pairs of each node and their respective key. However, the bottom nodes must contain a vector with pairs consisting of the last entry in each tuple and their respective values, and thus must be of a different type than the BranchNode. The code looks like this:

class GenNode
{
};

template<typename key_type,typename value_type>
class BranchNode : GenNode
{
    void insert(std::pair< std::vector<key_type> , value_type>);
private:
    std::vector< std::pair<key_type,GenNode*> > _children;
};

template<typename key_type,typename value_type>
class LeafNode : GenNode
{
private:
    std::vector< std::pair<key_type,value_type> > _children;
};

However, this is really ugly, because both classes must inherit from the useless GenNode class so that the children of each BranchNode can be either other BranchNodes or LeafNodes...is there a better way to do this?

Answer 1

If you want to store both types in the same vector, you need the classes to be related (one inherited from other or both inherited from the common ancestor).

Having an empty common ancestor may seem ugly. But you can get more elegant design if you put your search action (as well as other iterations/processings) into the base class as a virtual method, and implement it in BranchNode and LeafNode (the implementations would be different).

The base class should also be templated in this case. What I mean is having a base class like:

template<typename key_type,typename value_type>
class GenNode {
 public:
  virtual value_type search(key_type key) = 0;
};

Answer 2

Yes, you need two different types. In fact, something like this (Leaf OR Node) is called a discriminated union.

There are several ways of implementing it but in C++ having a common base class with two derived classes is probably the most common.

An interesting alternative to having a common base this is using boost::variant with a recursive wrapper. This is particularly interesting because it avoids using pointers (and thus takes care of memory management for you).