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.
-- Dr. Arno Schoedl Â· aschoedl_at_[hidden] Technical Director think-cell Software GmbH Â· Invalidenstr. 34 Â· 10115 Berlin, Germany http://www.think-cell.com Â· phone +49-30-666473-10 Â· toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl Â· Amtsgericht Charlottenburg, HRB 85229
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk