C++ (stl) 和 Java 中的迭代器，在概念上有区别吗？

Iterators in C++ (stl) vs Java, is there a conceptual difference?

提问by JeffV

I'm returning to c++ after being away for a bit and trying to dust off the old melon.

在离开一段时间并试图清除旧瓜后，我将回到 C++。

In Java Iterator is an interface to a container having methods: hasNext(), next()and remove(). The presence of hasNext()means it has the concept of a limitfor the container being traversed.

在 Java 中，Iterator 是一个容器的接口，具有以下方法：hasNext(),next()和remove()。存在hasNext()意味着它具有被遍历容器的限制的概念。

//with an Iterator
Iterator<String> iter = trees.iterator();
while (iter.hasNext()) 
{
    System.out.println(iter.next());
}

In the C++ standard template library, iterators seem to represent a datatype or class the supports the operator++and operator==but has no concept of a limitbuilt in so comparison is required before advancing to the next item. The limit has to checked by the user comparing two iterators in the normal case the second iterator is the container end.

在 C++ 标准模板库中，迭代器似乎表示支持的数据类型或类operator++，operator==但没有内置限制的概念，因此在前进到下一项之前需要进行比较。在正常情况下，用户必须通过比较两个迭代器来检查限制，第二个迭代器是容器端。

vector<int> vec;
vector<int>::iterator iter;

// Add some elements to vector
v.push_back(1);
v.push_back(4);
v.push_back(8);

for (iter= v.begin(); iter != v.end(); iter++)
{
    cout << *i << " "; //Should output 1 4 8
}

The interesting part here is that in C++ a pointer is an iterator to an array. The STL took what was existing and build convention around it.

有趣的是，在 C++ 中，指针是指向数组的迭代器。STL 采用了现有的内容并围绕它建立了约定。

It there any further subtlety to this that I am missing?

我想念的还有什么更微妙的地方吗？

采纳答案by Frank Krueger

Yes, there is a large conceptual difference. C++ utilizes different "classes" of iterators. Some are used for random access (unlike Java), some are used for forward access (like java). While even others are used for writing data (for use with, say, transform).

是的，存在很大的概念差异。C++ 使用不同的迭代器“类”。有些用于随机访问（与 Java 不同），有些用于前向访问（如 java）。甚至其他人也用于写入数据（例如用于transform）。

See the iterators concept in the C++ Documentation:

请参阅C++ 文档中的迭代器概念：

• Input Iterator
• Output Iterator
• Forward Iterator
• Bidirectional Iterator
• Random Access Iterator

• 输入迭代器
• 输出迭代器
• 前向迭代器
• 双向迭代器
• 随机访问迭代器

These are far more interesting and powerful compared to Java/C#'s puny iterators. Hopefully these conventions will be codified using C++0x's Concepts.

与 Java/C# 微不足道的迭代器相比，这些迭代器更有趣也更强大。希望这些约定将使用 C++0x 的Concepts进行编纂。

回答by Konrad Rudolph

Perhaps a bit more theoretical. Mathematically, collections in C++ can be described as a half-open interval of iterators, namely one iterator pointing to the start of the collection and one iterator pointing just behindthe last element.

也许更理论化一点。在数学上，C++ 中的集合可以描述为迭代器的半开区间，即一个迭代器指向集合的开头，一个迭代器指向最后一个元素的后面。

This convention opens up a host of possibilities. The way algorithms work in C++, they can all be applied to subsequences of a larger collection. To make such a thing work in Java, you have to create a wrapper around an existing collection that returns a different iterator.

这个约定开辟了许多可能性。算法在 C++ 中的工作方式，它们都可以应用于更大集合的子序列。要使这样的事情在 Java 中工作，您必须围绕现有集合创建一个包装器，该集合返回不同的迭代器。

Another important aspect of iterators has already been mentioned by Frank. There are different concepts of iterators. Java iterators correspond to C++' input iterators, i.e. they are read-only iterators that can only be incremented one step at a time and can't go backwards.

