C ++中的迭代器类别如何工作？ [英] How does iterator category in C++ work?

问题描述

我尝试了解迭代器的实现，在使用源代码时，我看到了这个语句：

I tried to understand iterator implementation, and while playing around with the source, I saw this statement:

typedef output_iterator_tag iterator_category;

我不明白这个typedef在类中是如何工作的？它提供了什么副作用？

I don't understand how this typedef work within the class? What's the side effect does it provide? Can anyone walk me through this?

推荐答案

你需要读一般的编程，因为你不太可能得到这个答案。

You need to read up on generic programming because you're not likely to get this answer.

输出迭代器是某些迭代器匹配的概念。每个迭代器是这个概念的实现具有与其相关联的某些功能。它类似于继承，但它不是。

"Output Iterator" is a concept that certain iterators match. Each iterator that is a realization of this concept has certain functionality associated with it. It's sort of like inheritance, but it isn't.

C ++没有任何代表概念的任何东西（是一个建议添加到C ++ 0x但失败使它）。在这种情况下，我们需要各种模板构造，以允许我们将一个标签与迭代器类型相关联。通过将output_iterator_tag类型与迭代器关联，我们声明我们的迭代器类型实现了OutputIterator的概念。

C++ doesn't have any such anything that represents concepts (was a proposed addition to C++0x but failed to make it). That being the case, we need various template constructs to allow us to associate a "tag" with an iterator type. By associating the output_iterator_tag type with an iterator we're claiming that our iterator type realizes the OutputIterator concept.

当你试图编写的算法尽可能优化并且通用。例如，使用可以递增或递减任意值（换句话说，除了1）的迭代器执行排序比不具有此功能的迭代器更有效。此外，为了得到一个新的迭代器，X距离另一个可能需要不同的操作，这取决于迭代器的能力。要编写这样的算法，您可以使用tag dispatching。为了更全面地解释这一点，下面是一个std :: advance的实现（未测试），它同时具有+ =运算符和只有++运算符的迭代器，并且两个版本都尽可能快。

This becomes very important when you're trying to write algorithms that are as optimized as possible and also generic. For example, performing a sort with an iterator that can be incremented or decremented by an arbitrary value (other than 1 in other words) is more efficient than one that doesn't have this capability. Furthermore, in order to get a new iterator that's X distance from another can require different operations depending on the capabilities of the iterator. To write such an algorithm you use "tag dispatching". To explain this more fully, here's an implementation (untested) of std::advance that works both with iterators that have a += operator and ones that only have a ++ operator and is as fast as possible with both versions.

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（可能有一堆类型错误甚至）...但这是想法。迭代器标签是空的类型，并且彼此之间的继承方式与概念彼此完善的方式完全相同。例如，随机接入迭代器是前向迭代器。因此，random_access_iterator_tag是forward_iterator_tag的导数。由于函数重载解析规则将random_access_iterator_tag传递给函数，而不是forward_iterator_tag函数，因此函数将解析为该函数的版本。

That's from memory so it's probably riddled with bugs (probably have a bunch of types wrong even)...but that's the idea. The iterator tags are types that are empty and also inherit from each other in exactly the same way as the concepts refine each other. For instance, a random access iterator IS a forward iterator. Thus random_access_iterator_tag is a derivative of forward_iterator_tag. Because of function overload resolution rules passing a random_access_iterator_tag to the function resolves to that version of the function rather than the forward_iterator_tag one.

再次阅读泛型编程。使用C ++的全部功能是至关重要的。

Again, go read up on generic programming. It's essential to utilizing the full power of C++.

哦，最后... typedef在迭代器的类定义中，因为它是一个很好的，方便的地方它。默认的iterator_traits可以找到它。你会想使用iterator_traits而不是那个定义，因为原始指针也是迭代器，他们不能有内部typedef。

Oh, and finally... The typedef is there in the iterator's class definition because it's a nice, convenient place to put it. A default iterator_traits can the look for it there. You'll want to use iterator_traits rather than that definition though because raw pointers are iterators too and they can't have internal typedefs.

这篇关于C ++中的迭代器类别如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！