I am a software engineer at Google on the Android project and the creator of the Java testing framework TestNG. When I'm not updating this weblog with various software-related posts or speaking at conferences, I am busy snowboarding, playing squash, tennis, golf or volleyball or scuba diving. Cedric is a DZone MVB and is not an employee of DZone and has posted 90 posts at DZone. You can read more from them at their website. View Full User Profile

Iterators? They still make these?

06.18.2010
| 7252 views |
  • submit to reddit

The war between procedural and functional programming continues to rage, and the latest skirmish appears in this article, where the author shows two versions that add the contents of a vector.

 

Traditional C++

int Dice::total() const {
int total = 0;

for(const_iterator current = dice.begin();
current != dice.end();
++current)
total += (*current)->faceValue();

return total;
}

Functional C++

int Dice::total() const {
return std::accumulate(
dice.begin(),
dice.end(),
0,
bind(std::plus<int>(), _1, bind(&Die::faceValue, _2))
);
}

The comments show the usual dichotomy between people who prefer one style over the other (I continue to think the procedural style is vastly more readable), but interestingly, nobody seems to notice the one thing that makes both these snippets terrible examples of clean code: they both use iterators.

Iterators were made popular by the Standard Template Library (STL). When it came out (around 1994 I think), the STL featured a lot of concepts that were quite groundbreaking at the time, such as the extreme emphasis on composition over inheritance, something that is still considered a very good practice today.

Unfortunately, the STL also made iterators very popular, and although back then, iterators definitely raised the level of abstraction in the manipulation of containers and algorithms, their main drawback is that they expose a lot more about the internals of the containers than users really need to know.

When the first versions of the Java Collections came out, they enthusiastically embraced iterators as well. We can’t blame the authors, nobody really knew better back then, and this kind of code:

Old Java

List<Integer> l = ...;
int result = 0;
for (Iterator<Integer> it = l.iterator(); it.hasNext(); ) {
result += it.next();
}

was considered a marvel of abstraction.

It took a few years, but finally, the Java community started wondering why we needed iterators at all for such operations. We have a containers, we have elements, and we want to apply a certain operation on these elements. In the description of this problem, iterators are nowhere to be found. This simple realization led to one of the best new features ever introduced in Java : the enhanced for loop.

New Java

List<integer> l = ...;
int result = 0;
for (int n : l) {
result += n;
}

The syntax itself is unimportant (some languages use foreach, others for i in l, etc…), what really matters is that iterators are gone.

Which brings us back to the two code snippets shown at the top of this post. What’s more disturbing is not so much that the procedural version of this code uses iterators (this is, sadly, a common idiom in C++) but that the functional version exposes iterators as well. Why the author of this snippet can even remotely think this is a good idea is beyond me.

And the more I think about iterators, the more I really wonder if they have any place in a public API. At all.

For a while, I thought that being able to traverse a collection without exposing the underlying container sounded like a good idea, so instead of returning a List or a Set, you just return an iterator. I could buy that, although I found that in practice, iterators are pretty hard to manipulate, and as soon as you find yourself needing more sophisticated access to the underlying container (such as the size of the sequence, or random access to its elements), you quickly replace your iterator with a collection exposing the richer interface you need.

Let’s just declare iterators a cute idea that no longer has its place in modern software and move on, shall we?

 

From http://beust.com/weblog/2010/06/17/iterators-they-still-make-these/

Published at DZone with permission of Cedric Beust, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Tags:

Comments

Sebastian Mueller replied on Fri, 2010/06/18 - 3:01am

Hi, interesting statements here, however I tend to disagree.

In your last example you say that iterators are gone. However they aren't (and I know that you know that they aren't :-) ). How would you *implement* the iteration (the Iterable interface) in List<integer> if you didn't have Iterators? In fact Iterators (except for the remove() method) are the smallest possible interface to make such a loop possible. If you want to remove iterators but keep the foreach loop, I would like to see your proposal on how the interface for the class that can be iterated should look like.

 

Hauke Ingmar Schmidt replied on Fri, 2010/06/18 - 3:35am

It does only work because the expression (the list l in this case) is of the type Iterable. See: http://java.sun.com/docs/books/jls/third_edition/html/statements.html#14.14.2

Fabrizio Giudici replied on Fri, 2010/06/18 - 3:38am

In addition to what other commenters said... if you have to scan a list in reverse order, or scan multiple lists at the same time, the foreach construct doesn't help. I'd really not say that iterators are not important today.

Michael Buck replied on Fri, 2010/06/18 - 7:26am

So what is the solution? What would a collections API look like without iterators yet provided the same functionality?

matt inger replied on Fri, 2010/06/18 - 8:26am

