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-20 19:40:21

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

>> But we have no way to provide an implementation of std::lower_bound.  We
>> can only provide an implementation of lower_bound (unqualified).
>
> I think we should first agree on the fundamental question of how to
> provide a specialized implementation of any std algorithm.

Unless std provides the hooks to do so, there is no way -- at least,
there is no way without establishing a name for the algorithm that
is not "std::" qualified.

> I agree with your scepticism about ADL. But we have to live with the
> C++ standard we have. 

Nonetheless there are plenty of techniques available for algorithm
customization.

> The only way I know to implement overloads in
> bulk is using free friend functions in a base class a la
> iterator_facade/boost.operator. Free friend functions always live in
> the same namespace as the class in which they are defined. So to find
> them, we must invoke ADL. I think the only way to avoid ADL would be
> macros (yuck!).
>
> That said, I have nothing against a wrapper for invoking ADL: 
>
> namespace boost {
>
> template< class ItA, class ItB, class Val > // two-template trick from boost::swap to
> avoid ambiguities
> It lower_bound( ItA a, ItB b, Val const& val ) {
> 	using std::lower_bound;
> 	return lower_bound(a,b,val);
> };
>
> };
>
> Then people have the choice of
>
> using std::lower_bound;
> lowerbound( ... );
>
> or
>
> boost::lower_bound( ... );

One problem I have with the above is that the likelihood of ambiguity is
too high, and either technique has the same problem (in the latter case
the ambiguity shows up in the Boost implementation).

>> Unless I'm missing something, I think, in that case, that the
>> fundamental operation is partition_point and not lower_bound or
>> upper_bound.  Can't the latter two be implemented in terms of
>> partition_point?
>
> Yes, lower_bound and upper_bound can always be implemented via
> partition_point. 

In that case I don't think lower_bound itself should be considered an
ADL hook.

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

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

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