Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> David Gileadi wrote:
> > Sergey Gromov wrote:
> >> If you draw a parallel between a range and a stack of paper, the shrink methods would probably be pop/snap...  I'd also propose next() for moving the start and prev() for moving the end.  It sounds a bit misleading but, on the other hand, it closely resembles forward and backward iteration with the opposite end of a range representing the iteration limit.  Or maybe forward()/backward(), or fwd()/back()?
> > 
> > Perhaps reduce() instead of pop() for moving the end?
> 
> I love reduce! Thought of it as well. Unfortunately the term is loaded with reduction of a binary operation over a range, as e.g. in std.algorithm.
> 
> I think shrink() is reasonable. next() moves to the next thing. shrink() shrinks the set of dudes I can reach.

I thought of next/shrink as well, but they look asymmetrical, and also next here is a form of shrink, too.  Someone could think of "shrink" as of chopping from both ends.

Bill Baxter <wbaxter@gmail.com> wrote:
> Here's one from DinkumWare's <algorithm>:
> 
> template<class _BidIt1,
> 	class _BidIt2,
> 	class _BidIt3> inline
> 	_BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
> 		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Range_checked_iterator_tag)
> 	{	// merge backwards to _Dest, using operator<
> 	for (; ; )
> 		if (_First1 == _Last1)
> 			return (_STDEXT unchecked_copy_backward(_First2, _Last2, _Dest));
> 		else if (_First2 == _Last2)
> 			return (_STDEXT unchecked_copy_backward(_First1, _Last1, _Dest));
> 		else if (_DEBUG_LT(*--_Last2, *--_Last1))
> 			*--_Dest = *_Last1, ++_Last2;
> 		else
> 			*--_Dest = *_Last2, ++_Last1;
> 	}
> 
> 
> You can probably work around it some way, but basically it's using the ability to ++ and -- on the same end as a sort of "peek next".

They're using the ability to ++ and -- to avoid post-decrement at any cost.  Otherwise it'd be just

> 		else if (_DEBUG_LT(*_Last2, *_Last1))
> 			*--_Dest = *_Last1--;
> 		else
> 			*--_Dest = *_Last2--;

Now the same algorithm in ranges:

> Merge_backward(R1, R2, R3)(R1 s1, R2 s2, R3 dst)
> {
>     for (;;)
>     {
>         if (s1.isEmpty())
>             dst[] = s2[];
>         else if (s2.isEmpty())
>             dst[] = s1[];
>         else if (s1.last < s2.last)
>         {
>             dst.last = s1.last;
>             s1.shrink();
>         }
>         else
>         {
>             dst.last = s2.last;
>             s2.shrink();
>         }
>         dst.shrink();
>     }
> }

If there were shrink-on-read and (eureka!) shrink-on-write operations, it would be even shorter:

>         else if (s1.last < s2.last)
>             dst.putBack(s1.getBack());
>         else
>             dst.putBack(s2.getBack());

where both getBack() and putBack() shrink the range from the end side.

Bill Baxter wrote:
> On Thu, Sep 11, 2008 at 2:44 AM, Andrei Alexandrescu
> Cognitive load...
> What if I want to write a nice standalone function that takes a
> pointer to where we are and manipulates it?  I have to pass that
> function two iterators I suppose?

A function only needing one iterator is a chymera. It can't move it any direction. To such a function you pass a pointer or reference to the object you want to manipulate directly. What's there to not like about it.

> One is (begin,current) the other
> (current,end), and as I iterate I have to move both the second of the
> first and the first of second?  All just to do something that should
> be trivial with a linked list.
> 
> I agree that your pinch range is needed, but I also see a need for
> something that maps more directly onto the features of a doubly linked
> list.

