Re: [boost] Boost.Algorithm design question

Subject: Re: [boost] Boost.Algorithm design question
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-10-06 05:17:10

on Wed Oct 05 2011, "Stephan T. Lavavej" <stl-AT-exchange.microsoft.com> wrote:

> [Marshall Clow]
>> So, what do people prefer (and why?):
>
>
>> template<typename InputIterator, typename V> 
>> bool none_of_equal ( InputIterator first, InputIterator last, V const &val ) 
>
>> or
>
>> template<typename InputIterator, > 
>> bool none_of_equal ( InputIterator first, InputIterator last,
>> iterator_traits<InputIterator>::value_type const &val )
>
>> In the first case, I think there's (possible) conversion from V to
>> iterator_traits<InputIterator>::value_type each time through the
>> loop.
>> In the second case, there is not.
>
> #1 is better. It follows the STL's conventions (e.g. look at
> std::find()) and permits heterogeneous comparisons.

Sorry, STL.  The other STL's conventions are wrong. :-)

> Consider vector<string> and val being "meow". string is directly
> comparable to const char *, without any conversions or temporaries.

You got lucky this time.

> Even better, consider vector<const char *> and val being a
> string. Here, the element type is still directly comparable to val's
> type, but val's type is not implicitly convertible to the element
> type.

That's cute.  IMO the principled thing to do in that case is to use the
version that takes the additional predicate.

> It is true that #1 can result in O(N) conversions, but that's really
> up to the element/value types involved. Typically, whenever the value
> type is implicitly convertible to the element type, and the element
> type is comparable with itself, a direct comparison between the two
> types could also be provided (as is the case with const char * and
> string), and will be provided when performance is important.
>
> Heterogeneous comparisons are surprisingly popular, and the STL is
> moving to support them better. For example, std::lower_bound() didn't
> support them in C++03, and does in C++11. 

/me realizes he is responsible for this change

But that's *totally* different.

/me fumbles around for the explanation

For the version that uses "<", it's an unintentional side-effect of
making the specification uniform.  The function signature already took
an unconstrained object by reference, and my paper was not trying to
change that.  It just happened to make the /semantics/ of using a type
different from the value type of the sequence meaningful in that case.
It also make the specification *simpler* overall and easier to
understand.

The _purpose_ was to support heterogeneity for the version that uses a
function.  The description in terms of partitioning is a more principled
and generic way to describe the actual requirements of the algorithm.
There was never any intention to promote the use of heterogeneous "<",
which again, doesn't make sense.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com