[boost] [Iterator][MultiIndex] iterator-specific partition_point-related functions

Subject: [boost] [Iterator][MultiIndex] iterator-specific partition_point-related functions
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-11-18 10:48:47

Hello,

I am posting this again with [Iterator] included in the subject. I am still hoping to raise some interest. If it does not work this time, I will give up, I promise.

Some iterator implementations would benefit from special implementations for partition_point-type functions, in particular lower_bound, upper_bound, equal_range and binary_search. Although they are not able to provide random access, if properly implemented, they offer O(log N) lookup. 

Here are some examples:

- multi-index container ordered index iterators can exploit the red-black tree.
- filter_iterator can exploit random access on the base iterator, and after an element is found, search forward for the next unfiltered element. The efficiency would degrade gracefully with the degree of filtering performed.
- [not in boost] union_iterator, which unifies two underlying sorted ranges, could do the look-up on both ranges independently and then do one final application of the predicate.
- Other boost iterator adaptors would not directly benefit from this scheme, but would be able to pass through to their base_iterator by appropriately wrapping the predicate. So for example, partition_point( transform_iterator( filter_iterator( random_access iterator ))) would still be efficient if filter_iterator keeps most of the elements.

lower_bound, upper_bound, equal_range and binary_search can all be implemented on top of partition_point. So I propose a special base class, partition_point_facade, similar to iterator_facade, which when provided with a member function It::partition_point( It it, Pred pred ), implements the others as free functions. Is there any interest, and possibly willingness to include it into Boost.Iterator?

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