I think you get a lot more insight by actually sitting down and rewriting a part of std.algorithm, and/or write some more meaningful algorithms with your abstraction of choice. When I started doing so I had no idea of what range primitives I need. And just like you now, I kept on hypothesizing in the dark on whether I need this and whether I need that. When you hypothesize in the dark the number of primitive things you need really grows unbounded, because there's always some unrealized imaginary need you want to satisfy. To carry the discussion on equal footing you need to do some of that work. Otherwise you will keep on coming with hypothetical situations of unverifiable likelihood, and I will have little meaningful retort to put forth.

Speaking of which, a great merit of Stepanov is that he showed what a great host of algorithms can be implemented with a precise and narrow interface. We all knew how to rotate elements in an array. He showed how to rotate elements in a singly-linked list.


Andrei

Sergey Gromov wrote:
> Bill Baxter <wbaxter@gmail.com> wrote:
>> Here's one from DinkumWare's <algorithm>:
>>
>> template<class _BidIt1,
>> 	class _BidIt2,
>> 	class _BidIt3> inline
>> 	_BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
>> 		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Range_checked_iterator_tag)
>> 	{	// merge backwards to _Dest, using operator<
>> 	for (; ; )
>> 		if (_First1 == _Last1)
>> 			return (_STDEXT unchecked_copy_backward(_First2, _Last2, _Dest));
>> 		else if (_First2 == _Last2)
>> 			return (_STDEXT unchecked_copy_backward(_First1, _Last1, _Dest));
>> 		else if (_DEBUG_LT(*--_Last2, *--_Last1))
>> 			*--_Dest = *_Last1, ++_Last2;
>> 		else
>> 			*--_Dest = *_Last2, ++_Last1;
>> 	}
>>
>>
>> You can probably work around it some way, but basically it's using the
>> ability to ++ and -- on the same end as a sort of "peek next".
> 
> They're using the ability to ++ and -- to avoid post-decrement at any cost.  Otherwise it'd be just
> 
>> 		else if (_DEBUG_LT(*_Last2, *_Last1))
>> 			*--_Dest = *_Last1--;
>> 		else
>> 			*--_Dest = *_Last2--;
> 
> Now the same algorithm in ranges:
> 
>> Merge_backward(R1, R2, R3)(R1 s1, R2 s2, R3 dst)
>> {
>>     for (;;)
>>     {
>>         if (s1.isEmpty())
>>             dst[] = s2[];
>>         else if (s2.isEmpty())
>>             dst[] = s1[];
>>         else if (s1.last < s2.last)
>>         {
>>             dst.last = s1.last;
>>             s1.shrink();
>>         }
>>         else
>>         {
>>             dst.last = s2.last;
>>             s2.shrink();
>>         }
>>         dst.shrink();
>>     }
>> }
> 
> If there were shrink-on-read and (eureka!) shrink-on-write operations, it would be even shorter:
> 
>>         else if (s1.last < s2.last)
>>             dst.putBack(s1.getBack());
>>         else
>>             dst.putBack(s2.getBack());
> 
> where both getBack() and putBack() shrink the range from the end side.

Got to say I'm pretty much in awe :o). But (without thinking much about it) I think the assignments dst[] = s1[] and dst[] = s2[] should be replaced with calls to copy(retro(sx), retro(dst)). No?

Andrei

"Andrei Alexandrescu" wrote
> Steven Schveighoffer wrote:
>> "Andrei Alexandrescu" wrote
>>> Bill Baxter wrote:
>>>> But upon further reflection I think it may be that it's just not what I would call a bidirectional range.  By that I mean it's not good at solving the problems that a bidirectional iterator in C++ is good for.
>>> It's good. I proved that constructively for std.algorithm, which of course doesn't stand. But I've also proved it theoretically informally to myself. Please imagine an algorithm that bidir iterators do and bidir ranges don't.
>>
>> Any iterative algorithm where the search might go up or down might be a candidate.  Although I think you have a hard time showing one that needs strictly bidirectional iterators and not random access iterators. Perhaps a stream represented as a linked list?  Imagine a video stream coming in, where the player buffers 10 seconds of data for decoding, and keeps 10 seconds of data buffered behind the current spot.  If the user pauses the video, then wants to play backwards for 5 seconds, what kind of structure would you use to represent the 'current point in time'?  A bidir range doesn't cut it, because it can only move one direction at a time.
>
> Of course it does. You just remember the leftmost point in time you need to remember. Then you use range primitives to get to where you want. Maybe a better abstraction for all that is a sliding window though.

