
Boost : 
Subject: Re: [boost] Boost.Algorithm design question
From: Dave Abrahams (dave_at_[hidden])
Date: 20111006 22:13:41
on Thu Oct 06 2011, "Stephan T. Lavavej" <stlATexchange.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 higherlevel meaning on the algorithm.
Exactly... no, wait... well, if you believe algorithms are abstractions
then it already had higherlevel 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk