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