On Mon, 17 Jul 2023, Richard Biener wrote:
> > > > > OK. Btw, while I didn't spot this during review I would appreciate > > > > > if the code could use vec.[q]sort, this should work with a lambda as > > > > > well I think. > > > > > > > > That was my first use, but that hits > > > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99469 > > > > > > That is not hitting PR 99469 but rather it means your comparison is not > > > correct for an (unstable) sort. > > > That is qsort comparator should have this relationship `f(a,b) == !f(b, > > > a)` and > > > `f(a,a)` should also return false. > > > > I'm using the standard std::pair comparator which indicates that f(a,a) is > > true, > > https://en.cppreference.com/w/cpp/utility/pair/operator_cmp > > > > > If you are running into this for qsort here, you will most likely run > > > into issues > > > with std::sort later on too. > > > > Don't see why or how. It needs to have a consistent relationship which > > std::pair > > maintains. So why would using the standard tuple comparator with a standard > > std::sort cause problem? > > At least for > > return left.second < right.second; > > f(a,a) doesn't hold. Note qsort can end up comparing an element to > itself (not sure if GCCs implementation now can). (it cannot but that is not important here) Tamar, while std::sort receives a "less-than" comparison predicate, qsort needs a tri-state comparator that returns a negative value for "less-than" relation, positive for "more-than", and zero when operands are "equal". Passing output of std::pair::operator< straight to qsort is not correct, and qsort_chk catches that mistake at runtime. std::sort is not a stable sort and therefore can cause code generation differences by swapping around elements that are not bitwise-identical but "equal" according to the comparator. This is the main reason for preferring our internal qsort, which yields same results on all platforms. Let me also note that #include <algorithm> is pretty heavy-weight, and so I'd suggest to avoid it to avoid needlessly increasing bootstrap times. Alexander
