Introducing Templates, Iterators, and Temporary Classes

Environment: Developed in (but not restricted to) VC6.

This article is an introduction to templates, iterators, and temporary classes illustrated by an implementation of a red-black tree.

Table of Contents

Background
The Self-Balancing Tree
Templates
Iterators
Temporary Classes (tree["Foo"]=3 vs. int i = tree["Foo"] )
But We Have This Already!
About the Source Code
Downloads

Background

The Balanced Binary Tree article gives a brief introduction to binary trees (and to recursion). There, my aim was to describe the binary tree concept with as few technicalities as possible. For instance, the balancing technique described is easy to understand (I think), though not very practical in RealLifeTM.

This time, I have a different approach, more focused on a tree's implementation and coding details. This article is not a description of how red-black balancing works, but uses a red-black implementation to illustrate some more or less interesting coding concepts.

In one way, it could be considered a sequel to the Balanced Binary Tree article, answering questions such as:

  • How could one implement a efficiently balanced tree that makes sense in the real world?
  • Is recursion really the thing? Is there perhaps something even better?

But, it could also just be regarded as an introduction to how to use templates, iterators, and temporary classes.

The Self-Balancing Tree

The idea is to have a binary tree that fairly cheap; it keeps itself fairly balanced at all times. I've chosen the red-black tree algorithm. In short, it works like this:

  • Whenever a new element is inserted or deleted, the elements are shuffled about to keep the balance.

A red-black tree accomplishes this by color marking every element as either red or black, and by applying a set of rules on the colored elements' relation, a tree gets fairly balanced.

Articles and information on red-black trees are already out there on the Net; use your favourite search engine...

Templates

Templates are really cool, but could at first glance could seem a bit complicated. But trust me, they aren't really.

A template is like a "#define on steroids." It is a way to just define a behavior without deciding what specific kind of data the behavior is acting upon. The compiler will generate the neccessary code when it feels it has to.

Example:

template <class MyType>
class MyClass
{
    MyType mFoo;
public:
    MyType GetFoo() const { return mFoo;}
    .
    .
}

Here there is a template class (note the template keyword and the < >'s), MyClass. It has an attribute, mFoo, but at this point we don't know what kind if type it really is. All we know is that there is an attribute and a method, GetFoo(), that returns it. Later on, when we can use the class, we specify what MyType really is:

  .
  .

  MyClass<CString> b;                 // b is a MyClass whose
                                      // MyType is a CString
  CString s = b.GetFoo();

  typedef MyClass<int> MyIntClass;    // MyIntClass is a
                                      // MyClass whose MyType
                                      // is an int
  MyIntClass a;
  int i = a.GetFoo();

  .
  .

Does this seem to fit into a binary tree idea, or what? Ideally, we'd want to implement a binary tree that is all-purpose, generic, and so forth, and we now have a technique that at one place just could describe how the tree behaves, and later on we decide what kind of elements it should hold.

We know (or at least can guess) that each element in the tree has some kind of key, and some kind of value. At this point, we just don't care which specific types they are. Kind of like this:

template <class KeyType, class ValueType>
class BinTree
{
  .
  .
}

The source code actually has two template classes, the BinTree<class KeyType, class ValueType>, and BinTreeNode<class KeyType, class ValueType>. A BinTreeNode is the element stored in the tree, where BinTree is the actual tree gizmo.

Some notes on template classes:

  • They must be 100% inline.
  • Only the stuff that is actually used will generate code. That is, it is not a problem if one designs a big template class with a lot of functions, but the application uses only one of them. Those not used will simply not exist in the executable.

Iterators

An iterator is (often a class) used for navigating through some collection of data.

Typically, to use an iterator, you would:

  • Initialize it.
  • Determine whether it is finished.
  • Get access to the element the iterator currently is at.
  • Increment it to the next element.

Consider the simplest, and most well-used iterator in the history of software engineering:
The int!
(Sure, it isn't only just an iterator, but anyway...)

for(int i=0; i<10; i++)
{
  Foo f = mFoo[i];
  .
  .
}
  • The i=0 part initializes the iterator.
  • The i<10 part determines whether it is finished.
  • The mFoo[i] part gives access to the element the iterator currently is at.
  • The i++ part increments the iterator to the next element.

With a more generic approach, we could describe it like this:

for(SomeIterator i=theFirstElement;!i.isBeyondLastElement();i++)
{
  Element e = i.GetElement();
}

For arrays and such, the int is sufficient. But, what if we want to get elements stored in another fashion? Given the generic approach, do we really need to care about the way the elements are stored? Couldn't we just let the iterator handle that issue?

Well, of course we can, and that is also one of the big advantages of iterators, as they encapsulate the way data is stored, and just provide a means to access it.

And another thing, let's say you want to be able to traverse the data in different ways. With the iterator approach, all you have to do is to define another iterator and let it do the work.

Consider a Binary Tree:

  • If we want to access the tree's element in a sorted way, we could define a SortedWayIterator (conceptually, it could be used for access in reverse order as well, initialize it to the last element and -- instead of ++ the way through).
  • If we want to access the elements in random order, we could define a RandomOrderIterator.
  • If we want to access the elements in another fashion, we just define another iterator for the task.

The provided source implements four different kinds of iterators for traversing through the binary tree. With a tree like...

...elements are traversed like this:

Iterator Description Order
BinTree::Iterator(++) Sorted. A B C D E F
BinTree::Iterator(--) Reversed F E D C B A
BinTree::ParentFirstIterator Parent elements are traversed before their children. D B A C F E
BinTree::ParentLastIterator Parent elements are traversed after their children. A C B E F D
BinTree::ByLevelIterator Top to bottom, level by level, left to right. D B F A C E

(Exercise for the reader: Do ParentLastIterator with a -- on the ParentFirstIterator instead.)

The code using the iterators doesn't differ much, though. It is really just

for(BinTree::[IteratorNameHere]
i=theTree.Get[SomeKindOf]Iterator();!i.atEnd();i++)
{
  // The iterators use the * (and ->) operator to provide access
  // to the elements
  BinTree::Node currentNode = (*i);
  .
  .
}

Iterators vs Recursion

The iterators differ quite a lot from the way one uses recursion to traverse the tree. The iterators simply keep track of one node at the time and, depending on its children, parents, and whatnot, figures out which is the next node to visit.

The ByLevelIterator is an exception to this; it will allocate an array (with roughly tree.Size()/2 nodes) that it updates as it goes. The other iterators have virtually no memory impact (well, they do hold a pointer to the root, and a pointer to the current node, but in a world where we count memory in 100s of Mb, it's nothing).

The big advantage is, however, that iterators "hide" the way the data is stored. You could have similar iterators for other kinds of data structures (arrays, database stuff, whatever). Recursion is pretty much a special tree-thingie.

Temporary Classes

I'd like to be able to use the [] operator like this:

  myTree["Foo"] = 42;

and I expect it to work like this:

  • If "Foo" already exist just update its value, else insert a new element ("Foo",42).

That's all quite easy to do; just let the tree have a [] operator that takes a KeyType as parameter and returns a ValueType.

However, I would also like to be able to access data in a similar manner, like this:

  int i = myTree["Foo"];

And now the big issue is:
What if "Foo" doesn't exist? Well, unlike the myTree["Foo"] = 42; situation, I don't want a new element to be created. Actually, I think I'd like to throw an exeption instead.

So, the question is really:

  • How can I let the tree's [] operator behave differently depending on what side of the = sign it is?

The solution isn't all that complicated (but I still think it's kinda cool):
Let the [] return a (temporary) class (instead of just the ValueType) that:

  1. Overloads the assignment operator
  2. Has a ValueType operator

The assignment operator will then handle the myTree["Foo"] = 42; situation, and the ValueType operator handles the i = myTree["Foo"] situation. From the provided source:

template <class KeyType, class ValueType>
class BinTree
{
public:
  .
  .
  // BinTree::AccessClass. Used by the [] operator.
  class AccessClass
  {
    // Let BinTree be the only one who can instantiate this class.
    friend class BinTree<KeyType, ValueType>;
  public:
    // Assignment operator. Handles the myTree["Foo"] = 32;
situation
    operator=(const ValueType& value)
    {
      // Just use the tree's Set method, it handles already
      // exists/not exist
situation
      mTree.Set(mKey,value);
    }

    // ValueType operator. Handles int i=myTree["Foo"],
    // myTree["Bar"] == 44 etc.
    operator ValueType()
    {
      Node* node = mTree.Find(mKey);

      // Not found
      if (node==0)
      {
        throw "Item not found";
      }

      return node->GetValue();
    }
  private:
    //------------------------------
    // Private Construction
    //------------------------------
    AccessClass(BinTree& tree, const KeyType& key):mTree(tree),
                                                   mKey(key){}
    //------------------------------
    // Disabled Methods
    //------------------------------
    // Default constructor
    AccessClass();

    //------------------------------
    // Private Members
    //------------------------------
    BinTree& mTree;
    const KeyType& mKey;
  };    // AccessClass;
  .
  .
  // operator [] for access to elements
  AccessClass operator[](const KeyType& k)
  {
    return AccessClass(*this, k);
  }
  .
  .

It will also handle comparisons, such as tree["Foo"]==43 or tree["Foo"]==tree["Bar"] (any ValueType access, really) such that it will throw an exception if the requested element doesn't exist.

One could let AccessClass implement == operators (two operators: one taking ValueType as param and another taking AccessClass) that return false instead of throwing exceptions when elements don't exist; in most cases they'd probably work.

They would have a slight problem, though:
tree["NonExistent"] == 43 would return false, while 43 == tree["NonExistent"] would throw an exception. It'd be a bit inconsistent.

But We Have This Already!

With the Standard Template Library, STL, comes some classes (std::map and std::set) that conceptually are implemented pretty much like this:

  1. They are template classes.
  2. They use iterators.
  3. Internally, they are red-black trees.

If you really don't care about the implementation (but then, you probably shouldn't read this article, anyway), use them!

They do have a tendency to flood the output with inane compiler warnings, though, and are for some reason as for from humanly readable as you can get (people designing code like that should be publicly spanked, IMHO).

Anyway, if you are interested in implementation details, I hope I've given you something to start with...

About the Source Code

BinTree.h

Everything is implemented as template classes in a single, commented, file. It has no external dependencies.

BinTreeTest.cpp

The demo project is a simple console application that tests that the tree works as expected. Check its source to see how one uses the darn thing...

The red-black implementation in the source is to some extent based on:
http://www.oopweb.com/Algorithms/Documents/PLDS210/Volume/red_black.html

Downloads

Download demo project - 9 Kb
Download source - 6 Kb


Comments

  • Presentable

    Posted by Mwanyu on 01/04/2006 06:44am

    Can be pleasing to ilustrate..

    Reply
  • Very good, but found a small bug...

    Posted by Yudi on 11/21/2004 05:50pm

    Hi :) Really liked the artical, and found it very useful. Something seems to be missing though. When deleting a black node, certain items need to be re-colored to mantain the red-black properties of the tree. I like your implementation and I'd appreciate it if you can fix it. Thanks!! Yudi.

    Reply
  • a little idea

    Posted by jolley on 05/03/2004 01:56am

    template 
    class MyClass
    {
        MyType mFoo;
    public:
        MyType GetFoo() const { return mFoo;}
        .
        .
    }
    
    I think that we should give the mFoo a value first.such as a set function,peharps
    for(int i=0; i<10; i++)
    {
      Foo f = mFoo[i];
      .
      .
    }
    it maybe a lovely way of express how to use iterators in a freshment 
    template 
    class BinTree
    {
    public:
      .
      .
      // BinTree::AccessClass. Used by the [] operator.
      class AccessClass
      {
        // Let BinTree be the only one who can instantiate this class.
        friend class BinTree;
      public:
        // Assignment operator. Handles the myTree["Foo"] = 32;
    situation
        operator=(const ValueType& value)
        {
          // Just use the tree's Set method, it handles already
          // exists/not exist
    situation
          mTree.Set(mKey,value);
        }
    
        // ValueType operator. Handles int i=myTree["Foo"],
        // myTree["Bar"] == 44 etc.
        operator ValueType()
        {
          Node* node = mTree.Find(mKey);
    
          // Not found
          if (node==0)
          {
            throw "Item not found";
          }
    
          return node->GetValue();
        }
      private:
        //------------------------------
        // Private Construction
        //------------------------------
        AccessClass(BinTree& tree, const KeyType& key):mTree(tree),
                                                       mKey(key){}
        //------------------------------
        // Disabled Methods
        //------------------------------
        // Default constructor
        AccessClass();
    
        //------------------------------
        // Private Members
        //------------------------------
        BinTree& mTree;
        const KeyType& mKey;
      };    // AccessClass;
      .
      .
      // operator [] for access to elements
      AccessClass operator[](const KeyType& k)
      {
        return AccessClass(*this, k);
      }
      .
    I do not agree with you very much ,because I never write
    a class in that way ,it doesnot read well   but I very admire your way of thinking

    • Re:a little idea

      Posted by PerFnurt on 05/03/2004 06:23am

      >I think that we should give the mFoo a value first Sure. But you could simply assume thats done somewhere, not revealed in the tiny code snippet since it has nothing to do with what Im trying to illustrate. >it doesnot read well It does to me

      Reply
    Reply
  • it's GOOD for me

    Posted by koskinen on 03/16/2004 07:23am

    thanks a lot

    • great help

      Posted by t3chn0n3rd on 12/16/2007 12:06pm

      thank you

      Reply
    Reply
  • iterators?

    Posted by Legacy on 05/16/2003 12:00am

    Originally posted by: John Torjo

    You have not quite gave a correct definition of
    "iterator", as is used in Standard C++.

    It should be more like:
    "an abstraction of a pointer". an advantage of iterators is that they can be further constrained than pointers
    (for instance, you can have an iterator that allows only forward iteration - a forward iterator).

    Your article, while it's quite good, doesn't show how iterators in STL are used, iterator categories, etc.

    Reply
  • 100% inline?

    Posted by Legacy on 05/06/2003 12:00am

    Originally posted by: David P

    The statement about functions in template classes, "They
    
    must be 100% inline", is misleading.

    Functions in template classes do not have to be inline.
    However, the source code for the template class must be
    available to the compiler at the point where you
    instantiate an object. For example:

    /* Template.h */
    template <class T>
    class MyTemplate {
    T square(T x);
    };

    /* Template.cpp */
    #include "Template.h"
    template <class T>
    T MyTemplate<T>::square (T x)
    { return x * x; }

    /* Main.cpp */
    #include "Template.h"

    void main()
    {
    MyTemplate mt;
    double nine = mt.square(3.0);
    }

    When the compiler compiles Main.cpp, it will need to
    compile square() with "T" set to "double", but cannot
    because it hasn't seen the source code to square(). So you
    will get an error.

    The way I fix this problem is simply to add the following
    line to the end of Template.h:

    #include "Template.cpp"

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • The explosion in mobile devices and applications has generated a great deal of interest in APIs. Today's businesses are under increased pressure to make it easy to build apps, supply tools to help developers work more quickly, and deploy operational analytics so they can track users, developers, application performance, and more. Apigee Edge provides comprehensive API delivery tools and both operational and business-level analytics in an integrated platform. It is available as on-premise software or through …

  • Java developers know that testing code changes can be a huge pain, and waiting for an application to redeploy after a code fix can take an eternity. Wouldn't it be great if you could see your code changes immediately, fine-tune, debug, explore and deploy code without waiting for ages? In this white paper, find out how that's possible with a Java plugin that drastically changes the way you develop, test and run Java applications. Discover the advantages of this plugin, and the changes you can expect to see …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds