<div dir="ltr"><div>I don't have the full thread for context.</div><div><br></div>There is no practical way to test if a given comparison function satisfies a strict-weak ordering or not. The issue is the requirement of transitivity:<div><br></div><div>a < b && b < c => a < c</div><div><br></div><div>Any test would have to ensure that this holds for all triplets in the sequence being sorted (and you would have to verify the other axioms as well).</div><div><br></div><div>The reason why sort can crash if this is violated is because it establishes a sentinel at a partition point and assumes nothing will cross the sentinel - you can bounds check with some additional cost but the ordering is still going to be undefined if this axiom is violated and there is no guarantee a bounds check will catch it.</div><div><br></div><div>There are some tests that can be done for common failures though - for example a common failure of sort is trying to sort a floating point sequence with float or doubles that contains NaNs. You can test for NaNs on such a sequence with an additional linear pass. But it doesn't help if you have a custom comparison that is passed in, that does something like compare the first member of a struct that is of type double.</div><div><br></div><div>There are many pre-conditions in STL (and most any other library interface) that cannot easily be validated.</div><div><br></div><div>Sean</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 14, 2016 at 10:11 PM, Marshall Clow <span dir="ltr"><<a href="mailto:mclow.lists@gmail.com" target="_blank">mclow.lists@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Jan 12, 2016 at 10:27 PM, Yury Gribov via cfe-dev <span dir="ltr"><<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
As for C++11, it has for e.g. srtd::sort:<br>
<br>
"Requires: operator< (for the version with no arguments) or comp (for the version with a comparison argument) defines a strict weak ordering (25.4)."<br>
<br>
which also sounds like UB.</blockquote><div><br></div><div>Exactly correct.</div><div>If your comparison operator does not define a SWO, then you have no guarantees of the results. Crashes are common.</div><div><br></div><div>In principle, I am very much in favor of a checker like this.</div><div>Passing an invalid comparison operator is one of the most common misuses of std::sort.</div><div><br></div><div>I worry about the cost, though.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>-- Marshall</div><div><br></div></font></span></div></div></div>
</blockquote></div><br></div>