RFC on range design for D2

[Andrei Alexandrescu]

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?

Andrei