Do we still need Iterator design pattern? [closed]

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be suppor开发者_Go百科ted by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 9 years ago.

I am learning the design patterns, and I found Iterator. Do we still need to use it?

Since we have collection, I am confused why we still need the Iterator Design Pattern.

---

IEnumerator<T> is an iterator and IEnumerable<T> creates them. Almost all collections implement IEnumerable<T>.

It's at the heart of Linq-To-Objects which is one of the core features of C# 3. So iterators are very important in modern C#.

C# 3 also introduced a special language feature allowing you to easily implement an iterator using the yield return syntax.

foreach is based on iterators too.

---

Collections in fact actively use iterators, in both languages. Whenever you walk through the elements of a collection, there is some sort of iterator involved, even if you don't see it explicitly in the code. I give examples in Java, as I am more familiar with it.

The preferred idiom to iterate over a collection prior to Java 5 - using an Iterator explicitly:

for (Iterator i = c.iterator(); i.hasNext(); ) {
  doSomething((Element) i.next()); // (No generics before 1.5)
}

And since Java 5:

for (Element e : elements) {
  doSomething(e);
}

The latter results in practically identical bytecode though, using an Iterator behind the curtain.

---

The IEnumerable interface is exactly the iterator pattern :)

---

In Java, an Iterator has other uses, in particular the Iterator.remove() can still be useful.

---

Yes, we still need iterators!

1) Looping through linked lists is O(n^2) in time without iterators.

for (int i = 0; i < list.size(); i++)
  list.get(i).foo();

To get to element #5, the list starts at the head element and follows 4 links. To get to element #6 on the next loop, it starts at the head again, following all the same links (plus one). An iterator would be clever enough to remember the last position, giving O(n). A lot faster!

2) There is a problem with size(). Sometimes you don't know the size yet. Some producer thread could be adding elements, while another thread wants to start reading. If it needs the size first, (for(i=0;i<size;i++) ) it can not start before the producer thread has finished.

A collection might be so big, that the elements don't fit in memory all together. An iterator only provides access to one element at a time, so it needs to fit in only one element.

3) How to loop through all the elements of a tree? To write that code bug free isn't that simple. Luckily, you can get an iterator to all the elements in the tree and happily iterate through them, not having to worry about order or anything.

The iterator hides how the elements are stored and only provides access, a nice abstraction.

---

Iterator and collection are different in that a collection essentially is holding items, and an iterator just retrieves items one by one, not contained within it.

For example, an IDataReader is an iterator to database items, and you could have an IEnumerable iterator to directory entries in a file system, as well as an iterator to a collection.

---

In many cases it is more efficient to iterate over an unknown number of items instead of collecting all of them in a collection. Here are several examples which show, why iterating is more efficient. In some cases it even isn't possible to use collections.

• The list is based on a slow resource, which cannot provide all items at once. (DB reader, file, some network stuff, calculation)
• The source only allows forward cursors (like tapes, DB cursor, server client stream stuff)
• The list is being generated
• The list is extreme long and cannot be held in memory at once
• You are using a linked list, where getting the next element is more efficient, than getting an element at index i.
• After getting a source list, a new result should be created, based on that list. For example a source list should be filtered and converted. It wouldn't be efficient to save the result in a new list, when only some of the values would be reused.

The last example refersd to linq or similiar approaches, where complex object structures can be transformed efficiently. Additionally it is mostly more complicated to use a for loop to handle all items instead of using foreach.

---

The Java and C# collections use the iterator pattern under the hood. It is almost a necessity for mutable collections.

If you instead choose to use the persistent collections (for example, those provided in the Functional Java library), you would no longer need the iterator pattern.

---

Collections encapsulate different types of organizations for a group of values - as in a set, list arrays and such.

What Iterators encapsulate / represent are these -

1. A reference to any one of the stored items in the collection in a type safe way.

Even though i have a list of strings, my internal list implementation would be using an object containing the String value along with next + previous items. Iterator hides these internal objects which might have been exposed otherwise.

1. A way to iterate through them -

Depending on the type of the actual object that represents the iterator iterating through them might be vastly different. eg on an array you would go to the next index. But ona list you would need to access the next or previous item references.

1. Common operations like first last and next items.

2. Additional information like iterator traits that let you know the type of movements supported using the iterator

So instead of having one custom for loop for vector and another custom loop for acessing the element of maps and another custom loop for accessing the collection of a list, we can now have a single access loop that can be applied to any of these types.

In fact this is what makes template based algorithms possible as they now need to only concentrate on what they do with the contents or collections and ignore the type of collections passed to them.

I would go so far as to say that the iterator pattern is the simplest and basic item from which the entire concept of template collections like STL starts.