Re: [boost] AlRangeExandrescu?

Subject: Re: [boost] AlRangeExandrescu?
From: Andrei Alexandrescu (andrei_at_[hidden])
Date: 2009-07-24 20:47:46

Mathias Gaunard wrote:
> Andrei Alexandrescu wrote:
> 
>> That would limit ranges because there are ranges that are not pairs of 
>> iterators.
> 
> All ranges can be expressed as pairs of iterators, so I hardly see how 
> that limits anything.
> The issue is that expressing a range as a pair of iterators may not 
> always be optimal.
> 
> 
> 
>> You would pass two adjacent ranges, like D's bringToFront (a 
>> generalization of STL's rotate, see 
>> http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html) takes.
> 
> Nice idea, that could work.
> But how can I generate those two adjacent ranges in the first place at 
> reasonable costs? Do ranges requires to provide a constant time 
> "complement" primitive?

There's no such need (a range could define it though).

A design that has a bidirectional iterator walking freely up and down 
between two limits would be difficult to port to ranges. (If the 
iterator is random-access, things are trivial.) Ranges can only shrink, 
they never grow unless assigned from the outside. So when you move one 
direction it would be difficult to grow one range (shrinking the other 
is easy). That design would benefit from letting the iterator 
abstraction exposed.

Another example of an iterator-based design that's not easy to replicate 
with ranges is Boost Multi-Index. (Thanks Emil Dotchevski for pointing 
that out during my talk. (Marshall Clow promised the video will be 
available Real Real Soon Now(tm).)) In Multi-Index, indexes store 
iterators; storing ranges would often waste twice the space for little 
or no benefit.

I'm sure there are other designs that would be similarly problematic. 
That's expected because, again, ranges are a higher level abstraction 
and there's always an inevitable loss. What is encouraging is that most 
iterator-based designs (including STL) benefit when converted to ranges, 
and that ranges simplify matters enough to open the mind to new 
possibilities.

Andrei