Re: [boost] [Iterator][MultiIndex]iterator-specificpartition_point-relatedfunctions

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