Arno Schödl escribió:
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. [...] 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