Different types of iterators

Question

Are there other types of iterators? Any links that show different types of iterators?

The only one I know is .NET's IEnumerable.

Particularly for C#, but all others are welcomed too.

Answer 1

Wikipedia has an excellent article on iterators:

In computer science, an iterator is an object that allows a programmer to traverse through all the elements of a collection, regardless of its specific implementation. An iterator is sometimes called a cursor, especially within the context of a database.

It also has code examples in the following languages:

• C++
• C# and other .NET languages
• Java
• Ruby
• Python
• PHP

Answer 2

An iterator is a lot of different things in different languages.

An obvious example of something "more than just the C# Iterator" is the C++ iterator, which is basically a marker into a sequence. Unlike the C# equivalent, it does not "know" where the sequence starts or ends, it just knows which element it currently points to, and how to get the next and perhaps previous element.

These iterators are typically used in pairs (denoting begin/end of a sequence), like this:

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5); // create a vector (equivalent to a C# List), and populate it with the numbers 1-5

// create two iterators, pointing to the beginning and end of this vector
std::vector<int>::iterator first = v.begin();
std::vector<int>::iterator last = v.end();

std::copy(first, last, std::ostream_iterator(std::cout)); // copy all elements found between first and last, to the standard output (in the shape of a special output iterator)

or if we were to traverse it manually, we'd do this:

for (vector<int>::iterator cur = v.begin(); cur != v.end(); ++cur) {
  int val = *cur; // get the value pointed to by the iterator
  cout << val; //  print that value to the standard output
}

The effect of this is the same as the std::copy function in the first example, but here you can see how the iterator is actually used to move through the sequence. The interesting thing is that you use a pair of iterators, so instead of having one iterator, with a "HasNext()" "GetCurrent" and "MoveForward" function (or similar), you have two iterators, and the "HasNext" is roughly speaking replaced with an equality test. We test if the iterator we're advancing through the sequence equals the given end iterator. If it does, we know we've reached the end of the sequence.

These iterators are further subdivided into different types with different capabilities. A vector's iterator belongs to the random access iterator category, which means that from any iterator, you can get to anywhere else in the sequence, in a single constant-time operation. For example, in the above example, I can get from the beginning of the vector to the end by doing this:

std::vector<int>::iterator last = v.begin() + 5; // advance 5 elements from begin

i can also go backwards

std::vector<int>::iterator first= v.end() - 5; // go 5 elements back from the end

Then there are bidirectional iterators, which still allow you to go both forward and backward in the sequence, but only one element at a time (so instead of + and - operators, you only have ++ and --). These are used for linked lists, for example. There is no way to skip, say, 5 elements in constant time in a linked list, so the linked list implementation only exposes bidirectional iterators, not random-access.

And this can be further narrowed down to a forward iterator (which only has the ++ operator. The ostream_iterator above is an example of this. Because it wraps a stream, there is no way to move backwards with such an iterator.

Most other languages implement iterators much like those found in C# though. C++ is the only one I know of which implements something significantly more complex (and powerful)

In particular, because C++ iterators are decoupled from the containers they point into, you can easily represent sub-ranges (for example, to denote the first three elements in the vector above, I could use the iterator pair v.begin(), v.begin() + 3. Another example is the find function, which searches in an iterator range, and returns an iterator pointing to the found element:

std::vector<int>::iterator result = std::find(v.begin(), v.end(), 3);

This example says to search the entire vector range for the first element with the value 3. It returns an iterator pointing to that element (or the end-iterator if no result was found)

This iterator can be paired with the ones we already had, so for example, we can now search in the sub-range between the search result and the end of the sequence:

std::vector<int>::iterator result2 = std::find(result + 1, v.end(), 3);

So the above will search for the next element with value 3, starting at one past the first search result, and ending with the end of the sequence. Of course, no element will be found then, so it returns v.end().

Answer 3

An Iterator is actually the name of a design pattern created by the Gang of Four. Design patterns are just guidelines and as such each language implements theirs slightly differently.

But in each language you are stuck with their implementation for built-in objects, and you can create your own implementation for your own objects.