24 Iterators library [iterators]

24.4 Iterator primitives [iterator.primitives]

24.4.1 Iterator traits [iterator.traits]

To implement algorithms only in terms of iterators, it is often necessary to determine the value and difference types that correspond to a particular iterator type. Accordingly, it is required that if Iterator is the type of an iterator, the types

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category

be defined as the iterator's difference type, value type and iterator category, respectively. In addition, the types

iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer

shall be defined as the iterator's reference and pointer types, that is, for an iterator object a, the same type as the type of *a and a->, respectively. In the case of an output iterator, the types

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer

may be defined as void.

The template iterator_traits<Iterator> is defined as

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

It is specialized for pointers as

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

and for pointers to const as

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

Note: If there is an additional pointer type  __far such that the difference of two  __far is of type long, an implementation may define

  template<class T> struct iterator_traits<T __far*> {
    typedef long difference_type;
    typedef T value_type;
    typedef T __far* pointer;
    typedef T __far& reference;
    typedef random_access_iterator_tag iterator_category;
  };

 — end note ]

Example: To implement a generic reverse function, a C++ program can do the following:

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) {
  typename iterator_traits<BidirectionalIterator>::difference_type n =
    distance(first, last);
  --n;
  while(n > 0) {
    typename iterator_traits<BidirectionalIterator>::value_type
     tmp = *first;
    *first++ = *--last;
    *last = tmp;
    n -= 2;
  }
}

 — end example ]