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