RFC on range design for D2

Sergey Gromov snake.scaly at gmail.com
Wed Sep 10 11:32:00 PDT 2008


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.


More information about the Digitalmars-d-announce mailing list