RFC on range design for D2

[Bill Baxter]

On Thu, Sep 11, 2008 at 1:45 AM, Andrei Alexandrescu
<SeeWebsiteForEmail at erdani.org> 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.

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".

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
				}
			}
	}

I /think/ that's taking advantage of going both ways on the same
iterator (or at least copies of the same iterator), but the code is a
little hard to read.

Part of my argument here is that it's more natural and requires less
cognitive load to think of things in terms of moving a cursor back and
forth.  So you won't convince me by constructing clever range unions
and differences to achieve the same thing as a simple ++ and -- can
do. :-)

Also a cursor that can go forward and backwards inbetween two limits
is exactly what is easy to do with a doubly linked list.  If you know
how to use a doubly linked list you know how to use my version of
bidir ranges.  That's true in all cases where you are using a
doubly-linked list.  For yours you have to think about how to map what
you want to do onto the operations that are actually available.  To me
that's clearly a greater cognitive load.

Another example is a function that is supposed to put a value back
into its proper sorted place.  Say you had a sorted list and now the
value of one node has been modified.  Write the function that puts
that value back in its rightful place.  The natural way to do it is
with a range that has a cursor pointing to the modified node that can
be moved either back or forward.

Also I see the function "std::advance" is used quite a lot in this
implementation of std::algorithm.  That moves the cursor forwards or
backwards N steps depending on the sign of N.

>>  Your bidir range may be useful (though I'm not really convinced that
>> very many algorithms need what it provides) --  but I think one also
>> needs an iterator that's good at what C++'s bidir iterators are good
>> at, i.e. moving the active cursor backwards or forwards.  I would call
>> your construct more of a "double-headed" range than a bidirectional
>> one.
>
> Oh, one more thing. If you study any algorithm that uses bidirectional
> iterators (such as reverse or Stepanov's partition), you'll notice that
> ALWAYS WITHOUT EXCEPTION there's two iterators involved. One moves up, the
> other moves down. This is absolutely essential because it tells that a
> bidirectional range models all a bidirectional iterator could ever do. If
> you can move some bidirectional iterator down, then definitely you know its
> former boundary so you can model that move with a bidirectional range.

This does seem to be true of a many of the algorithms that use bidirs
in std::algorithm, which did surprise me.  Actually seems to me that
these types of algorithms are only using bidirectional iterators for a
technicality -- because you can't compare a forward iterator and a
reverse iterator.  The bidirectionality of the iterator is not really
material.  One only needs the ++ op for one and the -- op for the
other.  That says to me the name of the range that does these two
things should be something other than "bidirectional", because
bidirectionality is not really the key property.  "Two-headed range"
or "squeeze range" or "pinch range" might be good names.

But anyway, I am convinced that your shrinking range type is useful.

> This is fundamental. Ranges NEVER grow. They ALWAYS shrink. Why? Simple:
> because a range has no idea what's outside of itself. It starts life with
> information of its limits from the container, and knows nothing about what's
> outside those limits. Consequently it ALWAYS WITHOUT EXCEPTION shrinks.

Doesn't seem to be quite so absolute from my perusal of std::algorithm.

--bb