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)
  {
     …
  }

我注意到函数签名的最后一个参数只是一个标记,我开始想知道为什么它在这里.快速浏览一下这个页面显示这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.所以你可以改变你的设计:

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

Answer 2

区分不同的_M_range_insert过载.

这个引用看起来好一点,并且有一个关于如何使用标记结构的示例.