on Thu Oct 06 2011, "Stephan T. Lavavej" <stl-AT-exchange.microsoft.com> wrote:
[Phil Endecott]
But in any case, it's not hard to write; just require that T is a type for which *i==value is valid.
What am I missing?
[Dave Abrahams]
You're missing that == should *mean* something.
Why should the algorithm assume any more meaning than it has to?
So that it can guarantee some meaning in the result.
For example, std::equal() does not require symmetry.
The standard specifications should not necessarily be used as a model. They're kind of a mess, and inconsistent.
This is just fine for people comparing a range of T to a range of T, where T == T is symmetric, and makes people comparing a range of X to a range of Y, where X == Y is provided and Y == X has not even been implemented (and X can't be converted to/from Y), super happy.
Yeah, but the specification for std::equal doesn't say that it returns true iff the sequences are equal. And it should. Right now you have to infer that from a bunch of C++ expressions (bits of the implementation which leak out into the specification) and your knowledge about the types involved. It's not a huge leap in this case, but it hurts the ability to think about algorithms at the abstract level, and it's unsustainable as the algorithms grow more complex. Try doing that with is_permutation. Now if you look at the specification for std::search, it says "finds a subsequence of equal values in a sequence." That's awesome! But it can't deliver that unless the value types' "==" operator actually means equality, and that requirement is nowhere to be found. So you might say that this specification imposes the /implicit/ requirement that "==" means equality. And if you look at "includes" in C++11 you'll see ,---- | 1. `true' if is empty or if every element in the range [first1, last1) | | is contained in the range [first2, last2) . Returns `false' otherwise. | | 2. At most `2 * ((last1 - first1) + (last2 - first2)) - 1' comparisons. `---- and that's it. This I like, but it only works if there's an implicit assumption that == means true equality.
You're not even requiring it to be symmetric. Why is it right to test *i==value instead of value==*i?
The algorithm takes (first, last, value), putting the range on the left and the value on the right.
OK, I guess that's one kind of logic. -- Dave Abrahams BoostPro Computing http://www.boostpro.com