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-22 10:35:44

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

I should have said "for counting_iterator<int> or some other fundamental type", by calculating with the bounds.

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

To get a bit more specific, are you suggesting introducing a boost::lower_bound? Do you want it to always forward to boost::partition_point? Or should it by default forward to std::lower_bound, and only be overloaded for those specific iterators for which a custom boost::partition_point is implemented?

I think we agree that we must introduce a default boost::partition_point. How should the customization happen there? Via ADL on partition_point, or again via overloading boost::partition_point?

Or do you want something else? What specifically?

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

If someone does not use 

using std::lower_bound;

in their code and instead calls the boost::lower_bound wrapper, I only see a risk of ambiguity if existing code has its own lower_bound,

a) which has different semantics, so calling our lower_bound found by ADL is wrong. I think the chances for that are pretty remote. Reusing names from std, but giving them different semantics should not have been done in the first place, particularly in large projects where any change is difficult to manage, but which should have code guidelines in place to prevent such name reuse. In small projects, the other function can just be renamed, and the code gets better for it.
 
b) or, the code has overloaded lower_bound for boost iterator types, and thus it is ambiguous which lower_bound is preferred. If the semantics are the same, the reason for the overload was presumably better performance, which we now provide. The extra overload can be removed. Our implementation should be good enough.

I think these scenarios are preferable over the problem that another library ("some_lib") supplies iterators and custom lower_bounds for them. Even if some_lib uses ADL to implement their custom lower_bound, how is a user of both boost and some_lib going to invoke the right lower_bound in generic code? With ADL on lower_bound, that would happen automatically. That's why I like ADL so much (among the choices we have with existing C++).

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