Boost logo

Boost :

Subject: Re: [boost] [Iterator][MultiIndex]iterator-specificpartition_point-relatedfunctions
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-12-24 08:15:35

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

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

... 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. Then, how do you do the forwarding? Instead, I suggest providing our own implementation of partition_point.

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


Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229

Boost list run by bdawes at, gregod at, cpdaniel at, john at