title: C++: Separate Classes for branch and leaf nodes?
body: <p>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: </p>
  
  <pre><code>class GenNode
  {
  };
  
  template&lt;typename key_type,typename value_type&gt;
  class BranchNode : GenNode
  {
      void insert(std::pair&lt; std::vector&lt;key_type&gt; , value_type&gt;);
  private:
      std::vector&lt; std::pair&lt;key_type,GenNode*&gt; &gt; _children;
  };
  
  template&lt;typename key_type,typename value_type&gt;
  class LeafNode : GenNode
  {
  private:
      std::vector&lt; std::pair&lt;key_type,value_type&gt; &gt; _children;
  };
  </code></pre>
  
  <p>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?</p>