Not sure.  I'd have to see how messy the 'use range primitives' looks :)

>
>> You would need 2 bidir ranges, but since you can't 'grow' the ranges, you can't add stuff as it is consumed from the forward range to the backwards range, or am I wrong about that?  So how do you continually update your backwards iterator?  I suppose you could simply 'generate' the backwards iterator when needed by diff'ing with the all range, but it seems unnecessarily cumbersome.  In fact, you'd need to regenerate both ranges as data is removed from the front and added to the back (because the ends are continually changing).  Perhaps a meta-range which has 2 bidir ranges in it can be provided.  It would be simple enough to implement using existing ranges, but might have unnecessary performance issues.
>
> You don't need a meta range, though it's a good idea to have it as a convenience structure. All you need is store the two ranges and do range operations on them.

Perhaps not, I haven't used the ranges as you have implemented them, nor have I used them from boost.  I agree with the general idea that ranges are safer and simpler to use when a range is needed.  It makes perfect sense to pass a single range type rather than 2 iterators, and this is the majority of usages for iterators anyways.  I 100% agree that ranges are the way to go instead of passing begin() and end() all the time to algorithm templates.

>
> Notice that "a range can't grow" is different from "a range can't be assigned from a larger range". In particular, a range operation can return a range larger than both input ranges. But not larger than their union :o).

Yes, so every time you add an element you have to update your forward range from the 'all' range so it includes the new element at the end.  Every time you remove an element, you have to update your reverse range from the 'all' range so it excludes the element at the beginning.  Failure to do this results in invalid ranges, which seems to me like a lot more work than simply not doing anything  (in the case of an iterator).  The pitfalls of using ranges for dynamically changing containers might outweigh the advantages that they provide in certain cases.

>> My belief is that ranges should be the form of input to algorithms, but iterators should be provided for using containers as general data structures.  Similar to how strings are represented by arrays/slices, but iterators (pointers) exist if you need them.
>
> If we agree it's better without iterators if not needed, we'd need a strong case to add them. Right now I have a strong case against them.

I don't need to worry about whether you have them or not, I can always implement them on my own ;)  Really, range/iterator support doesn't require direct support from the compiler (except for builtin arrays), and any improvements made to the compiler to support ranges (such as reference returns, etc) can be applied to iterators as well.

I think ranges are an excellent representation when a range of elements is needed.  I think a cursor or iterator is an excellent representation when an individual position is needed.

>> I'll probably move forward with this model in dcollections, I really like the range idea, and in general the view on how ranges are akin to slices. But I also like having access to iterators for other functions.
>
> Which functions?

Functions which take or return a single position.  Such as 'erase the element at this position' or 'find the position of element x'.

-Steve

On Thu, Sep 11, 2008 at 3:33 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Bill Baxter wrote:
>>
>> On Thu, Sep 11, 2008 at 2:44 AM, Andrei Alexandrescu
>> Cognitive load...
>> What if I want to write a nice standalone function that takes a
>> pointer to where we are and manipulates it?  I have to pass that
>> function two iterators I suppose?
>
> A function only needing one iterator is a chymera. It can't move it any direction. To such a function you pass a pointer or reference to the object you want to manipulate directly. What's there to not like about it.

Oops.  I meant two ranges not two iterators there.  There are no iterators in this world.  What I was after in the above is a function that somehow gets a) where we are, b) how far back we can go c) how far forward we can go.    With ranges that seems cumbersome.  With iterators it's exactly those 3 iterators.

> I think you get a lot more insight by actually sitting down and rewriting a part of std.algorithm, and/or write some more meaningful algorithms with your abstraction of choice. When I started doing so I had no idea of what range primitives I need. And just like you now, I kept on hypothesizing in the dark on whether I need this and whether I need that. When you hypothesize in the dark the number of primitive things you need really grows unbounded, because there's always some unrealized imaginary need you want to satisfy. To carry the discussion on equal footing you need to do some of that work. Otherwise you will keep on coming with hypothetical situations of unverifiable likelihood, and I will have little meaningful retort to put forth.

Ok.  There's the ultimatum.  I'll shut up and go to bed now.  :-)

--bb

Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Sergey Gromov wrote:
> > Bill Baxter <wbaxter@gmail.com> wrote:
> >> Here's one from DinkumWare's <algorithm>:
> >>
> >> template<class _BidIt1,
> >> 	class _BidIt2,
> >> 	class _BidIt3> inline
> >> 	_BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
> >> 		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Range_checked_iterator_tag)
> >> 	{	// merge backwards to _Dest, using operator<
> >> 	for (; ; )
> >> 		if (_First1 == _Last1)
> >> 			return (_STDEXT unchecked_copy_backward(_First2, _Last2, _Dest));
> >> 		else if (_First2 == _Last2)
> >> 			return (_STDEXT unchecked_copy_backward(_First1, _Last1, _Dest));
> >> 		else if (_DEBUG_LT(*--_Last2, *--_Last1))
> >> 			*--_Dest = *_Last1, ++_Last2;
> >> 		else
> >> 			*--_Dest = *_Last2, ++_Last1;
> >> 	}
> >>
> >>
> >> You can probably work around it some way, but basically it's using the ability to ++ and -- on the same end as a sort of "peek next".
> > 
> > They're using the ability to ++ and -- to avoid post-decrement at any cost.  Otherwise it'd be just
> > 
> >> 		else if (_DEBUG_LT(*_Last2, *_Last1))
> >> 			*--_Dest = *_Last1--;
> >> 		else
> >> 			*--_Dest = *_Last2--;
> > 
> > Now the same algorithm in ranges:
> > 
> >> Merge_backward(R1, R2, R3)(R1 s1, R2 s2, R3 dst)
> >> {
> >>     for (;;)
> >>     {
> >>         if (s1.isEmpty())
> >>             dst[] = s2[];
> >>         else if (s2.isEmpty())
> >>             dst[] = s1[];
> >>         else if (s1.last < s2.last)
> >>         {
> >>             dst.last = s1.last;
> >>             s1.shrink();
> >>         }
> >>         else
> >>         {
> >>             dst.last = s2.last;
> >>             s2.shrink();
> >>         }
> >>         dst.shrink();
> >>     }
> >> }
> > 
> > If there were shrink-on-read and (eureka!) shrink-on-write operations, it would be even shorter:
> > 
> >>         else if (s1.last < s2.last)
> >>             dst.putBack(s1.getBack());
> >>         else
> >>             dst.putBack(s2.getBack());
> > 
> > where both getBack() and putBack() shrink the range from the end side.
> 
> Got to say I'm pretty much in awe :o). But (without thinking much about it) I think the assignments dst[] = s1[] and dst[] = s2[] should be replaced with calls to copy(retro(sx), retro(dst)). No?

They originally use backward copying because they don't know where the destination range starts, long live buffer overrun.  In case of ranges the destination range is well defined and there are no overlaps---that is, I believe this algorithm doesn't support using the same buffer as source and destination.  So slice copying should be OK.

Sergey Gromov wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>> Sergey Gromov wrote:
>>> Bill Baxter <wbaxter@gmail.com> wrote:
>>>> Here's one from DinkumWare's <algorithm>:
>>>>
>>>> template<class _BidIt1,
>>>> 	class _BidIt2,
>>>> 	class _BidIt3> inline
>>>> 	_BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
>>>> 		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Range_checked_iterator_tag)
>>>> 	{	// merge backwards to _Dest, using operator<
>>>> 	for (; ; )
>>>> 		if (_First1 == _Last1)
>>>> 			return (_STDEXT unchecked_copy_backward(_First2, _Last2, _Dest));
>>>> 		else if (_First2 == _Last2)
>>>> 			return (_STDEXT unchecked_copy_backward(_First1, _Last1, _Dest));
>>>> 		else if (_DEBUG_LT(*--_Last2, *--_Last1))
>>>> 			*--_Dest = *_Last1, ++_Last2;
>>>> 		else
>>>> 			*--_Dest = *_Last2, ++_Last1;
>>>> 	}
>>>>
>>>>
>>>> You can probably work around it some way, but basically it's using the
>>>> ability to ++ and -- on the same end as a sort of "peek next".
>>> They're using the ability to ++ and -- to avoid post-decrement at any cost.  Otherwise it'd be just
>>>
>>>> 		else if (_DEBUG_LT(*_Last2, *_Last1))
>>>> 			*--_Dest = *_Last1--;
>>>> 		else
>>>> 			*--_Dest = *_Last2--;
>>> Now the same algorithm in ranges:
>>>
>>>> Merge_backward(R1, R2, R3)(R1 s1, R2 s2, R3 dst)
>>>> {
>>>>     for (;;)
>>>>     {
>>>>         if (s1.isEmpty())
>>>>             dst[] = s2[];
>>>>         else if (s2.isEmpty())
>>>>             dst[] = s1[];
>>>>         else if (s1.last < s2.last)
>>>>         {
>>>>             dst.last = s1.last;
>>>>             s1.shrink();
>>>>         }
>>>>         else
>>>>         {
>>>>             dst.last = s2.last;
>>>>             s2.shrink();
>>>>         }
>>>>         dst.shrink();
>>>>     }
>>>> }
>>> If there were shrink-on-read and (eureka!) shrink-on-write operations, it would be even shorter:
>>>
>>>>         else if (s1.last < s2.last)
>>>>             dst.putBack(s1.getBack());
>>>>         else
>>>>             dst.putBack(s2.getBack());
>>> where both getBack() and putBack() shrink the range from the end side.
>> Got to say I'm pretty much in awe :o). But (without thinking much about it) I think the assignments dst[] = s1[] and dst[] = s2[] should be replaced with calls to copy(retro(sx), retro(dst)). No?
> 
> They originally use backward copying because they don't know where the destination range starts, long live buffer overrun.  In case of ranges the destination range is well defined and there are no overlaps---that is, I believe this algorithm doesn't support using the same buffer as source and destination.  So slice copying should be OK.

One up for ranges then. Whew. I was due for it :o).

Andrei

Bill Baxter <wbaxter@gmail.com> wrote:
> Here's another, an insertion sort:
> 
> template<class _BidIt,
> 	class _Ty> inline
> 	void _Insertion_sort1(_BidIt _First, _BidIt _Last, _Ty *)
> 	{	// insertion sort [_First, _Last), using operator<
> 	if (_First != _Last)
> 		for (_BidIt _Next = _First; ++_Next != _Last; )
> 			{	// order next element
> 			_BidIt _Next1 = _Next;
> 			_Ty _Val = *_Next;
> 
> 			if (_DEBUG_LT(_Val, *_First))
> 				{	// found new earliest element, move to front
> 				_STDEXT unchecked_copy_backward(_First, _Next, ++_Next1);
> 				*_First = _Val;
> 				}
> 			else
> 				{	// look for insertion point after first
> 				for (_BidIt _First1 = _Next1;
> 					_DEBUG_LT(_Val, *--_First1);
> 					_Next1 = _First1)
> 					*_Next1 = *_First1;	// move hole down
> 				*_Next1 = _Val;	// insert element in hole
> 				}
> 			}
> 	}

