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@think-cell.com 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