What is the difference between iterators in Java and C++?

Question

How is the implementation of Iterator in Java different from that in C++?

Answer 1

C++ doesn't specify how iterators are implemented. It does however specify their interface and the minimal behaviour they must provide in order to work with other Standard Library components.

For example, for input iterators, the Standard specifies that an iterator must be dereferenceable via the * operator. It does not however specify how that operator is to be implemented.

Answer 2

implementations are defined entirely by standard library vendors/JRE vendors in C++/Java respectively. They aree free to implement them however they want, as long as their behaviour ocnforms to the respective standards.

Answer 3

C++ iterators (STL) try to mimic pointer syntax as much as possible, through operator overloading.

The standard specification define the various iterator concepts (like forward, bidirectional, random access, input, output). Each concept should match a specific interface (e.g. ++ operator for forward iterator to go to the next element in sequence, -- for bidirectional, +, += for random access, etc).

Answer 4

In the current C++ (97) standard library (in particular the portion formerly known as STL) defines a form of iterators that are very close to C pointers (including arithmetic). As such they just point somewhere. To be useful, you generally need two pointers so that you can iterate between them. I understand C++0x introduces ranges which act more like Java iterators.

Java introduced the Iterator (and ListIterator) interface in 1.2, largely taking over from the more verbose Enumerable. Java has no pointer arithmetic, so there is no need to behave like a pointer. They have a hasNext method to see if they have go to the end, instead of requiring two iterators. The downside is that they are less flexible. The system requires methods as subList rather than iterating between two iterators are specific points in the containing list.

A general difference in style is that whereas C++ use "static polymorphism" through templates, Java uses interfaces and the common dynamic polymorphism.

The concept of iterators is to provide the glue to allow separation of "algorithm" (really control flow) and data container. Both approaches do that reasonably well. In ideal situations "normal" code should barely see iterators.

Answer 5

In C++, you see people passing around iterators all the time. C++ iterators "point" to a specific element of a container. You can dereference an iterator to get the element (and you can do this over and over). You can erase the element that an iterator refers to efficiently. You can also make copies of an iterator (either by assigning to another variable, or passing an iterator by value to a function) to keep track of multiple places at the same time. Iterators in C++ can become "invalidated" by certain operations on the container, depending on the container. When an iterator becomes invalidated (the rules of which might be complex), operations with the iterator have undefined behavior, and may (inconsistently) crash your program or return incorrect results; although in some data structures (e.g. std::list), iterators remain valid through most modifications of the container.

In Java, you don't see that kind of usage. An Iterator in Java points "between" two elements, rather than "at" an element. The only way you get elements with an iterator is to move it forwards to get the element you moved over. Of course that changes the state of the iterator, and you can't go back; unless you have a ListIterator in which case you can move both forwards and backwards (but it is still annoying to have to move forwards and backwards just to remain still). You can't copy an iterator, because the interface does not expose a public copy method; so for example, you can't just pass a marker of a specific location to a function, without giving that function a reference to the same iterator that you have, and thereby allowing them to change the state of your iterator. In Java, an iterator will be invalidated (at least in the standard containers) by any modification of the container except through the iterator's own add() or remove() methods, which is overly conservative (e.g. most modifications on a LinkedList should not affect an iterator). When you try to use an invalidated iterator, it raises ConcurrentModificationException (confusingly named because it has nothing to do with Concurrency) instead of possibly causing undefined behavior, which is good.