This is a bit more complex.  If only basic operations on ranges are allowed, it looks like this:

> void Insertion_sort1(R, T)(R r)
> {
>     if (!r.isEmpty())
>     {
>         R tail = r;
>         do
>         {
>             tail.next();
>             R head = r.before(tail);
>             T _Val = head.last;
>             if (_Val < head.first)
>             {
>                 R from, to;
>                 from = to = head;
>                 from.shrink();
>                 to.next();
>                 copy(retro(from), retro(to));
>                 head.first = _Val;
>             }
>             else
>             {
>                 R head1 = head;
>                 head1.shrink();
>                 for (; _Val < head1.last; head.shrink(), head1.shrink())
>                     head.last = head1.last;
>                 head.last = _Val;
>             }
>         }
>         while (!tail.isEmpty())
>     }
> }

Though it starts to look much better if we employ shrink-on-read/shrink- on-write AND copy-on-shrink, AKA incremental slicing:

> void Insertion_sort1(R, T)(R r)
> {
>     if (!r.isEmpty())
>     {
>         R tail = r;
>         do
>         {
>             tail.next();
>             R head = r.before(tail);
>             T _Val = head.last;
>             if (_Val < head.first)
>             {
>                 copy(retro(head[0..$-1]), retro(head[1..$]));
>                 head.first = _Val;
>             }
>             else
>             {
>                 for (R head1 = head[0..$-1]; _Val < head1.last;)
>                     head.putBack(head1.getBack());
>                 head.last = _Val;
>             }
>         }
>         while (!tail.isEmpty())
>     }
> }

Steven Schveighoffer wrote:
> "Andrei Alexandrescu" wrote
>> Notice that "a range can't grow" is different from "a range can't be assigned from a larger range". In particular, a range operation can return a range larger than both input ranges. But not larger than their union :o).
> 
> Yes, so every time you add an element you have to update your forward range from the 'all' range so it includes the new element at the end.  Every time you remove an element, you have to update your reverse range from the 'all' range so it excludes the element at the beginning.  Failure to do this results in invalid ranges, which seems to me like a lot more work than simply not doing anything  (in the case of an iterator).  The pitfalls of using ranges for dynamically changing containers might outweigh the advantages that they provide in certain cases.

No, this is incorrect. I don't "have to" at all. I could define the
behavior of range as you mention, or I could render them undefined.
Iterators invalidate anyway at the drop of a hat, so they're none the
wiser. You can't transform a lack of an advantage into a disadvantage.

"Look at this pineapple. It's fresher than the other, and bigger too."

"No, it's about as big. That pineapple sucks."

>>> My belief is that ranges should be the form of input to algorithms, but iterators should be provided for using containers as general data structures.  Similar to how strings are represented by arrays/slices, but iterators (pointers) exist if you need them.
>> If we agree it's better without iterators if not needed, we'd need a strong case to add them. Right now I have a strong case against them.
> 
> I don't need to worry about whether you have them or not, I can always implement them on my own ;)  Really, range/iterator support doesn't require direct support from the compiler (except for builtin arrays), and any improvements made to the compiler to support ranges (such as reference returns, etc) can be applied to iterators as well.
> 
> I think ranges are an excellent representation when a range of elements is needed.  I think a cursor or iterator is an excellent representation when an individual position is needed.
> 
>>> I'll probably move forward with this model in dcollections, I really like the range idea, and in general the view on how ranges are akin to slices. But I also like having access to iterators for other functions.
>> Which functions?
> 
> Functions which take or return a single position.  Such as 'erase the element at this position' or 'find the position of element x'.

I agree. In fact I agreed in my original document, which I quote:
``Coding with ranges also has disadvatages. Some algorithms work
naturally with individual iterators in the "middle" of a range. A
range-based implementation would have to maintain a redundant range
spanning e.g. from the beginning of the container to that middle.''

