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

Asked 2008-09-11T11:50:24.490

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?

Edit Report

2 Answers

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.

answered 2008-09-11T12:05:12.083

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 itera

answered 2008-10-02T08:58:34.707

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

2 Answers

Your Answer