on Mon Dec 22 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
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.
Maybe so, but I'm obviously missing something, because I still can't guess what you have in mind.
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?
My current thinking is: boost::lower_bound -> partition_point (via ADL) -> std::lower_bound (by default) Make sense?
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. -- Dave Abrahams BoostPro Computing http://www.boostpro.com