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.