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> 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(),
              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



Downloads

Comments

  • 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 alicia_ylhew@yahoo.com 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 ylhew@yahoo.com

      Reply
    Reply
  • 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) {
    (*it)->FUNCTION();
    }
    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++)
    tset.erase(i);
    char *buff = new char[1024];
    for(i = 0;i < 100;i++)
    tset.insert(i);
    if(it2 != tset.end())
    cout << "Not same";
    else
    cout << "same";
    Can you give an example which uses similar it2 where it crashes.

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

Top White Papers and Webcasts

  • On-demand Event Event Date: September 10, 2014 Modern mobile applications connect systems-of-engagement (mobile apps) with systems-of-record (traditional IT) to deliver new and innovative business value. But the lifecycle for development of mobile apps is also new and different. Emerging trends in mobile development call for faster delivery of incremental features, coupled with feedback from the users of the app "in the wild." This loop of continuous delivery and continuous feedback is how the best mobile …

  • Stories about devastating cyberattacks are plaguing the news. Why? The DNS protocol is easy to exploit. See your network the way hackers do—as an easy target. Learn how you can effectively secure your DNS infrastructure today.

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds