Effective C++ item 47: Use Traits Classes For Information About Types

If you want to write a function advance to do iterator arithmetic, how do you implement it?

template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d);

If you have no idea what this is about, let’s first review STL iterator categories. There are five categories of iterators, corresponding to the operations they support.

• Input iterators can move only forward, can move only one step at a time, can only read what they point to, and can read what they’re pointing to only once. They’re modeled on the read pointer into an input file; the C++ library’s istream_iterators are representative of this category.
• Output iterators are analogous, but for output: they move only forward, move only one step at a time, can only write what they point to, and can write it only once. They’re modeled on the write pointer into an output file; ostream_iterators epitomize this category.
• Forward iterators can do everything input and output iterators can do, plus they can read or write what they point to more than once. This makes them viable for multi-pass algorithms. The STL offers no singly linked list, but some libraries offer one (usually called slist), and iterators into such containers are forward iterators. Iterators into TR1’s hashed containers (see Item 54) may also be in the forward category.
• Bidirectional iterators add to forward iterators the ability to move backward as well as forward. Iterators for the STL’s list are in this category, as are iterators for set, multiset, map, and multimap.
• Random access iterators add to bidirectional iterators the ability to perform “iterator arithmetic,” i.e., to jump forward or backward an arbitrary distance in constant time. Such arithmetic is analogous to pointer arithmetic, which is not surprising, because random access iterators are modeled on built-in pointers, and built-in pointers can act as random access iterators. Iterators for vector, deque, and string are random access iterators.

With these information, we can write some psudo code about the implementation

template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
    if (iter is a random access iterator) {
        iter += d;
    }
    else {
        if (d >= 0) { while (d--) ++iter; }
        else { while (d++) --iter; }
    }
}

In order to get the type information about iterator, we need help from traits: they allow you to get information about a type during compilation. Traits aren’t a keyword or a predefined construct in C++; they’re a technique and a convention followed by C++ programmers.

The way traits works is by adding typedefs to user-defined classes to identify type information. Let’s first define tags to identify different type of iterators.

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag: public input_iterator_tag {};
struct bidirectional_iterator_tag: public forward_iterator_tag {};
struct random_access_iterator_tag: public bidirectional_iterator_tag {};

And then add these tags as typedef to classes

template <typename T>
class deque {
public:
    class iterator {
    public:
        typedef random_access_iterator_tag iterator_category;
        ...
    }:
    ...
};

template <typename T>
class list {
public:
    class iterator {
    public:
        typedef bidirectional_iterator_tag iterator_category;
        ...
    }:
    ...
};

...

Now you can define a traits class as following

template<typename IterT>
struct iterator_traits {
    typedef typename IterT::iterator_category iterator_category;
    ...
};

By convention, traits are always implemented as structs, and such struct is called traits classes.

Above code is good for user-defined types, but it won’t work for pointers which falls under random access iterator category. To solve this problem, we define a specialized template implementation for pointers.

template<typename IterT>
struct iterator_traits<IterT*>
{
  typedef random_access_iterator_tag iterator_category;
  ...
};

So far, we have implemented the iterator_traits class so that iterator_traits<IterT>::iterator_categor can tell you what’s the type of iterator at compile time. It’s a common practice to create bunch of worker functions to handle different cases depend on type information, and let a master function call these worker functions. So our implementation of advance will look like this:

template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
    doAdvance(iter, d,
              typename iterator_traits<IterT>::iterator_category;
};
template<typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d,
               random_access_iterator_tag)
{
    iter += d;
}
template<typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d,
               bidirectional_iterator_tag)
{
    if (d >= 0) { while (d--) ++iter; }
    else { while (d++) --iter;         }
}
template<typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d,
               input_iterator_tag)
{
    if (d < 0 ) {
        throw std::out_of_range("Negative distance");
    }
    while (d--) ++iter;
}

Putting everything together and use std namespace for all interator types, we get following

#include <iostream>
#include <vector>
#include <list>
#include <unordered_set>

template<typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d,
               std::random_access_iterator_tag)
{
    std::cout << "random_access_iterator_tag\n";
    iter += d;
}

template<typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d,
               std::bidirectional_iterator_tag)
{
    std::cout << "bidirectional_iterator_tag\n";
    if (d >= 0) { while (d--) ++iter; }
    else { while (d++) --iter; }
}

template<typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d,
               std::input_iterator_tag)
{
    std::cout << "input_iterator_tag\n";
    if (d < 0 ) {
        throw std::out_of_range("Negative distance");
    }
    while (d--) ++iter;
}

template<typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d,
               std::output_iterator_tag)
{
    std::cout << "output_iterator_tag\n";
    if (d < 0 ) {
        throw std::out_of_range("Negative distance");
    }
    while (d--) ++iter;
}

template<typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d,
               std::forward_iterator_tag)
{
    std::cout << "forward_iterator_tag\n";
    if (d < 0 ) {
        throw std::out_of_range("Negative distance");
    }
    while (d--) ++iter;
}

template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
    std::cout << "---advance---\n";
    doAdvance(iter, d,
              typename std::iterator_traits<IterT>::iterator_category());
};

int main() {

    std::vector<int> intVector;
    std::vector<int>::const_iterator itVector = intVector.begin();
    advance(itVector, 0);

    int* intPtr = NULL;
    advance(intPtr, 0);

    std::list<int> intList;
    std::list<int>::const_iterator itList = intList.begin();
    advance(itList, 0);

    std::unordered_set<int> intSet;
    std::unordered_set<int>::const_iterator itSet = intSet.begin();
    advance(itSet, 0);

    std::ostream_iterator<int> otIS(std::cout, " ");
    advance(otIS, 0);

    std::istream_iterator<int> itIS;
    advance(itIS, 0);

    return 0;
}

/* output
---advance---
random_access_iterator_tag
---advance---
random_access_iterator_tag
---advance---
bidirectional_iterator_tag
---advance---
forward_iterator_tag
---advance---
output_iterator_tag
---advance---
input_iterator_tag
*/

Reference:
“Effective C++” Third Edition by Scott Meyers.