Re: [boost] [Iterator][MultiIndex]iterator-specificpartition_point-relatedfunctions

Subject: Re: [boost] [Iterator][MultiIndex]iterator-specificpartition_point-relatedfunctions
From: David Abrahams (dave_at_[hidden])
Date: 2008-12-25 01:55:51

on Wed Dec 24 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:

>> > I should have said "for counting_iterator<int> or some other fundamental type", by
>> > calculating with the bounds.
>
>> Maybe so, but I'm obviously missing something, because I still can't
>> guess what you have in mind.
>
> counting_iterator<int> lower_bound( counting_iterator<int> begin,
> counting_iterator<int> end, int n ) {
>   if( n<begin ) return begin;
>   else if( n<end ) return counting_iterator<int>(n);
>   else return end;
> }

OK, yes.  It works when the counting iterator is random-access.  This is
not a very significant optimization, IMO, but I see that it is one
nonetheless.

>> > To get a bit more specific, are you suggesting introducing a
>> > boost::lower_bound?  Do you want it to always forward to
>> > boost::partition_point? Or should it by default forward to
>> > std::lower_bound, and only be overloaded for those specific
>> > iterators for which a custom boost::partition_point is implemented?
>
>> My current thinking is:
>>   boost::lower_bound 
>>   -> partition_point (via ADL) 
>>      -> std::lower_bound (by default)
>> Make sense?
>
> Do you mean this?
>
> namespace boost {
>
> template< ... >
> It lower_bound( It begin, It end, T value ) {
>    using boost::partition_point;
>    return partition_point( begin, end, boost::bind( ... ) );
> }
>
> template< ... >
> It partition_point( It begin, It end, Pred pred ) {
>    return std::lower_bound( begin, end, boost::bind( ... ) );
> }
>
> // a custom implementation of partition_point:
> template< ... >
> transform_iterator<It,Func> partition_point(transform_iterator<It,Func> begin,
> transform_iterator<It,Func> end, Pred pred ) {
>    ...
> }

Something like that, yes.

> ... more custom implementations ...
>
> }
>
> Is implementing partition_point by std::lower_bound possible? I remember seeing a
> paper of yours that pointed out that in
>
> template< class It, class T, class Pred )
> lower_bound( It begin, It end, T value, Pred pred )
>
> T must be It::value_type. 

That is no longer the case.
See http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270
Also, see boost/detail/binary_search.hpp, which was introduced precisely
to work around one implementation's strict concept checking.

> Then, how do you do the forwarding? Instead, I suggest
> providing our own implementation of partition_point.

Equivalent.

>> > I think we agree that we must introduce a default
>> > boost::partition_point. How should the customization happen there?
>> > Via ADL on partition_point, or again via overloading
>> > boost::partition_point?
>
>> Inviting users to overload in your namespace is simply not a viable
>> customization approach in general, so ADL is it.
>
> O.k., agreed.
>
> Why do you think ADL is o.k. for customizing boost::partition_point (soon
> std::partition_point, N2666), but not for customizing std::lower_bound? AFAIK, the
> same arguments apply to both.

Because nobody wants to customize lower_bound, upper_bound, equal_range,
and binary_search when they could instead customize partition point
alone.

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