on Wed Dec 24 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
I should have said "for counting_iterator<int> or some other fundamental type", by calculating with the bounds.
Maybe so, but I'm obviously missing something, because I still can't guess what you have in mind.
counting_iterator<int> lower_bound( counting_iterator<int> begin, counting_iterator<int> end, int n ) { if( n<begin ) return begin; else if( n<end ) return counting_iterator<int>(n); else return end; }
OK, yes. It works when the counting iterator is random-access. This is not a very significant optimization, IMO, but I see that it is one nonetheless.
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?
My current thinking is: boost::lower_bound -> partition_point (via ADL) -> std::lower_bound (by default) Make sense?
Do you mean this?
namespace boost {
template< ... > It lower_bound( It begin, It end, T value ) { using boost::partition_point; return partition_point( begin, end, boost::bind( ... ) ); }
template< ... > It partition_point( It begin, It end, Pred pred ) { return std::lower_bound( begin, end, boost::bind( ... ) ); }
// a custom implementation of partition_point: template< ... > transform_iterator<It,Func> partition_point(transform_iterator<It,Func> begin, transform_iterator<It,Func> end, Pred pred ) { ... }
Something like that, yes.
... more custom implementations ...
}
Is implementing partition_point by std::lower_bound possible? I remember seeing a paper of yours that pointed out that in
template< class It, class T, class Pred ) lower_bound( It begin, It end, T value, Pred pred )
T must be It::value_type.
That is no longer the case. See http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270 Also, see boost/detail/binary_search.hpp, which was introduced precisely to work around one implementation's strict concept checking.
Then, how do you do the forwarding? Instead, I suggest providing our own implementation of partition_point.
Equivalent.
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?
Inviting users to overload in your namespace is simply not a viable customization approach in general, so ADL is it.
O.k., agreed.
Why do you think ADL is o.k. for customizing boost::partition_point (soon std::partition_point, N2666), but not for customizing std::lower_bound? AFAIK, the same arguments apply to both.
Because nobody wants to customize lower_bound, upper_bound, equal_range, and binary_search when they could instead customize partition point alone. -- Dave Abrahams BoostPro Computing http://www.boostpro.com