An Introduction to "Iterator Traits"

Introduction

If you go by dictionary, a trait means feature/attribute. In C++ there is no exception, here iterator traits means the feature/attribute of C++ Iterator. Before digging further, first we need to understand the design basics of iterator in C++.

In C++ STL (Standard Template Library), 3 things are meaningful and important:

1. Containers: These are used to manage collection of objects of a certain kind. Containers can be of two types: Sequence Containers (vector, deque, list) and Associative Containers (Set, Multiset, Map, Multimap).
2. Algorithms: These are used to process the elements of a collection. That is algorithms feed from containers and process those elements in a predefined way and may also push the results into the same/different container.
3. Iterator: These are used to step through the elements of collection of objects (aka containers).

The designer of STL chose a wonderful yet simple common approach - "The separation of data and operation".

• The data is held and managed by the Container classes.
• The operations over the containers are defined and managed by the configurable algorithms.

So, if Container classes and algorithms are completely different entities, there has to be a bridge between them, right? There has to be a dedicated tunnel between them, there has to be some kind of glue between them. Yes, you are right <=====> Iterators are those Bridge/Tunnel/Glue.

Someone might argue that STL concepts of Container/Algorithm/Iterator contradicts with the fundamental ideas of Object Oriented Programming: The STL separates the Data and the Operations (Algorithm) over it <---> rather than combining them. The beauty and flexibility of this design is you can almost bind up every kind of container with every kind of algorithm (by kind of algorithm, I mean to say - Modifying/Non-modifying/Mutating/Sorting/Numeric etc.).

Background

The introduction is done, but still in order to write iterator traits specific code, a little bit of background needs to be revised/polished. As you all know, iterators actually have different categories (Random Access, Bidirectional, etc). Different iterator categories have been built for different abilities.

Still sometimes it is almost necessary and mandatory to overload different iterator's ability/behavior in a seamless manner (aka - iterator independently for users/outsiders). You can just stop me here and ask ....... hey wait. What did you just say? "You want to overload the behavior of iterators in a iterator independent manner? What the heck does that mean?"

Yes, you read it correctly - sometimes it is absolute necessary to overload different iterator's behavior in a common platform, so that for outsiders it seems seamless.

Ok, you need an example? There are thousands of them. I will give a few of them:

1. C++

   difference_type count(Iterator iter1, Iterator iter2)

2. C++

   difference_type count_if(Iterator iter1, Iterator iter2, UnaryPredicate op)

The role of count algorithm is to count the number of elements in a container that has a certain value (form 1), and those satisfy a Unary Predicate (form 2) .... naturally a question comes, what will be the return type of those? The first thought could be ....... hey blah....... it could be an INT/SHORT. But no, that's not generic programming. We'll find this answer soon.
Another point here is: you should write your generic algorithm (count/count_if here) in such a manner that the user can call it up for any kind of containers (and thus for any kind of iterators). So you need to write these in such a manner that - generic function should behave seamlessly for any kind of iterator.

Another example is the distance() method. This method takes two Iterator positions and returns back the numeric distance between them. This method also works for all kinds of container and thus for all kinds of iterators.

There are many more.......... refer to the STL algorithm section for details.

So here comes the big question. How we can write a generic function/algorithm in a seamless manner?

Big thanks to the STL designers: They provide us everything. For this job few things they provide are a bit tricky, but they are very simple and useful.

First: for each iterator category, the C++ library provides an <iterator tag> that can be used as a "LABEL" for iterators. This structure looks like this: (you'll find it in a file named stl_iterator_base_types.hpp, I am using MinGw).

//@{
  /**
   *  @defgroup iterator_tags Iterator Tags
   *  These are empty types, used to distinguish different iterators.  The
   *  distinction is not made by what they contain, but simply by what they
   *  are.  Different underlying algorithms can then be used based on the
   *  different operations supported by different iterator types.
  */
  ///  Marking input iterators.
  struct input_iterator_tag {};
  ///  Marking output iterators.
  struct output_iterator_tag {};
  /// Forward iterators support a superset of input iterator operations.
  struct forward_iterator_tag : public input_iterator_tag {};
  /// Bidirectional iterators support a superset of forward iterator
  /// operations.
  struct bidirectional_iterator_tag : public forward_iterator_tag {};
  /// Random-access iterators support a superset of bidirectional iterator
  /// operations.
  struct random_access_iterator_tag : public bidirectional_iterator_tag {};
  //@} 

Note that inheritance is used. So, for example, any forward iterator is a kind of input iterator. However, note that the tag for forward iterators is only derived from the tag for input iterators, not from the tag for output iterators. Thus, any forward iterator is not a kind of output iterator. In fact, forward iterators have requirements that keep them from being output iterators.

If you write generic code, you might not only be interested in the iterator category. For example, you may need the type of the elements to which the iterator refers. Therefore, the C++ standard library provides a special template structure to define the iterator traits. This structure contains all relevant information regarding an iterator. It is used as a common interface for all the type definitions an iterator should have (the category, the type of the elements, and so on):

 namespace std {
    template <class T>
    struct iterator_traits {
        typedef typename T::value_type            value_type;
        typedef typename T::difference_type       difference_type;
        typedef typename T::iterator_category     iterator_category;
        typedef typename T::pointer               pointer;
        typedef typename T::reference             reference;
    };
}

In this template, T stands for the type of the iterator. Thus, you can write code that uses for any iterator in its category, the type of its elements, and so on. For example, the following expression yields the value type of iterator type T:

typename std::iterator_traits<T>::value_type

This structure has two advantages:

1. It ensures that an iterator provides all type definitions.
2. It can be (partially) specialized for (sets of) special iterators. The latter is done for ordinary pointers that also can be used as iterators:

namespace std {
    template <class T>
    struct iterator_traits<T*> {
        typedef T                          value_type;
        typedef ptrdiff_t                  difference_type;
        typedef random_access_iterator_tag iterator_category;
        typedef T*                         pointer;
        typedef T&                         reference;
    };
}

Thus, for any type "pointer to" "T", it is defined that it has the random access iterator category. A corresponding partial specialization exists for constant pointers (const T*). 

Using the Code

Writing Generic Functions for Iterators

Using iterator traits, you can write generic functions that derive type definitions or use different implementation code depending on the iterator category.

Using Iterator Categories

To use different implementations for different iterator categories, you must follow these two steps:

1. Let your template function call another function with the iterator category as an additional argument. For example:
   C++

   template <typename Itr>
   inline void my_function(Itr begin, Itr end)
   {
       my_function (beg, end,
           std::iterator_traits<Itr>::iterator_category());
   }  

2. Implement that other function for any iterator category that provides a special implementation that is not derived from another iterator category. For example:
   C++

   //my_function() for bidirectional iterators
    template <typename BidectionalIterator>
    void my_function (BidectionalIterator begin, BidirectionalIterator end,
                      std::bidirectional_iterator_tag)
    {
          //Bidirectional Iterator specific code is here
    }
   
   //my_function() for random access iterators
    template <typename RandomIterator>
    void  my_function(RandomIterator begin, RandomIterator end,
                      std::random_access_iterator_tag)
    {
   
               // Random access Iterator specific code is here
    }
   

Implementation of distance()

An example of following the steps in the previous subsection is the implementation of the auxiliary distance() iterator function. This function returns the distance between two iterator positions and their elements. The implementation for random access iterators only uses the operator - (aka, unary minus). For all other iterator categories, the number of increments to reach the end of the range is returned.

PLEASE READ THE COMMENTS CAREFULLY IN THE FOLLOWING CODE.

 //User always calls this method, general method for distance()

// User needs to satisfy the following 2 criteria: 
// For random access iterator, second iterator position must come 
// after first iterator position/
// For all other kind of iterator, second iterator must be reachable from first iterator
// Both of the iterator must refer to the same container, otherwise result is undefined
    template <typename Iterator>
    typename std::iterator_traits<Iterator>::difference_type
    distance (Iterator pos1, Iterator pos2)
    {
        return distance (pos1, pos2,
                         std::iterator_traits<Iterator>
                            ::iterator_category()); 
    }
 
    //Core implementation ..... distance() for random access iterators
    template <typename RandomAccessIterator>
    typename std::iterator_traits<RandomAccessIterator>::difference_type
    // Note the return type above, it solely depends on Iterators declared typedefs,
    // no so called INT/SHORT here
    distance (RandomAccessIterator first_position, RandomAccessIterator second_position,
               std::random_access_iterator_tag) 
    {
        return second_position - first_position; 
    }


    //distance() for input, forward, and bidirectional iterators
    // Keep in mind that here we are using only Input iterator tags, so
    // forward and bidirectional iterator will also be in this bucket, because we
    // used Inheritance while declare forward and bidirectional iterator tags.

    template <typename InputIterator>
    typename std::iterator_traits<lnputIterator>::difference_type
    // Note the return type here, truly generic
    distance (Inputlterator first_position, InputIterator second_position,
              std::input_iterator_tag) 
    {
        // note the type of the temp variable here, truly generic 
        typename std::iterator_traits<lnputIterator>::difference_type diff;
        for (diff=0; first_position != second_position; ++first_position, ++diff) {
             ;
        }
        return diff; 
    }  

The difference type of the iterator is used as the return type. Note that the second version uses the tag for input iterators, so this implementation is also used by forward and bidirectional iterators because their tags are derived from input_iterator_tag.

We can derive the same logic for defining the return type for count/count_if. So the ideal generic return type should be:

template <typename iterator>
typename std::iterator_traits<iterator>::difference_type
count(iterator itr1, iterator itr2){
// Your logic
}

Further Implementation 

You can write tons and tons of generic functions by just adapting this style. This style is really necessary when you end up with a generic function that should work seamlessly for any kind of iterator. 

References 

• C++ Programming Language - by Stroustrup
• C++ Standard Library: A Tutorial and Reference - by Josutis 

History

• 18^th May, 2009: Initial post