Subject: Re: [boost] [Iterator][MultiIndex]iterator-specificpartition_point-relatedfunctions
From: David Abrahams (dave_at_[hidden])
Date: 2008-12-29 10:03:43
on Mon Dec 29 2008, Arno SchÃ¶dl <aschoedl-AT-think-cell.com> wrote:
>> OK, but for which iterator can we implement an optimized partition_point
>> that works for arbitrary predicates? I thought the point of
>> "specializing" partition_point was to be able to do something smart with
>> iterators over sorted values (e.g. something like std::set iterators)
> partition_point performance improves from O(N) to O(log N) for
> - Boost.MultiIndex ordered index iterators (by exploiting the
> red-black tree),
OK, I see it now. Sorry for being dense.
The predicate is required to partition the range, so it can work.
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk