Writing my own implementation of stl-like Iterator in C++

Question

I'm currently trying to understand the intrinsics of iterators in various languages i.e. the way they are implemented.

For example, there is the following class exposing the list interface.

template<class T>
class List
{

    public:

    virtual void Insert( int beforeIndex, const T item ) throw( ListException ) =0 ;
    virtual void Append( const T item ) =0;   

    virtual T Get( int position ) const throw( ListException ) =0;
    virtual int GetLength() const =0;

    virtual void Remove( int position ) throw( ListException ) =0;


    virtual ~List() =0 {};
};

According to GoF, the best way to implement an iterator that can support different kinds of traversal is to create the base Iterator class (friend of List) with protected methods that can access List's members. The concrete implementations of Iterator will handle the job in different ways and access List's private and protected data through the base interface.

From here forth things are getting confusing. Say, I have class LinkedList and ArrayList, both derived from List, and there are also corresponding iterators, each of the classes returns. How can I implement LinkedListIterator? I'm absolutely out of ideas. And what kind of data can the base iterator class retrieve from the List (which is a mere interface, while the implementations of all the derived classes differ significantly) ?

Answer 1

STL doesn't really employ abstract base classes and virtual functions. Instead it is knowingly designed not to be OO (in the sense of GoF) and built entirely on templates, aiming for "compile-time polymorphism". Templates don't care about abstract interfaces. Things work as long as they have a sufficiently similar interface (e.g if you were to call Append push_back instead, more code expecting STL compliant containers would work for you, such as std::back_insert_iterator).

A STL compliant iterator would have to overload lots of operators to behave like a pointer (as far as possible, given the limitations of the container), including *, ->, ++, -- (if bidirectional - doubly linked), == and !=.

Answer 2

The C++ standard library does not use polymorphism and inheritance in its implementation of iterators; instead, it uses C++ template metaprogramming and the notion (but not formal syntax*) of "concepts".

Essentially, it will work if the interface for your iterator class adheres to some set of requirements. This set of requirements is called a "concept". There are several different iterator concepts (see this page for a list of all of them), and they are hierarchical. The basics of creating a compatible C++ iterator is to make your interface conform to the concept. For a simple iterator that goes only in the forward direction, this would require:

• A typedef value_type for the value that results from dereferencing your iterator.
• A typedef reference_type, which is the reference type for the corresponding value type.
• A typedef pointer, which is a pointer type for the corresponding value type.
• A typedef iterator_category, which needs to be one of input_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, or random_access_iterator_tag, depending on your traversal mechanism.
• A typedef difference_type indicating the result of subtracting two different iterators.
• A const value_type& operator*()const function for dereferencing the iterator.
• A value_type& operator*() function if your iterator can be used to manipulate the value.
• Increment (operator++() and operator++(int) functions) for seeking forward.
• A difference function: difference_type operator-(const type_of_iterator&)

If you choose one of the more advanced iterator categories, you may also need to specify a decrement and plus operator in order to be able to seek backwards or to seek an arbitrary distance.

*The C++ standard library uses concepts so frequently in an informal way, that the C++ standards commitee sought to introduce a formal mechanism of declaring them in C++ (currently they exist only in documentation of the standard library, and not in any explicit code). However, persistent disagreements on the proposal led to it being scrapped for C++0x, although it will likely be reconsidered for the standard after that.