
Boost : 
Subject: Re: [boost] Boost.Algorithm design question
From: Stephan T. Lavavej (stl_at_[hidden])
Date: 20111006 21:38:49
[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 higherlevel 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk