RFC on range design for D2

[Andrei Alexandrescu]

Sergey Gromov wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
>> Sergey Gromov wrote:
>>> Bill Baxter <wbaxter at 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