Re: [boost] Boost.Algorithm design question

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

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

> [Phil Endecott]
>> 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?
>
> [Dave Abrahams]
>> You're missing that == should *mean* something.
>
> Why should the algorithm assume any more meaning than it has to?

So that it can guarantee some meaning in the result.

> For example, std::equal() does not require symmetry. 

The standard specifications should not necessarily be used as a model.
They're kind of a mess, and inconsistent.

> This is just fine for people comparing a range of T to a range of T,
> where T == T is symmetric, and makes people comparing a range of X to
> a range of Y, where X == Y is provided and Y == X has not even been
> implemented (and X can't be converted to/from Y), super happy.

Yeah, but the specification for std::equal doesn't say that it returns
true iff the sequences are equal.  And it should.  Right now you have to
infer that from a bunch of C++ expressions (bits of the implementation
which leak out into the specification) and your knowledge about the
types involved.  It's not a huge leap in this case, but it hurts the
ability to think about algorithms at the abstract level, and it's
unsustainable as the algorithms grow more complex.  Try doing that with
is_permutation.

Now if you look at the specification for std::search, it says "finds a
subsequence of equal values in a sequence."  That's awesome!  But it
can't deliver that unless the value types' "==" operator actually means
equality, and that requirement is nowhere to be found.  So you might say
that this specification imposes the /implicit/ requirement that "=="
means equality.

And if you look at "includes" in C++11 you'll see

,----
| 1.  `true' if  is empty or if every element in the range [first1, last1)
| 
|    is contained in the range [first2, last2) .  Returns `false' otherwise.
| 
| 2.  At most `2 * ((last1 - first1) + (last2 - first2)) - 1' comparisons.
`----

and that's it.  This I like, but it only works if there's an implicit
assumption that == means true equality.

>> You're not even requiring it to be symmetric.
>> Why is it right to test *i==value instead of value==*i?
>
> The algorithm takes (first, last, value), putting the range on the
> left and the value on the right.

OK, I guess that's one kind of logic.

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