Boost logo

Boost :

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 <> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at