Section 3 - Constructing Templates by Subclassing from STL Containers

8B.3.1  Our Cake and Eating It

We finally have the vocabulary and perspective to compare what we gained and where we fell short when moving from our older custom list base classes to using the STL list class (and STL algorithms).  We will find there is a gap, and we fill that gap by adding a little home-made template on top of the STL list class.   This will show us how to deal with just about any shortcoming of the STL containers without having to start from scratch.

The STL solution to the FloatList problem was nice in that we could create a FloatList in a single line:

typedef insertableList<float> FloatList;

Now we have a new type, FloatList that we can work with using iterators, special methods and algorithms.  We have two problems, however:

1. We had to write new code to effect the general insert() and remove() methods.  These are the hardest methods to write, yet there are many classes (like float, int or any class that has a < operator) and applications in which we want to insert things into the list in ascending order.   It seems like there should already be insert() method inside some list class that is ready to go.
2. Once we wrote the class that polished off these two remaining methods (and showList()) for floats, we really did not have a solution that could be extended to any other type: we could not re-use the code we wrote.  It had to be copied, pasted, searched and replaced to work for other types.

What we would like is a template ascending_list that is exactly like the STL list, but has the two methods insert() and remove() already written.  (We will forego showList() since that is I/O dependent and, anyway, we could dream up more general replacements for it, such as ToString() - we will leave that as an assignment for the reader and allow showList() to be a global scope function for the remainder of this lesson.)

To be clear, we are looking for a template ascending_list that can be instantiated like so:

ascending_list<float> myList;

and which immediately, and without any further ado, admits invocations myList.insert(x) and myList.remove(x) that places x in the correct position in the list and removes (with a bool return type) x from the list, respectively.  If we have such a template, then we can use it for any type, not just float, and we don't have to write a single line of code.  (Of course this will only work for classes in which <, <=, > and/or >= are overloaded, but we can live with that!).

8B.3.2 Building Templates from Templates

We can accomplish this by combining inheritance with templates.  We will create a new template ascending_list that is inherited from the STL list.  We will add the two methods insert() and remove() (actually we are overriding remove() since it already exists in list).  Here is our template prototype:

template <class T>
class ascending_list : public list<T>
{
public:
  void insert(T x);
  bool remove(T x);
};

It's really not that bad, as you can see.  We use the class parameter T in the inheritance line, and it is a list<T> that we are using as our base class.  From here the main() method is a piece of cake - we just start using our functions insert() and remove().

Here is the full main() followed by the implementation of the above template prototype.  Remember:  we have just created something that won't have to be reproduced -- ascending_list is ours to use on any class from this point forward.

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

template <class T>
class ascending_list : public list<T>
{
public:
  void insert(T x);
  bool remove(T x);
};

typedef ascending_list<float> FloatList;
void showList(FloatList &myList);

// main method ---------------------------------------
int main()
{
  FloatList myList;
  int k;
  float x;

  // build list of 10 floats, 2 at a time (1 random and 1 k*100)
  for (k = 0; k < 5; k++)
  {
    x = 1000 * (float)rand()/(float)RAND_MAX; // bet 0 and 1000
    myList.insert(x);
    myList.insert(k*100);
  }

  // should be sorted
  showList(myList);

  // remove 5 nodes (and delete them!)
  for (k = 0; k < 5; k++)
  {
    x = k*100;
    if (myList.remove(x))
      cout << x << " removed\n";
    else
      cout << x << " not found.\n";
  }
  showList(myList);

  if (!myList.remove(-10)) // should have no effect
    cout << " -10 not in list as expected. ";
  showList(myList);

  return 0;
}

// ascending_list method definitions --------------------------
template <class T>
void ascending_list<T>::insert(T x)
{
  this->push_front(x);
  this->sort();
}

template <class T>
bool ascending_list<T>::remove(T x)
{
  list<T>::iterator found;
  found = find(this->begin(), this->end(), x);
  if (found == this->end())
    return false;

  list<T>::remove(x); // we reference the base class remove()
  return true;
}

void showList(FloatList &myList)
{
  list<float>::iterator iter;

  cout << endl << "_____Here's the List_______" << endl;
  for( iter = myList.begin(); iter != myList.end(); iter++)
  {
    cout.setf(ios::fixed);
    cout.precision(3);
    cout << "[" << *iter << "] ";
  }
  cout << endl << "_____That's all!_______" << endl << endl;
}

I have not been adding the output (run) of the programs in any of these FloatList examples because they are all identical to the first run we got weeks ago - that was our goal with them.  We wanted the same behavior.  You can run any of them to verify this.

I want to emphasize that the two method definitions for insert() and remove() should really be ignored when you evaluate the simplicity of the above solution.  They will not be in the source code here or in future instantiations of ascending_list because they are tucked away in the ascending_list.h header file.

Well this was pretty easy.  You might consider how we could make this ascending or descending and add other features to make the new template applicable to a wider range of applications, and when you do, be sure to change the name from ascending_list to something more fitting.

This last example, as simple as it is, gives us a framework for using templates, STL containers, algorithms and inheritance in pretty much any combination that we wish to build truly reusable code.  It contains quite a bit of C++ power and experience bundled into a small example.  If you understand it and can reproduce similar code, you are doing very well.