Iterators are a NECESSARY abstraction. Without them, it would be pretty much impossible for someone to implement an enhanced for loop (like in java). In fact, i java, the enhanced for loop is made possible, because that particular object implements the "Iterable" interface. As you know (i'm absolutely sure you do), the enhanced for loop is just syntactic sugar for the compiler anyway. I don't see how you could loop over an arbitrary data set (especially those without random) access without some sort of abstraction resembling an iterator. While I agree that in general, users should avoid iterators when looping, they're necessary for the actual implementation.

Cedric Beust replied on Fri, 2010/06/18 - 10:15am

I should have been more specific in my post, but yes, iterators as a concept are obviously essential, I am just saying that they should hardly ever appear in the code we write.

 

Chris Wilkes replied on Fri, 2010/06/18 - 10:21am

How would you represent a list of something that you don't know the size of?  For example you're streaming sensor data off the network.  There's no .size() of that and you probably won't be able to hold all of it in memory.

I also like using iterators as it tells the person using them that they should just run through the collection I'm giving them and not think about trying to traverse it another way or to keep it around in a cache.  It also makes filtering nice, you don't have to build up Lists upon Lists to give people a filtered view of an underlying datasource.

Dan Hrivnak replied on Fri, 2010/06/18 - 11:03am

Iterators are still very necessary.  You can't use the enhanced for loop to remove some elements in a collection based on criteria found while in the loop.  For read-only operations, the enhanced for loop does indeed rock.

Matt Edlefsen replied on Tue, 2010/06/22 - 10:33am

By far the best way of doing this I've seen is the ruby way:

collection.each do |element|
   #work
end

By using closures you can allow the collection object to do all of the actual iterating, which removes the need for an iterator abstraction.

In a compiled language if the "each" method was inline then a smart compiler could optimize this to produce code very close to a hand written loop.

Travis Calder replied on Fri, 2010/06/18 - 2:45pm

I think Chris raises a very important point as well.

I can write a loop over a list without using iterator, but the same doesn't work for situations when you don't know your size.

Anything of a streaming variety immediately breaks this assumption. As well, I believe JDBC actually moves through result-sets in small subsets, and the iterator style is required there too.

There are also the times that I have something that just isn't a standard collection, and I don't want to give the caller access to any collection. Sometimes it's very useful to extend the Iterator interface and make my class an iterator itself. Alternatively, I could make it an iterable, and then return an iterator, but that's six of one and a half-dozen of the other. I still need that "Iterator" concept.

Nick Lozon replied on Fri, 2010/06/18 - 3:58pm

Just a cute idea? I don't think you can beat the efficiency of jumping around a data set effortlessly knowing the size of the underlying object, like you can with iterators. I really don't see how you can trash talk iterators when most looping and set traversing "algorithms" are based on iterators. That fancy for-loop of yours probably uses iterators in the backgrounds - its just a dumbed down implementation. For most programmers, the day comes when you need to increase the step-value of your loop, or traverse backwards...and you discover the amazing iterator...and think, "why didn't I know about this earlier?". Don't mind me. Just annoying that iterators play the largest role in all set traversing, and this guy is trying to undermine them like they're nothing.

Erwin Mueller replied on Fri, 2010/06/18 - 11:02pm

I think the comments are missing the point. In my view the author don't say that the iterator pattern is bad or should not be used. But the API should hide the fact that we are using Iterators.

 The for-each loop hides the fact that we are using the Iterator interface, because we don't see the old style for (Iterator it= ... anymore.

In the C++ example, why we can't just have 

int Dice::total() const {
return std::accumulate(
dice,
0,
bind(std::plus<int>(), _1, bind(&Die::faceValue, _2))
);
}

 Note the missing iterators.

That we are using iterators is an implementation detail.  The fact that the for-each loop in Java uses the Iterable interface is an implementation detail. 

The problem with the Java for-each loop is that it is tied to the Iterable interface, now and forever. We can't change this implementation detail, because then a lot of code wouldn't work anymore. It would be better if the Java designer thought a step further and implemented closures. That way we could use something else besides Iterable for the for-each loop.

Jeroen Wenting replied on Mon, 2010/06/21 - 12:17am

Let's just declare people who don't understand what's happening and make sweeping statements (like the one that iterators are useless) because of that a cute idea that should be burried deep and forgotten about.

Nick Lozon replied on Mon, 2010/06/21 - 8:26am

Yes, there is API implementation to facilitate iterators, but that does not negate the existence, usefulness or robustness of iterators. Such a "Java" way of doing things - use an API call for everything and not really understand what's going on.

Mike P(Okidoky) replied on Mon, 2010/06/21 - 10:35am

The "Traditional C++" sample looks readable. The "New Java" version looks very nice. The "Functional C++" looks horrid and it is highly unlikely you'd be able to mix junior / intermediate programmers in the development team, with this kind of inelegant code butchering. I agree that iterating behaviors do not belong in an API at all. In C++, a macro can help make it more readable. Perhaps macros need enhancing to allow for more flexibility. Java continues to be effective because it has been protected from being butchered. I agree that new features aren't necessarily bad, but people need to keep better in mind how to keep junior developers effective in the team.

Michael Eric replied on Wed, 2012/09/26 - 3:41pm

The new for-loops haven’t really made iterators go away though. They’ve just made them easier to work with, a little syntactic sugar. Look at a language like python, it’s got iterators all over the place, with a hugely simplified interface. And if you need anything more complicated, you can use the richer sequence types.

So iterators are still a good idea, they just needed a nicer interface

linux archive 

Rehman Khan replied on Sat, 2012/02/25 - 4:28am

First off, I agree that the procedural code is much more understandable–but only because it’s in C++, a language with a syntactical bias towards procedural code.

Conceptually, I actually find the functional way more understandable, and I think you do too; hence, your preference to obviate away the explicitness of the for loop for the foreach style loop.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.