Boost logo

Boost :

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( ... );


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.


Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229

Boost list run by bdawes at, gregod at, cpdaniel at, john at