Re: [boost] [Iterator][MultiIndex] iterator-specificpartition_point-related functions

Subject: Re: [boost] [Iterator][MultiIndex] iterator-specificpartition_point-related functions
From: David Abrahams (dave_at_[hidden])
Date: 2008-11-19 18:27:59

on Tue Nov 18 2008, joaquin-AT-tid.es wrote:

> 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.

a. that all sounds very interesting
b. I'd like to see more detail
c. I probably can't absorb it now, though; I'm buried under a deadline
   at the moment.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com