RFC on range design for D2

Sergey Gromov snake.scaly at gmail.com
Wed Sep 10 11:57:53 PDT 2008


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.


More information about the Digitalmars-d-announce mailing list