Re: [boost] [MultiIndex] STL algorithmsupport formulti_index_containers

Subject: Re: [boost] [MultiIndex] STL algorithmsupport formulti_index_containers
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-11-14 04:40:10

> That would be a nice extension mechanism. Maybe you can write a short 
> description of the
> whole scheme so as to raise interest in the list.

So here we go: 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.

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