Are iterators and ranges going to co-exist?

[Steven Schveighoffer]

On Tue, 20 Jul 2010 13:53:37 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> Steven Schveighoffer wrote:
>> On Tue, 20 Jul 2010 09:52:00 -0400, Andrei Alexandrescu  
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>
>>> On 07/20/2010 03:01 AM, Peter Alexander wrote:
>>>> Some more arguments for iterators/cursors:
>>>>
>>>> 1. How would you implement Floyd's cycle finding algorithm using  
>>>> ranges?
>>>> (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
>>>> It uses two iterators over the same range. You would have to  
>>>> wastefully
>>>> use 2 ranges that have the same end coordinate.
>>>
>>> I think there's a confusion somewhere. You may want to check out the  
>>> SList definition in std.algorithm. A SList range is exactly one  
>>> pointer thick. With singly-linked lists it's the iterator approach  
>>> that is wasteful because it canonically transports a null pointer as  
>>> end().
>>  That is an example of a single exception to the rule :)  AFAIK, no  
>> other container types have ranges with no end pointer or length.
>
> C-style strings and generally all sentinel-terminated sequences.

As long as the sentinel is null or some invalid value.  I have  
sentinel-style containers that use a specific sentinel element, which must  
be used as the second endpoint.  These ranges are generally more flexible  
in terms of expressing a range over a container.

The OP's point is pretty accurate IMO, *most* ranges require two pieces of  
info, and I agree with you that the cost of extra storage is worth it for  
the benefits you get.  Your singling out of SList as an example of how  
some containers can implement falsely implies IMO that there are many  
containers with that style of range, when in fact, most of the ranges are  
at least two words thick.  SList stands alone in that category, at least  
for the moment.  I also expect the majority of containers to not use  
single-pointer ranges.

>
>> It also makes SList ranges less expressive.  For example, what if I  
>> wanted a range between two elements in the list?  Such a range is  
>> actually unconstructable.  SList is not a very good example of a  
>> container, because it is so unique and limited.
>
> To express such ranges in SList I used Take.

That is not the same.  For instance, removing the tail of such a range  
 from a singly-linked list is O(n), where it could be O(1) if the range was  
two end points.

-Steve