C++ Trees Part 1
by Justin Gottschlich

3. Using the core::tree<>

C++'s STL implementation is genius. The advantages and subtleties of its implementation are so numerous, it is impossible to cover them in a single article, or even in a single book. It was with STL in mind, that the core::tree<> was designed. The core::tree<> container follows as many of the STL design practices as possible, while still ensuring its own tree behavior remains correct.

The core::tree<> implements both const_iterators and iterators for tree iteration. By default, it uses operator<() and operator==() for inserts and finds/removes, but allows predicates to be used to overload that functionality. The core::tree<> implements begin() and end() on its containers as well as post-increment and pre-increment on its iterators. For moving in and out within the tree, methods in() and out() can be called – this makes tree depth iteration very simple. Many other powerful pieces of functionality are implemented as well, such as size(), level() and, of course, full tree copying (just like all STL containers) by use of operator=().

Perhaps the biggest downfall of the std::map<> tree implementation is its lack of simple "complete" tree copying. Calling operator=() on the std::map<> would result in pointer copying, not object copying and implementing a full tree copy would require even more dynamical memory allocation introducing more possibilities for erroneous programmer made memory management mistakes (more memory leaks).

Again, the above problems dissolve when using the core::tree<>. Copying a tree into another tree is as simple as:

   core::tree<Leaf> tree1;
   // ... do work on tree1 here
   // now copy the entire contents of tree1 into tree2
   core::tree<Leaf> tree2 = tree1;

Thus, the core::tree<> container's learning curve is very low for anyone who is already familiar with C++'s STL containers.

The below sample code demonstrates the ease of use of the core::tree<> container. The code in figure 3.1 performs simple tree construction and tree output.

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

void fun()
{
   // the tree containers all sit inside the core namespace
   using namespace core;
   using namespace nTreeData;

   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));
      }
   }

   ////////////////////////////////////////////////////
   // output the leaf tree
   ////////////////////////////////////////////////////
   for (tree<Leaf>::const_iterator iter = leafTree.begin();
        iter != leafTree.end();
        ++iter)
   {
      std::cout << iter.data().value() << std::endl;

      tree<Leaf>::const_iterator inner = iter;
      // tree's iterators are containers themselves - use the
      // same iterator to traverse inwards through the tree
      for (inner = inner.in(); inner != inner.end();
           inner = inner.in())
      {
         for (int tabs = 1; tabs < inner.level(); ++tabs)
            std::cout << "\t";

         std::cout << (*inner).value() << std::endl;
      }
   }
}
Figure 3.1

For clarity, a step-by-step analysis of the core::tree<> code in figure 3.1 is given below.

Construct the tree container:
```
tree<Leaf> leafTree;
```
Populate the tree with data. The outer for loop inserts branches into the root tree. The inner for loop inserts branches into each additional branch inserted. Thus, the outer for loop is a breadth population and the inner for loop is a depth population. Notice that the inner for loop assigns the inserted iterator to itself: iter = iter.insert(). This forces iter to continue stepping inward, becoming the iterator of the branch inserted by the iter.insert() operation.
```
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));
   }
}
```

Iterate through the tree. The outer for loop iterates through the branches of the root tree. The inner for loop iterates inward. Again, notice how inner = inner.in() is performed within the nested for loop. This forces the inner iterator to continue to step into itself until there are no further branches inward.

for (tree<Leaf>::const_iterator iter = leafTree.begin();
     iter != leafTree.end();
     ++iter)
{
   std::cout << iter.data().value() << std::endl;

   tree<Leaf>::const_iterator inner = iter;
   // tree's iterators are containers themselves - use
   // the same iterator to traverse inwards through the tree
   for (inner = inner.in(); inner != inner.end();
        inner = inner.in())
   {
      for (int tabs = 1; tabs < inner.level(); ++tabs)
         std::cout << "\t";

      std::cout << (*inner).value() << std::endl;
   }
}

The output of the leafTree that's built above is as follows:

As you can see from the above output the root of the tree has ten branches. Each of those ten branches contain five inner branches, all nested within each other. Analyzing the output in step 4 can aid in understanding the code in step 3.

Due to the core::tree<> design following some of the STL container paradigms, certain STL algorithms can be followed. For example, the std::for_each algorithm can be used to iterate across any breadth of tree (keep in mind, tree depth iteration requires a bit more work). Figure 3.2 demonstrates a simple core::tree<> implementation using std::for_each.

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

////////////////////////////////////////////////////
void outputLeaf(const Leaf &l)
{
   std::cout << l.value() << std::endl;
}

////////////////////////////////////////////////////
void fun()
{
   core::tree<Leaf> leafTree;

   for (int i = 0; i < nTreeData::kMaxLeaves; ++i)
      leafTree.insert(Leaf(i));
   std::for_each(leafTree.begin(), leafTree.end(), outputLeaf);
}
Figure 3.2

To perform complete tree output iteration (both breadth and depth) in a single function, a minor amount of recursion is generally suggested (although it can be performed iteratively). However, the code is still very straightforward and easy to write:

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

////////////////////////////////////////////////////
void outputLeaf(core::tree<Leaf>::const_iterator &tree)
{
   // a tree iterator can check itself for its end
   for (core::tree<Leaf>::const_iterator i = tree.begin();
        i != tree.end(); ++i)
   {
      for (int tabs = 1; tabs < i.level(); ++tabs)
         std::cout << "\t";
      std::cout << (*i).value() << std::endl;

      outputLeaf(i);
   }
}
   
////////////////////////////////////////////////////
void fun()
{
   // the tree containers all sit inside the core namespace
   using namespace core;
   using namespace nTreeData;

   core::tree<Leaf> leafTree;

   //for (int i = 0; i < nTreeData::kMaxLeaves; ++i)
   //   leafTree.insert(Leaf(i));
   ////////////////////////////////////////////////////
   // 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 a 100 placeholder leaf, then insert a leaf
         // and step into it
         iter.insert(Leaf(100));
         iter = iter.insert(Leaf(depth));
      }
   }

   outputLeaf(static_cast<core::tree<Leaf>::const_iterator >(leafTree));
}
Figure 3.3

Figure 3.3 will properly output a tree with any number of branches within any given branch. Additionally, figure 3.3 demonstrates a fundamental difference between core::tree<> containers and STL containers:

core::trees<> are core::tree<>::iterators.

The last line of code in figure 3.3 shows the static_cast<> operation converting a core::tree<> into a core::tree<>const_iterator. This is a fundamental deviation and necessity for the core::tree<> implementation. This concept alone, is what makes the core::tree<> container possible. More detailed explanation is given about this concept in the next portion of the core::tree<> series.

Conclusion

Contents

	Introduction
	std::map<> versus core::tree<>
	Using the core::tree<>
	Conclusion

	Printable version
	Discuss this article

The Series

Part 1

Part 2