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

Subject: Re: [boost] [Iterator][MultiIndex]iterator-specificpartition_point-relatedfunctions
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-12-29 09:53:17

> 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), and
- filter_iterator based on any random-access iterator (by exploiting the random-access property of the unfiltered range).

transform_iterator, indirect_iterator, reverse_iterator, and shared_container_iterator partition_points can be implemented such that any performance gain of the underlying iterator's partition_point is preserved.

std library implementors could write a fast partition_point for std::set/multiset iterators, but this requires implementation knowledge, so we cannot do it in boost.

Arno

--
Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone [phone] · toll-free (US) [phone]
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229