Re: [boost] Boost.Algorithm design question

Subject: Re: [boost] Boost.Algorithm design question
From: Stephan T. Lavavej (stl_at_[hidden])
Date: 2011-10-06 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 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