2. std::map<> versus core::tree<>

Many experienced C++ programmers use C++'s standard template library's (STL) map<> and multimap<> to generate trees. Yet, these containers make poor substitutes for true tree designs for a variety of reasons. This section will take a closer look at the pitfalls of using C++'s std::map<> and std::multimap<> for tree containment.

2.1 Basic std::map<> tree implementation

Before beginning the implementation of a tree using std::map<>, a framework must be defined in which the tree will work. For the purposes of this article the following namespace will be used to control the number of leaves generated at the root level and maximum branch depth of the trees constructed:

namespace nTreeData
{
   const int kMaxLeaves = 10;
   const int kMaxDepth = 5;
}
Figure 2.1

Additionally, the following class defined (in figure 2.2) will be used as the leaf node, which will be inserted at every branch of the tree.

class Leaf
{
public:

   Leaf() : value_(0) {}
   explicit Leaf(const int &value) : value_(value) {}

   const int &value() const { return value_; }

   bool operator==(const Leaf &rhs) const
      { return this->value() == rhs.value(); }
   bool operator<(const Leaf &rhs) const
      { return this->value() < rhs.value(); }

private:
   int value_;
};
Figure 2.2

Combining the definitions provided in figure 2.1 and figure 2.2, an example of an std::map<> tree can be constructed:

#include <map>
#include <iostream>

typedef std::map<Leaf, int> LeafMapConcrete;
typedef std::map<Leaf, int>* LeafMapPointer;
typedef std::map<Leaf, LeafMapPointer > LeafMap;

void fun()
{
   using namespace nTreeData;
   LeafMap leafTree;

   ////////////////////////////////////////////////////
   // create a simple leaf tree
   ////////////////////////////////////////////////////
   for (int i = 0; i < kMaxLeaves; ++i)
   {
      // insert a starter leaf
      LeafMapPointer p = new LeafMapConcrete;
      leafTree.insert(LeafMap::value_type(Leaf(i), p));
      LeafMap::iterator iter = leafTree.find(Leaf(i));

      // continue inserting children inside of children
      for (int depth = 0; depth < kMaxDepth; ++depth)
      {
         LeafMapPointer inner = new LeafMapConcrete;
         LeafMap* outer = (LeafMap*)(iter->second);
         outer->insert(LeafMap::value_type(Leaf(depth), inner));

         iter = outer->find(Leaf(depth));
      }
   }

   ////////////////////////////////////////////////////
   // deallocate the leaf tree
   ////////////////////////////////////////////////////
   for (LeafMap::iterator destroy = leafTree.begin();
        destroy != leafTree.end();
        ++destroy)
   {
      LeafMap::const_iterator inner = destroy;
      LeafMap* iterMap = (LeafMap*)(destroy->second);
      LeafMap* lastMap;

      for (inner = iterMap->begin(); inner != iterMap->end();
           inner = iterMap->begin())
      {
         lastMap = iterMap;
         // move the iterMap forward
         iterMap = (LeafMap*)inner->second;
         delete lastMap;
      }
   }   
}
Figure 2.3

Figure 2.3 demonstrates how to use a std::map<> to implement a tree in C++. The above implementation is a common method for overcoming STL's lack of native tree container support. Unfortunately, it has many problems:

1. Dynamic memory allocation and deallocation must be implemented for the tree by the programmer. Additional code must be added in figure 2.3 to do full depth and breadth tree iteration to allocate and deallocate each branch. Currently, figure 2.3 only provides simple deallocation (since we're assuming knowledge of the tree layout). Correct and complete memory deallocation requires more work. Additionally, it is very common for programmers to make mistakes when implementing complex memory management, which leads to memory leaks. One of the advantages of using STL containers is that they perform memory management internally [Josuttis1]. However, when using STL maps to construct trees in this manner, the memory management advantage of STL is lost.
2. Many C-style / reinterpret_cast<> type-casts are required. Type-casting is dangerous (especially, C-style casting and reinterpret_cast<>). Accidental incorrect type-casting can cause unexpected run time behavior. As Stroustrup reminds us, we should avoid explicit casting [Stroustrup1].
3. The code is complex. Simply doing the construction and destruction of the tree is rather hard to understand. If the code to generate and populate a simple tree is this difficult to write, how difficult will it be to write more complex trees? What about the difficulty of maintaining this tree code (especially by someone who didn't originally write the code)? Sutter and Alexandrescu point out in their "C++ Coding Standards", simple should always be preferred over complex [Sutter1]. Figure 2.3's tree implementation clearly violates this rule.
4. There is a great deal of wasted space. For each branch of the tree generated, an extra integer is generated serving no purpose except as a filler. Unfortunately, there is no way to remove this extra filler. This is another clue that the design is flawed - unnecessary pieces are present in the implementation that do not aid the design.

Consider now the same tree being generated using the core::tree<> container:

#include "tree.h"
#include <iostream>

void fun()
{
   using namespace nTreeData;
   using namespace core;

   core::tree<Leaf> leafTree;

   ////////////////////////////////////////////////////
   // create a simple leaf tree
   ////////////////////////////////////////////////////
   for (int i = 0; i < kMaxLeaves; ++i)
   {
      // insert a starter leaf
      tree<Leaf>::iterator iter = leafTree.insert(Leaf(i));

      // continue inserting children each time
      for (int depth = 0; depth < kMaxDepth; ++depth)
      {
         // insert and step into the newly created branch 
         iter = iter.insert(Leaf(depth));
      }
   }
}
Figure 2.4

The code within figure 2.4 implements the same tree as the std::map<> solution within figure 2.3. However, the tree constructed using the core::tree<> container (figure 2.4) is less complex than the tree constructed using std::map<>. Furthermore, the core::tree<> implementation requires less code than the std::map<> implementation. Lastly, the core::tree<> implementation has none of the pitfalls the std::map<> implementation has:

1. No dynamic memory allocation or deallocation is needed, it is all handled internally.
2. Not even a single type-cast is used.
3. The code is very straightforward.
4. There is no wasted space.

Reviewing the above implementations of trees, it is clear the tree implementation using std::map<> is error-prone, complex and run time unsafe. However, the tree implementation using the core::tree<> is simple and elegant, and solves the tree design problem with no additional programmatic overhead. The core::tree<> code is also easier to understand than the std::map<> code which leads to easier code maintenance.

Using the core::tree<>