C++中的迭代器类如何工作？

Question

我试图理解迭代器的实现,在玩源时,我看到了这样的说法:

typedef output_iterator_tag iterator_category;

我不明白这个typedef是如何在课堂上工作的？它提供的副作用是什么？谁能跟我走过这个？

Answer 1

您需要阅读泛型编程,因为您不太可能得到这个答案.

"输出迭代器"是某些迭代器匹配的概念.作为此概念的实现的每个迭代器都具有与之相关的某些功能.这有点像继承,但事实并非如此.

C++没有任何代表概念的东西(是C++ 0x的一个新增功能,但未能成功).在这种情况下,我们需要各种模板结构,以允许我们将"标记"与迭代器类型相关联.通过将output_iterator_tag类型与迭代器相关联,我们声称我们的迭代器类型实现了OutputIterator概念.

当您尝试编写尽可能优化且通用的算法时,这变得非常重要.例如,使用可以递增或递减任意值(换句话说除了1)的迭代器执行排序比没有此功能的迭代器更有效.此外,为了获得一个新的迭代器,与另一个迭代器的X距离可能需要不同的操作,具体取决于迭代器的功能.要编写这样的算法,请使用"标签调度".为了更全面地解释这一点,这里是一个std :: advance的实现(未经测试),它既可以使用具有+ =运算符的迭代器,也可以使用仅具有++运算符且两个版本尽可能快的迭代器.

template < typename RandomAccessIterator >
RandomAccessIterator advance( RandomAccessIterator it
                            , int amount
                            , random_access_iterator_tag) 
{ return it + amount; }

template < typename ForwardIterator >
ForwardIterator advance(ForwardIterator it, int amount, forward_iterator_tag)
{
  for (;amount; --amount) ++it;
  return it;
}

template < typename Iterator >
Iterator advance(Iterator it, int amount)
{
  typedef typename std::iterator_traits<Iterator>::iterator_tag tag;
  advance(it, amount, tag());
}

这是来自内存所以它可能充满了错误(甚至可能有一堆类型错误)......但这就是想法.迭代器标记是空的类型,并且彼此之间的继承方式与概念相互完善的方式完全相同.例如,随机访问迭代器是一个前向迭代器.因此,random_access_iterator_tag是forward_iterator_tag的衍生物.由于函数重载解析规则将random_access_iterator_tag传递给函数解析为该函数的版本而不是forward_iterator_tag.

再次,阅读泛型编程.利用C++的全部功能至关重要.

哦,最后......在iterator的类定义中有typedef,因为它是一个很好,方便的地方.默认的iterator_traits可以在那里查找它.您可能希望使用iterator_traits而不是该定义,因为原始指针也是迭代器,并且它们不能具有内部typedef.