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-22 12:45:54

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

>> > There are some (albeit a little contrived) cases such as
>> > couting_iterator, where lower_bound and upper_bound can be
>> > implemented faster ( O(1) ) than partition_point,
>
>> How so?
>
> 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.

>> > so to throw out lower_bound/upper_bound altogether and always
>> > replace them with a wrapper around partition_point seems very
>> > heavy-handed to me.
>
>> Nobody's talking about throwing them out.  They make good sense as
>> high-level algorithms.  However, I don't believe they should be
>> customized directly.  Maybe partition_point should be customized, and
>> exactly how to do that is a possible subject for discussion.
>
> 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?

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

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