Re: [boost] Boost.Algorithm design question

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

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

>> Yeah, but the specification for std::equal doesn't say that it returns
>> true iff the sequences are equal.  And it should.
>
> You're trying to impose higher-level meaning on the algorithm. 

Exactly... no, wait... well, if you believe algorithms are abstractions
then it already had higher-level meaning.  An algorithm is not its
implementation in C++.

> Indeed, that's what it's usually used for, but algorithms are more
> powerful when phrased with weaker requirements. Weakness is strength!
>
>> Try doing that with is_permutation.
>
> The phrasing for that would be tricky but the intent would be
> clear. Remove "Requires:: ForwardIterator1 and ForwardIterator2 shall
> have the same value type. The comparison function shall be an
> equivalence relation.", then say that is_permutation(ForwardIterator1
> first1, ForwardIterator1 last1, ForwardIterator2 first2) returns true
> iff a bijection exists from elem1 in [first1, last1) to elem2 in
> [first2, first2 + (last1 - first1)) with elem1 == elem2. 

Exactly, the phrasing gets worse.  Your phrasing isn't even quite right,
but it's close.  Actually, I don't know how to phrase it.  operator==
isn't a bijection.  You have to say something like for each a in
[first1,last1) there exists exactly one b in [first2,last2) such that a
== b.  But then you don't get to say "bijection" :-)

> [first2, first2 + (last1 - first1)) with elem1 == elem2

> Similarly for pred(elem1, elem2). In fact, the algorithm is misnamed -
> it should be is_bijection().

Shouldn't is_bijection be a predicate on a function?  I think "bijection
exists" would be closer, but that's not even quite right.  The fact that
you can't come up with a good name for this broader function should tell
you something.

> The current rules forbid asking whether a vector<const char *> is a
> "permutation" of a vector<string>. But the actual algorithm is totally
> fine with that.

Yeah, and that was the basis on which I expanded lower_bound et al.

>> Now if you look at the specification for std::search, it says "finds a
>> subsequence of equal values in a sequence."  That's awesome!
>
> It would be better as an informative note - the requirements in
> [alg.search]/2 are already perfect. (In particular, they say X == Y
> and do not require Y == X to compile.)

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