Boost logo

Boost :

Subject: Re: [boost] [Iterator][MultiIndex]iterator-specificpartition_point-relatedfunctions
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-12-30 11:06:00

Argh. There is a problem with implementing boost::lower_bound/upper_bound. The Dinkumware std library as in MSVC 9 makes unqualified calls to lower_bound/upper_bound in their implementation of equal_range, probably with the intent of letting people ADL-overload them. I read somewhere that this is now considered a defect. The fix in boost::swap for this problem is equivalent to defining boost::lower_bound as

template< class It, class ItR /*extra template*/, class Val >
It lower_bound(It itBegin,ItR itEnd,Val const& x);

The extra template parameter ensures that std::lower_bound is preferred over the then-weaker boost::lower_bound, avoiding ambiguity. But at the same time, IMO it would be nice to have range implementations of boost::lower_bound et. al., which among others have the signature

template<class Rng, class Val, class BinPred>
typename boost::range_iterator<const Rng>::type lower_bound(Rng const& rng,Val const& x,BinPred pred);

creating ambiguity.

Without the fix for Dinkumware, there is no ambiguity, because when the iterator implementation is invoked, both iterators have the same type, so the iterator implementation is preferred. IMO, it is pretty safe to assume that for calls with range, Rng and Val won't have the same type.

I see the following solutions:

a) different name for lower_bound(range). For good reason, Boost.RangeEx already named all range algorithms like their iterator counterparts, which is intuitive. I would hate to make an exception for lower_bound.
b) forgo boost::lower_bound/upper_bound and ADL-overload std::lower_bound/upper_bound. Pretty big design change as well, would basically go back to partition_point_facade to provide bulk ADL overloads.
c) put boost::lower_bound into a different namespace to shield it from ADL
d) Hope that nobody mixes MSVC std::equal_range with boost partition_point algorithms.
e) make Dinkumware fix their library:-)

I think c) is the least-bad option. Any more ideas/opinions?


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