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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk