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

Subject: Re: [boost] [Iterator][MultiIndex]iterator-specificpartition_point-relatedfunctions
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-12-19 03:38:57

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

I agree with your scepticism about ADL. But we have to live with the C++ standard we have. 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( ... );

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

Arno

--
Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone [phone] · toll-free (US) [phone]
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229