The slides from my keynote at BoostCon 2009 (www.boostcon.com) are now available from:

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

The talk went so well, the urge to brag is too mighty to resist. I mean it's not everyday that several people come and tell they've literally lost sleep and focus on other talks because of thinking about ranges. Also, there was a definite feel of "before" and "after". In short, the talk has generated a great deal of interest in both D proper and in the Boost community rewriting the STL entirely in terms of ranges.


Andrei

Andrei Alexandrescu wrote:
> The slides from my keynote at BoostCon 2009 (www.boostcon.com) are now available from:
> 
> http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/08/iterators-must-go.pdf 
> 
> 
> The talk went so well, the urge to brag is too mighty to resist. I mean it's not everyday that several people come and tell they've literally lost sleep and focus on other talks because of thinking about ranges. Also, there was a definite feel of "before" and "after". In short, the talk has generated a great deal of interest in both D proper and in the Boost community rewriting the STL entirely in terms of ranges.

Have you considered an article in the paper version of DrDobb's?

And maybe some other publications, too. D could use this PR. (Maybe even CUJ.)

http://www.reddit.com/r/programming/comments/8isiw/author_of_modern_c_design_stl_iterators_must_die/

Walter Bright wrote:
> http://www.reddit.com/r/programming/comments/8isiw/author_of_modern_c_design_stl_iterators_must_die/ 


The link reads like Andrei wants to mureder Stepanov.....

Good thing I read the slides. :-)

Great paper!  The only quibble I have so far is that I think iterators can support sentinel-terminated containers, it just isn't terribly natural to do so.

On Thu, 07 May 2009 23:01:20 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> The slides from my keynote at BoostCon 2009 (www.boostcon.com) are now available from:
>
> http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/08/iterators-must-go.pdf
>
> The talk went so well, the urge to brag is too mighty to resist. I mean it's not everyday that several people come and tell they've literally lost sleep and focus on other talks because of thinking about ranges. Also, there was a definite feel of "before" and "after". In short, the talk has generated a great deal of interest in both D proper and in the Boost community rewriting the STL entirely in terms of ranges.

A good paper.

You still have not addressed the usage of iterators as general data structure pointers.  As far as I can tell, ranges do not implement this.

i.e. find surrounding elements of an element.

With iterators:

auto iter = container.find(elem);
auto elembefore = iter - 1;
auto elemafter = iter + 1;

Assuming incrementing and decrementing an iterator is checked for out-of-bounds.

-Steve

Sean Kelly wrote:
> Great paper!  The only quibble I have so far is that I think iterators can support sentinel-terminated containers, it just isn't terribly natural to do so.

The things I particularly like:

find_end() -- Reverse iterators are a pain in the ass.  The simplicity of this is just fantastic.

Chain, Zip, Stride, Radial -- 100% pure awesome.

partial_sort() -- The definition of this is just ingenious.  It derives naturally from the range design and yet I'd never have thought of it otherwise.

Regarding iostream ranges, I'd have liked if there was a bit more about the difference in interface: put vs. push/pop.  One "benefit" of stream iterators is that they use the same syntax as other iterators, so it would be good to hear why the change in syntax for ranges isn't actually a design flaw.

Overall, the presentation makes a very compelling case for ranges. While it's /possible/ to do quite a lot with iterators, the truly interesting stuff is so difficult/messy that it isn't worth doing. Ranges are elegant and safe for even fancy things.  Nice work.

Steven Schveighoffer wrote:
> You still have not addressed the usage of iterators as general data structure pointers.  As far as I can tell, ranges do not implement this.
> 
> i.e. find surrounding elements of an element.
> 
> With iterators:
> 
> auto iter = container.find(elem);
> auto elembefore = iter - 1;
> auto elemafter = iter + 1;
> 
> Assuming incrementing and decrementing an iterator is checked for out-of-bounds.

The problem is that last statement - "Assuming". If the iterator is the first or the last, or if there's only 1 or 2 elements in the container, it's crash city. Iterators are *inherently* uncheckable.

For finding the elemafter, it's trivial as find() returns a range from the found element to the end (and it's also trivially checkable!).

For elembefore, there's a bit more work involved, probably defining a find() that returns a range backed up by one one.

On Fri, 08 May 2009 11:57:41 -0400, Walter Bright <newshound1@digitalmars.com> wrote:

> Steven Schveighoffer wrote:
>> You still have not addressed the usage of iterators as general data structure pointers.  As far as I can tell, ranges do not implement this.
>>  i.e. find surrounding elements of an element.
>>  With iterators:
>>  auto iter = container.find(elem);
>> auto elembefore = iter - 1;
>> auto elemafter = iter + 1;
>>  Assuming incrementing and decrementing an iterator is checked for out-of-bounds.
>
> The problem is that last statement - "Assuming". If the iterator is the first or the last, or if there's only 1 or 2 elements in the container, it's crash city. Iterators are *inherently* uncheckable.
>
> For finding the elemafter, it's trivial as find() returns a range from the found element to the end (and it's also trivially checkable!).
>
> For elembefore, there's a bit more work involved, probably defining a find() that returns a range backed up by one one.

You're assuming an iterator does not know its bounds.  Maybe I should call it something other than iterator.  How about cursor?

There are definite reasons to use containers in ways that don't involve std.algorithm, where something that has the easy ability to move back and forth N times without weird subrange operations.

I'm thinking of a structure with either a pointer to the container for bounds checking, or a range and pointer combined (where the invariant is that the pointer is always within the range).

I'm not saying ranges are not great, i think they are a HUGE step forward, but the statement "Iterators must be eliminated" may be too harsh.  Perhaps the unchecked iterator, yes (but you may want to allow it in certain performance-critical code).

-Steve

Steven Schveighoffer wrote:
> You're assuming an iterator does not know its bounds.

That's right. That's the usual design, which is based on the pointer model. Pointers do not know their limits.

> Maybe I should call it something other than iterator.  How about cursor?

Or range? <g>


> There are definite reasons to use containers in ways that don't involve std.algorithm, where something that has the easy ability to move back and forth N times without weird subrange operations.
> 
> I'm thinking of a structure with either a pointer to the container for bounds checking, or a range and pointer combined (where the invariant is that the pointer is always within the range).
> 
> I'm not saying ranges are not great, i think they are a HUGE step forward, but the statement "Iterators must be eliminated" may be too harsh.  Perhaps the unchecked iterator, yes (but you may want to allow it in certain performance-critical code).

If you had an iterator that knew its beginning and end, then the whole paradigm of:

   for (iterator i = begin; i != end; i++)

doesn't make much sense because of the redundancy.