However, I could meanigfully rewrite std.algorithm to work on ranges
alone. The disadvantage does exist but is minor, For example, find does
not return an iterator. It simply shrinks its input range until the
element is found, or until it is empty. That way you can nicely use the
result of find iteratively.

Range find(alias pred = "a == b", Range, E)(Range haystack, E needle)
{
    alias binaryFun!(pred) test;
    for (; !haystack.isEmpty; haystack.next)
    {
        if (test(haystack.first, needle)) break;
    }
    return haystack;
}

This is quite a few bites smaller than the previous version, which is
now to be found in std.algorithm:

Iterator!(Range) find(alias pred = "a == b", Range, E)(Range haystack, E
needle)
{
    alias binaryFun!(pred) test;
    for (auto i = begin(haystack); i != end(haystack); ++i)
    {
        if (test(*i, needle)) return i;
    }
    return end(haystack);
}

It has two less variables, and VERY importantly, one less type to deal
with. Arguments aired against primitive ranges systematically omit this
important simplification they bring. When you don't weigh in the
advantages, of course all there is to be seen are the disadvantages.

Better yet, when find does return, client code's in better shape because
it doesn't need to compare the result against end(myrange). It can just
test whether it's empty and be done with.

So a newcomer to D2 would have to have an understanding of containers
and ranges. Containers own data. They offer various traversals to crawl
them in the form of ranges. Ranges are generalized slices.

If iterators are thrown into the mix, things get more complex because
iterators are a lower-level primitive, a generalized pointer. So the
newcomer would have to ALSO understand iterators and deal with functions
that require or return either. They'd have to learn how to pair
iterators from ranges and how to extract iterators from ranges (more
primitives). They'd also have to understand when it's better to hold on
to a range (most of the time) versus a naked iterator (seldom and for a
dubious convenience).

I /understand/ there are advantages to iterators. Just don't forget the
cost when discussing them.

I am also sure that if I sat down long enough contemplating my navel I
could come with more examples of iterators=good/ranges=bad. I am also
sure that if I continued doing so I could also figure cases where a
doubly linked-list iterator that "knows" whether it's atBegin or atEnd
could come in handily. In fact how about this imaginary discussion
between Stepanov and his imaginary colleague Tikhonov:

Stepanov: "Here, I have these cool iterators. I can express a great deal
of stuff with them. It's amazing."

Tikhonov: "Ok, I have a doubly-linked list. An iterator is a node in the
list, right?"

S: "Da. Those are bidirectional iterators because they can move in two
directions in the list."

T: "Ok, my first element has prev == NULL and last element has next ==
NULL. Does your iterator know when it's at the begin and at the end of
the list?"

S: "No. You see, you'd have to compare two iterators to figure that out.
Just pass around an iterator to the beginning and end of the list
fragment you're interested in, as you find fit."

T: "That sucks! I want an iterator to move up and down and tell me when
it's at the beginning and at the end, without another stinkin' iterator."

S: "I implemented a great deal of algorithms without needing that. What
algorithms of yours can't work with a comparison instead of atBegin and
atEnd?"

T: "Well, I need to think of it. Maybe some video buffer or something."

S: "That works. You just save the iterator at the beginning of the
sliding window. Then you compare against it."

T: "But I don't like that. I want you to define atBegin and atEnd so I
don't need to carry an extra laggard!"

S: "Then what algorithms would fundamentally rest on that particular
feature?"

T: "No idea. Here, let me look at my navel."

S: "While you do that, let me ask you this. Whatever those algorithms
are, they can't work on a circular list, right?"

T: "I guess not. atBegin is never true for a circular list, unless,
damn, you keep another iterator around to compare with."

S: "So those algorithms of yours would work on a doubly-linked list but
not on a circular list. Are you sure you care for that distinction and
that loss in generality?"

T: "Gee, look at the time. It's Friday evening! Let's go have a beer."


Andrei