In the evaluator of a custom language, I would like to replace our own sort routines with std::sort
or other routines, possibly tbb::parallel_sort
. The problem is that we allow users of the language to supply their own comparison routine, and in the implementations I have tried, std::sort
does not take kindly to routines that fail to be a strict order. In particular, it quickly starts looking at “elements” outside the iterator range to sort.
I assume that if I put an indirection layer on top of the iterators, I could avoid that by using virtual sentinels, but there is no reason to assume that the resulting calls would necessarily ever terminate.
So, given a black box bool f(widget const &a, widget const &b)
and a non-user-controlled total order operator<(widget const &a, widget const &b)
, what would be the minimal amount of calls I would need to make to get a sort call that does terminate and that does order according to f
if that is, in fact, an order? It looks to me like the following should work, but I am hoping that I could get by with fewer calls to f
by some clever method, possibly remembering previous comparison calls:
bool f_stabilized(widget const &a, widget const &b) {
bool fab = f(a, b);
bool fba = f(b, a);
return (fab != fba) ? fab : (a < b);
}
Would it be reasonable to start out by just calling f
and only after seeing n^2 calls for a list of length n to fall back to such a “stabilized” version? I realize that there is no reason to assume the result would be correctly ordered and I would need to start over from the beginning with such a wrapper.
std::sort
as a drop in.std::sort
is that? I've had my share of bugs in comparison operators, but the only think I've ever got fromstd::sort
was an assertion, never segfault and never endless loop. True, you don't want assertion either.std::sort
used by clang on OS X 10.6 does, I’ve seen it in a debugger. (Who would use strict quick sort down to one-element arrays, anyway?) The low-level routines where that happens aptly haveunchecked
in their names and do things likewhile (*left < foo) --left;
(quoted from memory, certainly wrong variable names). That runs out of bounds if your<
routine actually is a<=
operation.