Re: [boost] Boost.Algorithm design question

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

on Thu Oct 06 2011, "Phil Endecott" <spam_from_boost_dev-AT-chezphil.org> wrote:

> Dave Abrahams wrote:
>> I don't think you can evaluate these choices just by looking at the
>> implementations.  Before anyone else votes option 1, I'd like to see
>> somebody write the description of the algorithm, including the concept
>> requirements.
>
> Well we can start by copying what the experts wrote for std::find,
> can't we?  

Who are "the experts?"  The specification that we have in the standard
library is not current best practice when it comes to Generic
Programming.  I'm not sure who crafted the language, but it's not what
we should do today.

> For the non-predicate version it just says "Returns: The first
> iterator i in the range [first,last) for which *i==value holds"
> (n3242).  

Exactly, a pile of syntax.

> none_of_equal could be written in the same style.  But you seem to
> want something different than that; I guess that you want to add a
> requirement on the type of the value, right?  

No, I want to avoid a requirement by encoding it into the function
signature.

> If so, why do you want that even though it wasn't deemed necessary for
> the standard?  

See above.

> But in any case, it's not hard to write; just require that T is a type
> for which *i==value is valid.
>
> What am I missing?

You're missing that == should *mean* something.  You're not even
requiring it to be symmetric.  Why is it right to test *i==value instead
of value==*i?

on Thu Oct 06 2011, lcaminiti <lorcaminiti-AT-gmail.com> wrote:

> Dave Abrahams wrote:
>> 
>
>> on Thu Oct 06 2011, lcaminiti <lorcaminiti-AT-gmail.com> wrote:
>> 
>>> Dave Abrahams wrote:
>>>> 
>>>> I don't think you can evaluate these choices just by looking at the
>>>> implementations.  Before anyone else votes option 1, I'd like to see
>>>> 
>>>
>>> Well, I'm not so sure I like option 1 anymore... if option 1 was an
>>> oversight in STL then there is no sense in perpetuating the specification
>>> error in Boost.Algorithm (perhaps Boost.Algorithm should then go with
>>> option
>>> 2 and explain the rationale of why it's different than what STL does for
>>> example with std::find).
>>>
>>>> somebody write the description of the algorithm, including the concept
>>>> requirements.  With option 2, we know that == has to be an equivalence
>>>> relation.  The semantics in option 1 are a lot fuzzier.
>>>> 
>>>
>>> Good point! I'll try to start :)
>>>
>>> template< typename Iter, typename Val >
>>>     requires
>>>         InputIterator<Iter>, 
>>>         EqualityComparable&lt;iterator_traits&lt;Iter&gt;::value_type,
>>> Val>
>>> bool none_of_equal ( Iter first, Iter last, Val const& val ) ; // option
>>> 1a
>> 
>> What you failed to do here was to describe the semantic requirements on
>> EqualityComparable&lt;A,B&gt;, where A != B.
>> 
>
> I see, how about the semantic of EqualityComparable&lt;A, B&gt; with A != B
> is up for discussion :)
>
> Here's a (funny) way I could satisfy the EqualityComparable&lt;A, B&gt;
> requirement:
>
> #include <vector>
> #include <algorithm>
>
> struct orange {
>     int weight;
> };
>
> struct apple {
>     int weight;
> };
>
> bool operator== ( orange const& l, apple const& r )
>     { return l.weight == r.weight; } // comparing apples with oranges?!
>
> int main ( ) {
>     std::vector<orange> v(2);
>     std::find(v.begin(), v.end(), apple());
>     return 0;
> }
>
> No type conversion, EqualityComparable&lt;A, B&gt; is some sort of
> equivalence that can be defined among the different types without converting
> them into one another... isn't that confusing :)
>
> I am starting to find option 1 confusing... (like the example above). Maybe
> is best to go with option 2 for the _equal functions requiring the types to
> be the same because that's the commonly understood semantic of ==. For
> comparing apples with oranges (and other strange things), we can use the
> predicate version of the algorithms.
>
> --Lorenzo
>
> --
> View this message in context: http://boost.2283326.n4.nabble.com/Boost-Algorithm-design-question-tp3876424p3879948.html
> Sent from the Boost - Dev mailing list archive at Nabble.com.
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>

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