8

在分析应用程序时，我碰到了 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是一个空结构。它在这里的作用是什么？显然它对函数没有用，而且它可能会浪费一个寄存器，或者堆栈上的一些空间。所以为什么？

4

5 回答 5

11

简而言之：标签用于重载，用于优化。

举个简单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());
}
于 2013-07-02T10:38:29.183 回答
6

区分不同的_M_range_insert重载。

这个参考似乎好一点，并且有一个关于如何使用标签结构的例子。

于 2013-07-02T10:17:43.013 回答
4

冒着引用您的链接的风险..

将迭代器的类别标识为前向迭代器的空类：

它用作标识迭代器种类的标记，以便函数在这里_M_range_insert可以适当地执行。由于是类型名，可以用来触发不同的重载。

在我的暗示中，我有

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)

在其他重载中。

于 2013-07-02T10:16:45.457 回答
1

它是模板元编程机制的一部分，它用于根据参数的特征选择适当的重载，因此例如，如果您有随机访问迭代器，您可以利用它并检查它们之间的距离并在插入之前保留。另一方面，如果您只有前向迭代器检查距离将是 O(n)，所以您不这样做，只需向后推，这可能导致多次重定位，因此速度较慢。编译器还将优化这些空结构，因此没有运行时损失。

于 2013-07-02T10:23:00.037 回答
1

有几个重载可以插入到向量中，其中一些对于构造函数是重复的。如果向量元素是整数类型，则其中两个重载会发生冲突：

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

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

如果你有一个vector<int>and 调用vec.insert(vec.bgein(), 5, 4)，你肯定是要插入值 4 的 5 倍。但是重载决议会看到模板并调用那个模板，推断InputIt为 be int。

为了解决这个问题和其他一些行为问题，标准库的实现者发明了一些特征和一堆标记类。特征是一个模板元函数，它将给出三个不同的标签，就像 Karthik T 在他的回答中所说：

  • _Int_iterator_tagifInputIt是整型
  • forward_iterator_tagifInputIt是前向迭代器（包括随机访问迭代器）
  • input_iterator_tagifInputIt是不是前向迭代器的迭代器类型

然后，您将有一堆重载_M_range_insert，将不同的标签类型作为附加参数，每个都做正确的事情，这意味着

  • insertInt-Tag 的重载将重定向到（或其实现）的第一个非模板化重载
  • 前向迭代器的重载调用reserve(std::distance(first,last))并复制迭代器范围内的元素
  • 普通输入迭代器的重载只是复制元素，可能会导致多次重新分配。它不能调用reserve，因为输入迭代器只能被评估一次（例如 istream 迭代器）

然后，模板化的插入方法在概念上将如下所示：

template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last )
{
  return _M_range_insert(pos, first, last, InsertIteratorTraits<InputIt>::tag_type());
}
于 2013-07-02T11:49:26.117 回答