定义我自己的容器的迭代器 [英] Defining iterator of my own container

问题描述

我对一些关于定义自己的迭代器的概念感到困惑：

I am confused with some concepts about defining my own iterator:

从这里： http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-iterator-define.html ，这似乎建议使用定义运算符的内部迭代器类。许多其他继承基类 iterator 来重新定义运算符。

From this: http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-iterator-define.html, which seems to suggest using inner iterator class which defines the operators. Many others inherit the base class iterator to redefine the operators.

我很困惑应该使用哪些方法。为什么会有

I am quite confused about which methods should be used. Why is there

typedef ptrdiff_t difference_type;

例如，在容器类定义的开头？

for example, at the beginning of the definition of container class?

非常感谢！

推荐答案

关于什么是STL容器的C ++规范要求任何STL容器类型有几个不同的字段可用。有些像 begin（）和 end（）是函数，而其他类似 iterator 是类型。这些限制也适用于迭代器。这允许C ++模板函数内省它们的参数类型来查找更多的属性。例如，所有STL迭代器类型必须定义一个 iterator_category 字段，其中包含编码其功能的类型。这样，STL算法可以具有基于它们接受的迭代器的功率的不同功能的不同实现。类示例是 distance 函数，它接受两个迭代器并返回它们之间的空格数。如果输入是低的 ForwardIterator 或 BidirectionalIterator ，通过前进迭代器并计算需要多少步，其在O（n）中运行。如果输入是 RandomAccessIterator ，那么迭代器可以被减去以获得O（1）中的结果。

The C++ specification on what exactly an STL container is mandates that any STL container type have several different fields available. Some, like begin() and end(), are functions, while others, like iterator, are types. These restrictions also apply to iterators. This allows C++ template functions to introspect on their types of their arguments to look up more properties. For example, all STL iterator types must define an iterator_category field containing a type encoding their capabilities. This way, the STL algorithms can have different implementations of different functions based on the power of the iterators they accept. A class example is the distance function, which takes two iterators and returns the number of spaces between them. If the input is a lowly ForwardIterator or BidirectionalIterator this works by marching the iterators forward and counting how many steps were took, which runs in O(n). If the input is a RandomAccessIterator, then the iterators can just be subtracted to get the result in O(1).

幸运的是，通常不需要显式列出所有typedef。在< iterator> 头中有一个名为 iterator 的实用程序类型，它参数化了许多不同的参数。如果您定义一个自定义的迭代器类型，您可以继承 iterator 以自动导入所有这些信息。

Fortunately, you usually don't have to explicitly list all the typedefs. There's a utility type in the <iterator> header called iterator that's parameterized over a lot of different arguments. If you define a custom iterator type, you can inherit from iterator to import all of this information automatically. It's essentially a faster way of having all the typedefs in place.

对于你需要重载的操作符来说，这是一个更快捷的方法来处理所有 typedef ，至少需要得到 ++ （前缀和后缀）， == ，！= ， * （指针解引用）和 - > 所有迭代器类型支持这一点。对于双向迭代器或更高版本，您还应该具有 - 定义（前缀和后缀）。最后，对于随机访问迭代器，您应该支持 [] ， + ， + = ， - （备份多个步骤并减去两个迭代器）， - = code>< ，> ，< = code>> = 。

As for what operators you need to overload, at a bare minimum you need to get ++ (prefix and postfix), ==, !=, * (pointer dereference), and -> defined. All iterator types support this. For bidirectional iterators or higher, you should also have -- defined (prefix and postfix). Finally, for random-access iterators, you should support [], +, +=, - (back up many steps and subtract two iterators), -=, <, >, <=, and >=.

希望这有助！

这篇关于定义我自己的容器的迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！