What is the role of std::forward_iterator_tag?

Question

Upon profiling an application, I bumped into that piece of the standard library implementation shipped with gcc 4.7.1. It is include/g++-v4/bits/vector.tcc:

template<typename _Tp, typename _Alloc>
template<typename _ForwardIterator>
  void
  vector<_Tp, _Alloc>::
    _M_range_insert(iterator __position, _ForwardIterator __first,
          _ForwardIterator __last, std::forward_iterator_tag)
  {
     …
  }

I noticed that the last argument of the function signature is just a tag, and I started wondering why it was here. A quick look at this page shows that std::forward_iterator_tag is an empty structure. What is its role here? Clearly it's useless to the function, and it might waste a register, or some space on the stack. So why?

Answer 1

In a nutshell: Tags are for overloading, for optimization.

Take a simple advance as example, you might design:

template<class II, class D>
void advance(II& i, D n){
    while( n-- ) ++i;
}

However it have O(n) complexity, which is not acceptable when you have a random_access_iterator. So you may change your design like this:

template<class II, class D>
void advance_II(II& i, D n){
    while( n-- ) ++i;
}

template<class RAI, class D>
void advance_RAI(RAI& i, D n){
    i += n;
}

template<class II, class D>
void advance(II& i, D n){
    if(is_random_access_iterator(i)) // not yet designed
        advance_RAI(i, n);
    else
        advance_II(i, n);
}

However the version of function to use is decided at run-time, so we try to let compiler decided which method to choose at compile-time. So we give iterators tags. There are five tags:

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

Now you can do this:

template<class II, class D>
void __advance(II& i, D n, input_iterator_tag){
    while( n-- ) ++i;
}

template<class RAI, class D>
void __advance(RAI& i, D n, random_access_iterator_tag){
    i += n;
}

template<class II, class D>
void advance(II& i, D n){
    __advance(i, n, iterator_traits<II>::iterator_category());
}

Answer 2

To distinguish between different _M_range_insert overloads.

This reference seems a little better, and has an example on how the tag structures can be used.

Answer 3

At the risk of quoting your link..

Empty class to identify the category of an iterator as a forward iterator:

It is used as a tag to identify the kind of iterator, so that the functions, here _M_range_insert can act appropriately. Since it is a type name, it can be used to trigger different overloads.

In my impl, I have

void _Insert(const_iterator _Where, _Iter _First, _Iter _Last,
            _Int_iterator_tag)

void _Insert(const_iterator _Where, _Iter _First, _Iter _Last,
            input_iterator_tag)

void _Insert(const_iterator _Where, _Iter _First, _Iter _Last, 
            forward_iterator_tag)

Among other overloads.

Answer 4

It's a part of template metaprogramming machinery and it is used to choose appropriate overload based on traits of arguments, so for example if you have random access iterators you can take advantage of that and check distance between them and reserve before insert. On the other hand if you only have forward iterators checking distance would be O(n), so you don't do it, just push back, which can result in multiple relocations and therefore be slower. Also compiler will optimize out these empty structs, so there is no runtime penalty.

Answer 5

There are several overloads for insertion into a vector, some of them are duplicated for the constructors. Two of those overloads have a conflict if the vector elements are of integral type:

iterator insert( const_iterator pos, size_type count, const T& value );

template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last );

If you have a vector<int> and call vec.insert(vec.bgein(), 5, 4), you surely mean to insert 5 times the value 4. But overload resolution will see the template and call that one, deducing InputIt to be int.

To solve that problem and some other behavioral stuff, the implementors of the standard library have invented some traits and a bunch of tag classes. The traits is a template metafunction that will give three different tags, like Karthik T said in his answer:

• _Int_iterator_tag if InputIt is of integral type
• forward_iterator_tag if InputIt is a forward iterator (that includes random access iterators)
• input_iterator_tag if InputIt is an iterator type that is not a forward iterator

You will then have a bunch of overloads of _M_range_insert, taking the different tag types as additional parameters, each doing the Right Thing, meaning

• The overload for the Int-Tag will redirect to the first non-templated overload of insert (or its implementation)
• The overload for forward-iterators calls reserve(std::distance(first,last)) and copies the elements from the iterator range after that
• The overload for plain input iterators just copies the elements, maybe causing multiple reallocations. It cannot call reserve, because the input iterators can be evaluated only once (thing e.g. of istream iterators)

The templated insert method will then look conceptually like this:

template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last )
{
  return _M_range_insert(pos, first, last, InsertIteratorTraits<InputIt>::tag_type());
}