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.
Best Answer
Your question seems to boil down to whether or not C++'s
std::sort
can be used with comparison functions that do not behave like the<
operator. Operator<
is a strict weak order, not a total order. Any container or algorithm in the C++ standard library that depends on operator<
assume that it forms a strict weak ordering, and if you violate that assumption then havoc can ensue (as you've seen.) So, to bluntly answer the question in your title,std::sort
works absolutely fine with custom comparator routines, but those custom routines must behave properly.As for how to generate a proper ordering for
std::sort
given a possible total ordering, you might try the following. Given a custom ordering functionf
, define a new ordering functionf_weak
like so:and then pass
f_weak<T>(f)
as the last parameter tostd::sort
. This code is untested, and uses some modern C++ features, but I'm sure you get the gist of it.