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

Question

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

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 limit for the container being traversed.

//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 limit built 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.

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.

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

Answer 1

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).

See the iterators concept in the C++ Documentation:

• 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.

Answer 2

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 behind the last element.

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.

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.

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

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.

Answer 3

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 and C# iterators can't be copied. You can't recover a previous position. The common C++ iterators can.

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.

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

• 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.

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.

Answer 4

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 pair of 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.pdf or 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)

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

Answer 5

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

Answer 6

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.

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).

Answer 7

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.

Answer 8

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.

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.

Answer 9

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.

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.

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