Frank 已经提到了迭代器的另一个重要方面。迭代器有不同的概念。Java迭代器对应于C++的输入迭代器，即只读迭代器，一次只能递增一步，不能倒退。

On the other extreme, you have C pointers which correspond exactly to C++' concept of a random access iterator.

在另一个极端，您有 C 指针，它们与 C++ 的随机访问迭代器概念完全对应。

All in all, C++ offers a much richer and purer concept that can be applied to a much wider variety of tasks than either C pointers or Java iterators.

总而言之，与 C 指针或 Java 迭代器相比，C++ 提供了更丰富和更纯粹的概念，可以应用于更广泛的任务。

回答by Aaron

As mentioned, Java and C# iterators describe an intermixed position(state)-and-range(value), while C++ iterators separate the concepts of position and range. C++ iterators represent 'where am I now' separately from 'where can I go?'.

如前所述，Java 和 C# 迭代器描述了一个混合的位置（状态）和范围（值），而 C++ 迭代器将位置和范围的概念分开。C++ 迭代器分别代表“我现在在哪里”和“我可以去哪里？”。

Java and C# iterators can't be copied. You can't recover a previous position. The common C++ iterators can.

无法复制 Java 和 C# 迭代器。您无法恢复以前的位置。常见的 C++ 迭代器可以。

Consider this example:

考虑这个例子：

// for each element in vec
for(iter a = vec.begin(); a != vec.end(); ++a){
  // critical step!  We will revisit 'a' later.
  iter cur = a; 
  unsigned i = 0;
  // print 3 elements
  for(; cur != vec.end() && i < 3; ++cur, ++i){
      cout << *cur << " ";
  }
  cout << "\n";
}

Click the above link to see program output.

单击上面的链接查看程序输出。

This rather silly loop goes through a sequence (using forward iterator semantics only), printing each contiguous subsequence of 3 elements exactly once (and a couple shorter subsequences at the end). But supposing N elements, and M elements per line instead of 3, this algorithm would still be O(N*M) iterator increments, and O(1) space.

这个相当愚蠢的循环遍历一个序列（仅使用前向迭代器语义），将 3 个元素的每个连续子序列精确打印一次（最后打印几个较短的子序列）。但是假设 N 个元素，每行 M 个元素而不是 3 个，这个算法仍然是 O(N*M) 迭代器增量和 O(1) 空间。

The Java style iterators lack the ability to store position independently. You will either

Java 风格的迭代器缺乏独立存储位置的能力。你要么

• lose O(1) space, using (for example) an array of size M to store history as you iterate
• will need to traverse the list N times, making O(N^2+N*M) time
• or use a concrete Array type with GetAt member function, losing genericism and the ability to use linked list container types.

• 丢失 O(1) 空间，使用（例如）大小为 M 的数组在迭代时存储历史记录
• 将需要遍历列表 N 次，使 O(N^2+N*M) 时间
• 或者使用具有 GetAt 成员函数的具体 Array 类型，失去通用性和使用链表容器类型的能力。

Since only forward iteration mechanics were used in this example, i was able to swap in a list with no problems. This is critical to authoring generic algorithms, such as search, delayed initialization and evaluation, sorting, etc.

由于只有向前迭代机制，在此例子中，我能交换与名单没有问题。这对于编写通用算法至关重要，例如搜索、延迟初始化和评估、排序等。

The inability to retain state corresponds most closely to the C++ STL input iterator, on which very few algorithms are built.

无法保持状态最接近于 C++ STL 输入迭代器，在其上构建的算法很少。

回答by Anthony Williams

A pointer to an array element is indeed an iterator into the array.

指向数组元素的指针实际上是数组的迭代器。

