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@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229