RFC on range design for D2

[Andrei Alexandrescu]

Bill Baxter wrote:
> But upon further reflection I think it may be that it's just not what
> I would call a bidirectional range.  By that I mean it's not good at
> solving the problems that a bidirectional iterator in C++ is good for.

It's good. I proved that constructively for std.algorithm, which of 
course doesn't stand. But I've also proved it theoretically informally 
to myself. Please imagine an algorithm that bidir iterators do and bidir 
ranges don't.

>  Your bidir range may be useful (though I'm not really convinced that
> very many algorithms need what it provides) --  but I think one also
> needs an iterator that's good at what C++'s bidir iterators are good
> at, i.e. moving the active cursor backwards or forwards.  I would call
> your construct more of a "double-headed" range than a bidirectional
> one.

Oh, one more thing. If you study any algorithm that uses bidirectional 
iterators (such as reverse or Stepanov's partition), you'll notice that 
ALWAYS WITHOUT EXCEPTION there's two iterators involved. One moves up, 
the other moves down. This is absolutely essential because it tells that 
a bidirectional range models all a bidirectional iterator could ever do. 
If you can move some bidirectional iterator down, then definitely you 
know its former boundary so you can model that move with a bidirectional 
range.

This is fundamental. Ranges NEVER grow. They ALWAYS shrink. Why? Simple: 
because a range has no idea what's outside of itself. It starts life 
with information of its limits from the container, and knows nothing 
about what's outside those limits. Consequently it ALWAYS WITHOUT 
EXCEPTION shrinks.


Andrei