As you say, in Java, an iterator has more knowledge of the underlying container than in C++. C++ iterators are general, and a pairof iterators can denote any range: this can be a sub-range of a container, a range over multiple containers (see http://www.justsoftwaresolutions.co.uk/articles/pair_iterators.pdfor http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/zip_iterator.html) or even a range of numbers (see http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/counting_iterator.html)

正如您所说，在 Java 中，迭代器比在 C++ 中拥有更多的底层容器知识。C++ 迭代器是通用的，一对迭代器可以表示任何范围：这可以是一个容器的子范围，一个跨多个容器的范围（参见http://www.justsoftwaresolutions.co.uk/articles/pair_iterators.pdf或http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/zip_iterator.html）甚至一系列数字（参见http://www.boost.org/doc/libs/1_36_0 /libs/iterator/doc/counting_iterator.html)

The iterator categories identify what you can and can't do with a given iterator.

迭代器类别标识您可以使用给定的迭代器做什么和不能做什么。

回答by Douglas Leeder

To me the fundamental difference is that Java Iterators point between items, whereas C++ STL iterators point at items.

对我来说，根本区别在于 Java 迭代器指向项之间，而 C++ STL 迭代器指向项。

回答by DrPizza

C++ iterators are a generalization of the pointer concept; they make it applicable to a wider range of situations. It means that they can be used to do such things as define arbitrary ranges.

C++ 迭代器是指针概念的概括；它们使其适用于更广泛的情况。这意味着它们可用于执行诸如定义任意范围之类的事情。

Java iterators are relatively dumb enumerators (though not so bad as C#'s; at least Java has ListIterator and can be used to mutate the collection).

Java 迭代器是相对笨拙的枚举器（虽然不像 C# 那样糟糕；至少 Java 有 ListIterator 并且可以用来改变集合）。

回答by Neo M Hacker

There are plenty of good answers about the differences, but I felt the thing that annoys me the most with Java iterators wasn't emphasized--You can't read the current value multiple times. This is really useful in a lot of scenarios, especially when you are merging iterators.

关于差异有很多很好的答案，但我觉得 Java 迭代器最让我烦恼的事情没有被强调——你不能多次读取当前值。这在很多场景中非常有用，尤其是在合并迭代器时。

In c++, you have a method to advance the iterator and to read the current value. Reading its value doesn't advance the iteration; so you can read it multiple times. This is not possible with Java iterators, and I end up creating wrappers that do this.

在 C++ 中，您有一个方法来推进迭代器并读取当前值。读取它的值不会推进迭代；所以你可以多次阅读它。这对于 Java 迭代器是不可能的，我最终创建了执行此操作的包装器。

A side note: one easy way to create a wrapper is to use an existing one--PeekingIteratorfrom Guava.

旁注：创建包装器的一种简单方法是使用现有的包装器——来自 Guava 的PeekingIterator。

回答by Marcus Downing

Iterators are only equivalent to pointers in the trivial case of iterating over the contents of an array in sequence. An iterator could be supplying objects from any number of other sources: from a database, from a file, from the network, from some other calculation, etc.

在按顺序迭代数组内容的微不足道的情况下，迭代器仅等效于指针。迭代器可以从任意数量的其他来源提供对象：来自数据库、文件、网络、其他一些计算等。

回答by Tom Hawtin - tackline

C++ library (the part formerly known as STL) iterators are designed to be compatible with pointers. Java, without pointer arithmetic, had the freedom to be more programmer-friendly.

C++ 库（以前称为 STL 的部分）迭代器旨在与指针兼容。Java，没有指针算法，可以自由地对程序员更友好。

In C++ you end up having to use a pair of iterators. In Java you either use an iterator or a collection. Iterators are supposed to be the glue between algorithm and data structure. Code written for 1.5+ rarely need mention iterators, unless it is implementing a particular algorithm or data structure (which the vary majority of programmers have no need to do). As Java goes for dynamic polymorphism subsets and the like are much easier to handle.

在 C++ 中，您最终不得不使用一对迭代器。在 Java 中，您可以使用迭代器或集合。迭代器应该是算法和数据结构之间的粘合剂。为 1.5+ 编写的代码很少需要提及迭代器，除非它正在实现特定的算法或数据结构（大多数程序员不需要这样做）。由于 Java 使用动态多态性子集等，因此更容易处理。