Subject: Re: [boost] [Iterator][MultiIndex] iterator-specificpartition_point-related functions
Date: 2008-11-18 11:27:48
Arno SchÃ¶dl escribiÃ³:
> 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.
> 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?
Although I've commented on this a few days ago, let me restate that
I am very interested in having something like this in Boost. IMHO
the partition approach is a nice addition to the iterator framework,
and fills in the gap by which associative containers have to provide
lookup member functions instead of relying on <algorithm>, an
ugly breach of genericity.
JoaquÃn M LÃ³pez MuÃ±oz
TelefÃ³nica, InvestigaciÃ³n y Desarrollo
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk