What is the purpose of the iterator_category typedef?

Question

I tried to understand iterator implementation, and while playing around with the source, I saw this statement:

typedef output_iterator_tag iterator_category;

I don't understand how this typedef work within the class? What's the side effect does it provide? Can anyone walk me through this?

Answer 1

You need to read up on generic programming because you're not likely to get this answer.

"Output Iterator" is a concept that certain iterators match. Each iterator that is a realization of this concept has certain functionality associated with it. It's sort of like inheritance, but it isn't.

C++ doesn't have any such anything that represents concepts (was a proposed addition to C++0x but failed to make it). That being the case, we need various template constructs to allow us to associate a "tag" with an iterator type. By associating the output_iterator_tag type with an iterator we're claiming that our iterator type realizes the OutputIterator concept.

This becomes very important when you're trying to write algorithms that are as optimized as possible and also generic. For example, performing a sort with an iterator that can be incremented or decremented by an arbitrary value (other than 1 in other words) is more efficient than one that doesn't have this capability. Furthermore, in order to get a new iterator that's X distance from another can require different operations depending on the capabilities of the iterator. To write such an algorithm you use "tag dispatching". To explain this more fully, here's an implementation (untested) of std::advance that works both with iterators that have a += operator and ones that only have a ++ operator and is as fast as possible with both versions.

template < typename RandomAccessIterator >
RandomAccessIterator advance( RandomAccessIterator it
                            , int amount
                            , random_access_iterator_tag) 
{ return it + amount; }

template < typename ForwardIterator >
ForwardIterator advance(ForwardIterator it, int amount, forward_iterator_tag)
{
  for (;amount; --amount) ++it;
  return it;
}

template < typename Iterator >
Iterator advance(Iterator it, int amount)
{
  typedef typename std::iterator_traits<Iterator>::iterator_tag tag;
  advance(it, amount, tag());
}

That's from memory so it's probably riddled with bugs (probably have a bunch of types wrong even)...but that's the idea. The iterator tags are types that are empty and also inherit from each other in exactly the same way as the concepts refine each other. For instance, a random access iterator IS a forward iterator. Thus random_access_iterator_tag is a derivative of forward_iterator_tag. Because of function overload resolution rules passing a random_access_iterator_tag to the function resolves to that version of the function rather than the forward_iterator_tag one.

Again, go read up on generic programming. It's essential to utilizing the full power of C++.

Oh, and finally... The typedef is there in the iterator's class definition because it's a nice, convenient place to put it. A default iterator_traits can the look for it there. You'll want to use iterator_traits rather than that definition though because raw pointers are iterators too and they can't have internal typedefs.