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

EN

你需要阅读泛型编程的知识，因为你不太可能得到这个答案。

“输出迭代器”是某些迭代器匹配的概念。作为这个概念的实现的每个迭代器都有与之相关的某些功能。这有点像继承，但它不是。

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

这是来自内存的，所以它可能充满了bug(甚至可能有一堆错误的类型)...but，这就是我们的想法。迭代器标记是空的类型，它们也是以完全相同的方式相互继承的，就像概念相互细化一样。例如，随机访问迭代器就是前向迭代器。因此，random_access_iterator_tag是forward_iterator_tag的派生。由于函数的重载，将random_access_iterator_tag传递给函数的解析规则将解析为该版本的函数，而不是forward_iterator_tag版本。

再说一次，去阅读泛型编程。要充分利用C++的强大功能，这一点至关重要。

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