Issue while designing B+Tree template class in C++

Question

Hi,

I'm trying to write a generic C++ implementation of B+Tree. My problem comes from the fact that there are two kinds of nodes in a B+Tree; the internal nodes, which contain keys and pointers to child nodes, and leaf nodes, which contain keys and values, and pointers in an internal node can either point to other internal nodes, or leaf nodes. I can't figure how to model such a relationship with templates (I don't want to use casts or virtual classes).

Hope there is a solution to my problem or a better way to implement B+Tree in C++.

Answer 1

The simplest way:

bool mIsInternalPointer;
union {
  InternalNode<T>* mInternalNode;
  LeafNode<T>* mLeafNode;
};

This can be somewhat simplified by using boost::variant :)