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 SGI Documentation.

• Trivial Iterator
• 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

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 3

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 4

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 5

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 6

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

Answer 7

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 8

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' seperately 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, loosing 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 evaluaton, sorting, etc.

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