Boost logo

Boost :

Subject: Re: [boost] [Iterator][MultiIndex] iterator-specificpartition_point-related functions
From: joaquin_at_[hidden]
Date: 2008-11-18 11:27:48

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at