[STL]
Why should the algorithm assume any more meaning than it has to?
[Dave Abrahams]
So that it can guarantee some meaning in the result.
That's necessary for something like std::sort(), which needs op<() to have "reasonable" properties. Something like std::lower_bound (and none_of_equal) can and should have extremely weak requirements. [STL]
For example, std::equal() does not require symmetry.
[Dave Abrahams]
The standard specifications should not necessarily be used as a model. They're kind of a mess, and inconsistent.
Sure - but in this case, std::equal()'s behavior is reasonable.
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. 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. Similarly for pred(elem1, elem2). In fact, the algorithm is misnamed - it should be is_bijection(). 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.
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.) STL