Re: Basic design question, about data structures
JSeb wrote:
template <typename T> class TreeNode
{
private:
T* mpData;
const TreeNode<T>* mpLeftChild;
const TreeNode<T>* mpRightChild;
TreeNode(const T& aData)
: mpData(&aData), mpLeftChild(NULL), mpRightChild(NULL)
{ }
// ...
};
There are many problems in storing just a pointer to the data. The
most prominent one is that it's very unsafe, as it requires the user to
be very careful about how he creates and stores the data. For instance,
giving the TreeNode constructor a temporary would cause a malfunction
(which the compiler probably doesn't even detect). Likewise giving it a
local instance of an object which will go out of scope sooner than the
tree will also cause malfunction.
Another problem is the one of responsibility: Who is responsible for
freeing the data, the user or this data container? There would be
advantages and disadvantages in both solutions. For example, if the
responsibility for freeing the data is left to the data container, it's
handier from the point of view of the user, and makes the code slightly
safer (as mistakes are less likely to happen). OTOH, it ties the hands
of the user: He *must* always allocate the data with 'new'. He can't,
for example, have an array of the data and give pointers to the data
elements to the tree (because then the tree would try to delete the
individual elements of the data, which is undefined behavior, afaik).
OTOH, if managing the data is left to the user then it becomes more
error-prone, as the user must be very careful when and how he deletes
the data.
Using smart pointers can alleviate this problem a bit, but OTOH it
would still be impossible to give temporaries or elements of an array to
the data container.
And of course there's the slight problem of memory usage (although
it's not such a big problem with a binary tree, as it's already using
quite a log of ancillary memory for each node): If you force the user to
allocate each object with 'new', that consumes additional RAM, compared
to the case where the object is directly stored in the tree node.
The approach of the STL containers is that they store copies of the
data objects in the data structure elements. It solves most
responsibility problems and in many cases it's much more
memory-efficient (std::vector and std::deque being good examples), and
it allows giving temporaries and local objects to the container. If
copying the objects is very heavy, the responsibility of making it
lighter is left to the user. (He can, for example, make the STL
container store pointers instead of instances if he wants.)