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