4.6 Building an Iterator Class

To illustrate how to overload a set of operators for a class, let's walk through the implementation of an iterator class. We must support the following usage:

Triangular trian( 1, 8 ); 


Triangular::iterator 


            it = trian.begin(), 


            end_it = trian.end(); 





while ( it != end_it ) 


{ 


    cout << *it << ' '; 


    ++it; 


} 

For this to work, of course, the operators !=, *, and ++ must be defined for objects of the iterator class. How do we do this? We define them as operator member functions. An operator function looks like an ordinary function except that rather than provide the function with a name, we specify the keyword operator followed by the operator we wish to overload. For example,

class Triangular_iterator 


{ 


public: 


//  set _index to index-1 in order not to subtract 1 with 


//  each element access ... 


    Triangular_iterator( int index ) : _index( index-1 ){} 


    bool operator==( const Triangular_iterator& ) const; 


    bool operator!=( const Triangular_iterator& ) const; 


    int  operator*() const; 


    int& operator++();       // prefix version 


    int  operator++( int );  // postfix version 


private: 


    void check_integrity() const; 


    int _index; 


}; 

The Triangular_iterator class maintains an index into the Triangular class static data member, _elems, which holds the sequence elements. (For this to work, the Triangular class must grant special access permission to the member functions of the Triangular_iterator class. In Section 4.7 we see how to grant access privilege through the friend mechanism.) Two Triangular_iterator class objects are equal if the two _index members are equal:

inline bool Triangular_iterator:: 


operator==( const Triangular_iterator &rhs ) const 


          { return _index == rhs._index; } 

An operator is applied directly to the class object(s):

if ( trian1 == trian2 ) ... 

If we wish to apply the operator to a class object addressed by a pointer, we must first dereference the pointer to gain access to the class object:

if ( *ptri1 == *ptri2 ) ... 

The complement of an operator is typically implemented in terms of its associated operator. For example,

inline bool Triangular_iterator:: 


operator!=( const Triangular_iterator &rhs ) const 


          { return !( *this == rhs ); } 

The rules governing operator overloading are as follows:

• We cannot introduce new operators. All the predefined operators can be overloaded except the four operators ., .*, ::, and ?:.

• The predefined arity of the existing operators cannot be overridden. Every binary operator must be provided with two operands, and every unary operator with only one. We cannot define the binary equality operator, for example, to take either more or fewer parameters than its predefined two.

• The predefined precedence of the existing operators cannot be overridden. For example, the division operator always takes precedence over addition.

• An operator function must take at least one class type as an argument. That is, we cannot redefine existing operators or introduce operators for nonclass types, such as pointers.

An operator can be defined either as a member operator function,

inline int Triangular_iterator:: 


operator*() const 


{ 


    check_integrity(); 


    return Triangular::_elems[ _index ]; 


} 

or as a nonmember operator function,

inline int 


operator*( const Triangular_iterator &rhs ) 


{ 


    rhs.check_integrity(); 





    // note: the non-member instance has no 


    // access privilege to nonpublic members 


    return Triangular::_elems[ rhs.index() ]; 


} 

The parameter list of a nonmember operator always defines one more parameter than its member operator counterpart. In a member operator, the this pointer implicitly represents the left operand.

The check_integrity() member function ensures that _index is not larger than _max_elems and that _elems holds the necessary elements.

inline void Triangular_iterator:: 


check_integrity() const 


{ 


    // we'll look at the throw expression in Chapter 7 ... 


    if ( _index > Triangular::_max_elems ) 


         throw iterator_overflow(); 





    // grow vector if necessary ... 


    if ( _index > Triangular::_elems.size() ) 


         Triangular::gen_elements( _index ); 


} 

We must provide a prefix (++trian) and postfix (trian++) instance of the increment operator. The prefix instance is defined with an empty parameter list:

inline int& Triangular_iterator:: 


operator++() 


{   // prefix instance 


    ++_index; 


    check_integrity(); 


    return Triangular::_elems[ _index ]; 


} 

Ordinarily, the postfix instance would also be defined with an empty parameter list. However, each overloaded operator must have a unique parameter list. The language solution is to require that we define the postfix instance with a single integer parameter:

inline int Triangular_iterator:: 


operator++( int ) 


{ 


    // postfix instance 


    check_integrity(); 


    return Triangular::_elems[ _index++ ]; 


} 

Both the prefix and the postfix instance of the increment (and decrement) operator can be applied directly to an object of the class:

++it; // prefix 


it++; // postfix 

Where is the single integer argument for the postfix instance? The compiler generates that for us automatically to force the postfix instance of the operator to be called. Happily, the user does not need to bother about it.

Our next task is to provide a begin() and end() pair of member functions for the Triangular class as well as to support the definition of iterator. The iterator support requires that I introduce the topic of nested types, which is discussed soon.

First, however, here are the necessary modifications to the Triangular class definition:

#include "Triangular_iterator.h" 





class Triangular { 


public: 


   // this shields users from having to know 


   // the actual name of the iterator class ... 


   typedef Triangular_iterator iterator; 





   Triangular_iterator begin() const 


   { 


        return Triangular_iterator( _beg_pos ); 


   } 





   Triangular_iterator end() const 


   { 


        return Triangular_iterator( _beg_pos+_length ); 


   } 


   // ... 





private: 


   int   _beg_pos; 


   int   _length; 


   // ... 


}; 

Nested Types

A typedef introduces an alternative name for a type, and takes this general form:

typedef existing_type new_name; 

Here, existing_type can be a built-in, compound, or class type. In our example, we provide iterator as a synonym for the Triangular_iterator class in order to simplify its use. The syntax for defining an object of type iterator

Triangular::iterator it = trian.begin(); 

uses the class scope operator to direct the compiler to look in the Triangular class definition for the declaration of iterator. If we simply write

iterator it = trian.begin(); // error 

the compiler does not know to look within the Triangular class for the declaration of iterator, so the definition of it is flagged as an error.

By nesting iterator within each class that supports the iterator abstraction, we can provide multiple definitions with the same name but at the cost of a more complex declaration syntax.

Fibonacci::iterator   fit = fib.begin(); 


Pell::iterator        pit = pel.begin(); 


vector<int>::iterator vit = _elems.begin(); 


string::iterator      sit = file_name.begin();