Re: Baby X is bor nagain

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

Ben Bacarisse <ben@bsb.me.uk> writes:
[...]

On a C language point, I don't think the standard says anything about
sorting with non-order functions like the one above.  Is an
implementation of qsort permitted to misbehave (for example by not
terminating) when the comparison function does not implement a proper
order relation?

>
N1570 7.22.5p4 (applies to bsearch and qsort):
"""
When the same objects (consisting of size bytes, irrespective of
their current positions in the array) are passed more than once to
the comparison function, the results shall be consistent with one
another. That is, for qsort they shall define a total ordering on
the array, and for bsearch the same object shall always compare
the same way with the key.
"""
>
That's a "shall" outside a constraint, so violating it results in
undefined behavior.

I think it should be clearer.  What the "that is" phrase seems to
clarify in no way implies a total order, merely that the repeated
comparisons or the same elements are consistent with one another.  That
the comparison function defines a total order on the elements is, to me,
a major extra constraint that should not be written as an apparent
clarification to something the does not imply it: repeated calls should
be consistent with one another and, in addition, a total order should be
imposed on the elements present.

--
Ben.