c++ - std::forward_iterator_tag 的作用是什么？

Question

在分析一个应用程序时，我碰到了 gcc 4.7.1 附带的那部分标准库实现。它是 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)
  {
     …
  }

我注意到函数签名的最后一个参数只是一个标记，我开始想知道它为什么会在这里。快速浏览 this page表明 std::forward_iterator_tag 是一个空结构。它在这里的作用是什么？显然它对函数没有用，它可能会浪费一个寄存器，或者堆栈上的一些空间。那为什么？

Answer 1

简而言之:标签是为了重载，为了优化。

以一个简单的advance为例，你可以设计:

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

但是它的复杂度为 O(n)，当您有一个 random_access_iterator 时，这是 Not Acceptable 。所以你可以这样改变你的设计:

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);
}

然而，要使用的函数的版本是在运行时决定的，所以我们尽量让编译器在编译时决定选择哪种方法。所以我们给迭代器标签。有五个标签:

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 {};

现在你可以这样做了:

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());
}