Creating Custom STL Iterators for Linked Lists

Environment: VC6, SP4


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.


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> myContainer;
CMyUniqueContainer<T>::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:

CIDIteratorBase.h Contains minimum iterator class definitions
CIDListBase.h Contains a class definition for a minimum use linked list
CIDLinkedList.h Inherits from CIDListBase and adds functionality to compare with my previous list article

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(),
              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(), 
              ostream_iterator<int>( cout, "\n" ) );

   cout << "Sorting with internal list qsort()" << endl;
   // Set the comparison function
   myIntList.setcompare( ReverseIntCompare );


   // Print the sorted list (now in reverse order)
   cout << "Printing again..." << endl;
   std::copy( myIntList.begin(),
              ostream_iterator<int>( cout, "\n" ) );
catch( CIDListException &e ) {
   cout << "CIDLinkedList exception caught!" << endl;
   cout << "Reason: " << e.Why() << endl;

Happy Coding,




  • Very useful

    Posted by Legacy on 05/27/2002 12:00am

    Originally posted by: Christian Lipp

    The CIDIteratorBase.h is very useful,
    but I noticed that the const_iterator and
    the iterator only differ in the returnvalue
    of operator*.

    Wouldn't a iterator<const T> do the same?

    • cann't download sample demo project

      Posted by on 04/19/2004 02:07am

      Hi, I cann't download the sample demo project. Can anyone kindly please send a copy to me ? thanks

  • Nice trick

    Posted by Legacy on 05/21/2002 12:00am

    Originally posted by: Kaushal Malhotra

    Ian, I like you tricks esp. to copy the whole list to stdout. Cooooool!!
    These days I am hearing some fuss about iterators. May I give an example of code to explain my point:

    typedef std::set<TYPE> TYPESet;

    TYPESet::iterator it;
    const TYPESet::iterator& it2 = tset.end();
    for (it = MEMBER.begin(); it != it2; ++it) {
    Is this practice of using it2 prefetched, dangerous, even if we are not changing the size of set(like we delete 100 elements and add 100 making size same to previous one)
    I tried various ways to crash this code like:

    const TYPESet::iterator& it2 = tset.end();
    for(i = 0;i < 100;i++)
    char *buff = new char[1024];
    for(i = 0;i < 100;i++)
    if(it2 != tset.end())
    cout << "Not same";
    cout << "same";
    Can you give an example which uses similar it2 where it crashes.

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

Top White Papers and Webcasts

  • Anthony Christie, the Chief Marketing Officer for Level Communications, is responsible for customer experience, worldwide marketing and product management. In this informative asset, he shares his insights into why a private network connection to cloud-bases applications is the right decision for your enterprise. Download now to find out more.

  • Enterprises are increasingly looking to platform as a service (PaaS) to lower their costs and speed their time to market for new applications. Developing, deploying, and managing applications in the cloud eliminates the time and expense of managing a physical infrastructure to support them. PaaS offerings must deliver additional long-term benefits, such as a lower total cost of ownership (TCO), rapid scalability, and ease of integration, all while providing robust security and availability. This report …

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date