C++ Iterators Considered Harmful?

Question

At the Boost library conference today, Andrei Alexandrescu author of the book Modern C++ Design and the Loki C++ library, spoke about why iterators are bad, and he had a better solution.

I tried to read the presentation slides, but could not get much out of them. I have these questions for the StackOverflow community:

1. Are iterators bad?
2. Is his replacement really better?
3. Will C++ implementators pick up his ideas?

http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/08/iterators-must-go.pdf

Answer 1

I agree with him that iterators are mostly inferior to ranges, and I don't know if 'something better' will get picked up.

"The good is the enemy of the best" is strongly at play here, as it usually is. Iterators are useful and firmly entrenched, so it's hard to know if something better like ranges can supplant them in a reasonable amount of time.

Answer 2

I think C++ implementors will have their hands full producing full working support for C++0x, without implementing new, non-standard paradigms.

Answer 3

1. Sometimes
2. Probably
3. Not likely, at least not for many years

Answer 4

First, to answer your questions:

1. No. In fact, I argued elsewhere that iterators are the most important/fundamental concept of computer science ever. I (unlike Andrei) also think that iterators are intuitive.
2. Yes, definitely but that shouldn't come as a surprise.
3. Hmm. Looking at Boost.Range and C++0x – haven't they already?

Andrei's big contribution here is just to say: drop the concept of iterators altogether, see ranges not just as a convenience wrapper but rather as a core construct. Other languages have already done this (much of Andrei's concepts just echo .NET's LINQ or Python's iterators) but they all only offer output ranges. Andrei argues for different types of ranges, much like the conventional iterator categories.

In that light, it's odd that he starts by mocking the arbitrariness of these iterator categories.

I also think that his examples are off, especially his file copying: yes, the iterator variant is a huge improvement over the 1975 code. It reduces a loop with complicated break condition down to one statement. What he's really taking issue with here is just the syntax. Well, excuse me: we're talking about C++ here – of course the syntax is ugly. And yes, using ranges here is an improvement – but only syntactically.

I also think that Andrei's find implementation is off. What he really defines there is the DropUntil operation (naming is hard!) from LINQ. The find operation should really return either one or zero elements (or an iterator!). Shunning iterators here isn't helpful in my opinion since we might want to modify the value directly instead of copying it. Returning a one-element range here only adds overhead without a benefit. Doing it Andrei's way is bad because then the name of the method is just wrong and misleading.

That said, I essentially agree with Andrei in almost all points. Iterators, while being my pet concept from computer science, are certainly a big syntactical burden and many ranges (especially infinite generators) can (and should) be implemented conveniently without them.

Answer 5

I think we should use ranges next to iterators, i.e. we should choose the evolution way, not revolution way.

Answer 6

C++0x is already making the first steps:

• rvalue references solve some problems with treating containers as ranges
• ranges have been added to the core library, including range concepts

Transitioning to ranges without losing any iterator functionality (think of all the combinations of iterator categories, const-ness and rvalue-ness) is hard, especially if you try to factor in infinite and mutable ranges.

Answer 7

1. Most of us make a simple use of them in what have become well known idioms, like in for loops to iterate through an std::vector. A developer reads it and knows what's going on. In our everyday coding life, iterators are not good or bad, they're just "what gets the job done".
2. Probably, yes.
3. I don't think so.

Answer 8

Andrei at times can be a bit provocative. Iterators are a reasonable concept, and quite fundamental in the sense that bits are. But just like most bits in C++ are not bools, but part of larger types,most iterators should be dealt with at a high level. Andrei is right that the proper level to do so is the range object. But not all ranges are properly exposed as iterator ranges, as the istream_iterator sentinel shows. That's just a hack to create an artificial end iterator. I don't think his ideas will be picked up by implementations, though. C++1x will be as relevant as C99.

Answer 9

The only argument I can see from that presentation is the inability to define ranges, and the c++0x "Range for statement" proposal seems to eliminate that problem to some extent anyway. maybe it shouldn't be an argument about if iterators should / shouldn't be used at all, but more what situations should / shouldn't they be used for?

Answer 10

Like any API or function, if misused can create many problems of identification difficult. Iterators have used in many projects, but always maintaining the necessary care required according to their characteristics. Its use should be preceded by a good understanding of their limitations. Iterators can be very useful if user properly.
This questions are related :
Is there any way to check if an iterator is valid?
Should I prefer iterators over const_iterators?

Answer 11

I disagree with both Andrei and Konrad and myself :-)

The most fundamental concept is an interface not an iterator and that is pretty obvious in any work anyone does today (which is all about cross-library, cross-language, cross-compiler, cross-OS, cross-platform, you cross-name it :-)

Neither iterator or range (apart from source-level use) offer anything more than a clean and simple, non intrusive or intrusive, non shared or shared, non unique or unique: pointer ! Clean pointer to typed data is simply put universal and you can make data mutable or immutable and many other things. All interface is is just another level of indirection to it while still being friendly to machine and compiler of all sorts, plus far safer, relegating iterators and range usage to an implementation detail.

To that extent IEnumerable and IQueryable do the half 'right thing' TM but they are clearly inferior in their concepts of iteration and much more to what you can do with STL, retain control and so on and on (but otoh, they have better metadata and hence a better, cleaner model). Point being with interfaces you can build any abstraction you want and satisfy, well probably contraversial but essentially a no-brainer: optimal, and runtime or compile-time neutral data representation and code (heck essential to algorithms and compilers and VMs and what not).

It is even possible to optimise it for 'dynamic'/component systems down to 'runtime' inlining (screw HotSpot VM:-).. To that extent, the advance to 1975 is minimal as evident by a huge interop industry workload (it's everywhere you look, including this site, its use of proprietary and open tech, etc; in computer science idealism, well, this type of interfacing 'work' should not exist should it)..

Answer 12

Isn't Andrei trying to do some hidden marketing for the D language (currently he is working with it)...?

Andrei states that containers are ok, but iterators are ugly, non-intuitive, error-prone and dangerous, hard to implement (well this last one seems to be rather true...) And what do we have in C++... pointers? Aren't they ugly/.../dangerous? But we happily embraced them and live with them.

Which one is more intuitive to write:

for(auto i=foo.begin();i!=foo.end();++i)
    bar(*i);

or

for (auto r=foo.all(); !foo.empty(); foo.popFront())
        bar(r.front());

Iterators concept can be complemented with ranges and other ideas, but I think that they have their place and won't be replaced.

Answer 13

1. No, they are not bad, they are very clever idea in fact. However, they are not ideal and there is room for improvements in the concept of iterator.

2. It solves number of real-life problems with iterators. For instance, it's tedious (also error prone) in many cases to query two separate objects, iterators, from a single containers and then pass them as still two separate objects to an algorithm. Why not to pass a single object around? Even std::pair<iterator, iterator> would make for a crude range which is easier to manipulate - one object, not two. Also, it's a good idea to consider a range is an iterator. That's in fact what Andrei suggests. By the way, some of these problems have been already solved by Boost.Range.

3. I would expect it happened, but it will not be a revolution, rather evolution.