Creating Custom STL Iterators for Linked Lists

Environment: VC6, SP4

Purpose

This article describes a technique of implementing your own STL type custom iterators for those who have developed their own algorithms and/or other abstract data types.

Preamble

Initially, I possessed what I thought was a pretty good set of doubly linked list routines. These had evolved over time and had been tested on so many operating systems that I was satisfied that my code was fast, robust, and bug-free. Although the code was initially developed in “C” before the days of C++, the code worked and performed quite well.

When C++ became firmly established, the transition of my C code to C++ was initially quite simple. I merely installed a class wrapper around my function calls using the extern “C” paradigm. However, although this technique was easy, I found that ultimately the code appeared ugly and half completed. It was well documented however and I decided to submit it to the codeguru (see here).

My article certainly generated some passionate responses. People either liked it or loathed it!

The Problem

Assume you have a set of algorithms encapsulated in an appropriate container and fully C++ compliant in terms of polymorphic behavior, written in orthodox canonical form, and so forth. Now apply the STL iterator paradigm to it such that you may iterate over elements in the container:

CMyUniqueContainer<T&gt myContainer;

CMyUniqueContainer<T&gt::iterator Iter = myContainer.begin();

The Solution

Is not as simple as you might think. There are plenty of resources available on the Internet, but there is a distinct shortage of step-by-step examples on the subject. The example here takes the functionality of my previous ClinkedList article and provides one (of very many) ways to implement an STL equivalent solution.

Theoretically, you don’t ever have to write your own Linked Lists because they exist in the STL as just such a container class. Given this, now assume that your code is better in many respects to the STL Algorithms and Container classes. If you study the STL code in some depth you may discover that it has many good points and some bad (just look at all of those function calls!). Is there a way to utilize the STL so that it is complementary to your code? (For example, using the STL std::sort() algorithm is inefficient for large lists and you wouldn’t use it in real-time or mission-critical applications where every micro-second counts!)

The short answer is “there is!”, but in order to create your own code compatible with the STL, you must make your class behave like a container class; further, you need to be able to access its methods and properties by using STL iterators.

In short, an STL iterator is a class that behaves like a pointer. There are different types, too:

• Input Iterators (not used herein)


• Output Iterators (not used herein)


• Forward Iterators (not used herein)


• Bidirectional Iterators (const and non-const )


• Random Access Iterators (const and non-const)

Each one of these iterators has a particular purpose, but I have included the file “CIDIteratorBase.h” that defines these for you, so you don’t have to worry about how to get the classes coded and working. An explanation of iterators and their functionality and use within the STL will not be included here, as it probably deserves at least one or two chapters in a book to cover these effectively.

Okay, now you have a set of iterators. How do you get them to work in your own classes? The answer is that you must create your own custom container classes which in turn contain inner classes called iterators.

Here is an example of a custom container class that manages a doubly linked list (CIDListBase.h). This class contains all minimal functionality for a linked list, but this may be further built on by deriving from the class presented.

Finally, there is the CIDLinkedList.h file containing a class I want to use by extending the functionality of the CIDListBase class, as well as my own quick sort routine which is definitely faster than std::sort(). ( I have used Dean Wyant’s CperfTimer performance timer class to prove it! )

I have made the source files as generic as possible, but I believe that these files contain enough information for the reader to modify to suit his or her own needs:

The Demo includes a HTMLHelp file, exercises, most of the code, and many of the STL algorithms including:

• accumulate


• advance


• copy


• count


• count_if


• equal


• fill


• find


• find_first_of


• find_if


• for_each


• generate_n


• max_element


• remove


• replace


• replace_if


• reverse


• reverse_copy


• transform

Example Use

#include “CIDLinkedList.h”

try {

   CIDLinkedList<int> myIntList;

   CIDLinkedList<int>::iterator Iter;

   // Add some ints to the list
   for( int i = 0; i < 5; i++ ) {

      myIntList.push_back( i + 1 );

   }
   cout << “List contains (” << myIntList.size() << “) elements” << endl;

   cout << “Printing list contents…” << endl;

   // Print to the screen using 1 method

   std::copy( myIntList.begin(),

              myIntList.end(),

              ostream_iterator<int>( cout, “n” ) );
   cout << “Printing again…” << endl;

   // Print using another method

   for(  Iter = myIntList.begin();

         Iter != myIntList.end();

         Iter++ )

   {

       cout << *Iter << endl;

   }
   cout << “Sorting with std::sort()” << endl;

   std::sort( myIntList.begin(), myIntList.end() );
   cout << “Printing again…” << endl;

   std::copy( myIntList.begin(),

              myIntList.end(),

              ostream_iterator<int>( cout, “n” ) );
   cout << “Sorting with internal list qsort()” << endl;

   // Set the comparison function

   myIntList.setcompare( ReverseIntCompare );
   myIntList.sort();
   // Print the sorted list (now in reverse order)

   cout << “Printing again…” << endl;

   std::copy( myIntList.begin(),

              myIntList.end(),

              ostream_iterator<int>( cout, “n” ) );

}

catch( CIDListException &e ) {

   cout << “CIDLinkedList exception caught!” << endl;

   cout << “Reason: ” << e.Why() << endl;

}

Happy Coding,

Ian