Re: [boost] AlRangeExandrescu?

Subject: Re: [boost] AlRangeExandrescu?
From: Andrei Alexandrescu (andrei_at_[hidden])
Date: 2009-07-27 09:41:29

Andrew Bromage wrote:
> Andrei Alexandrescu <andrei <at> metalanguage.com> writes:
> 
>> 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.
> 
> I don't see a problem with this case.  The limits are a range, and the
> internal bidirectional iterator is a subrange of that range.  There's
> no reason why a subrange couldn't be allowed to grow since we know its
> enclosing range.
> 
>> Another example of an iterator-based design that's not easy to replicate 
>> with ranges is Boost Multi-Index.
> 
> Right.  Suffix arrays are a similar case (indeed, suffix arrays can be
> represented straightforwardly with Boost.MultiIndex).
> 
> However, I suspect that the overwhelming majority of uses of
> Boost.MultiIndex are better thought of as permutations rather than
> a containers-of-iterators.  If there was an abstract notion of
> permutation that was just as high-level as ranges, most of these
> problems may go away.
> 
> I say "most".  I've used a containter-of-iterators to represent
> inverted indexes, and they are definitely not permutations.

Incidentally I've implemented an inverted index as a random-access range 
of input ranges, and found it an extremely satisfying design. Probably 
it's the best range-based design I put together so far.

The random-access range is maintained as a binary heap so you can always 
extract the smallest entity from the inverted index. You popFront that 
entity from the top inverted list and then reestablish the heap property 
if needed. Doing that is cheap because you swap input ranges (small). 
Whenever one of the inverted lists gets exhausted, it is eliminated from 
the random-access range. The search ends when the random-access range is 
exhausted.

Andrei