Using std::sort et al. with user-defined comparison routine

Question

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.

Answer 1

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 function f, define a new ordering function f_weak like so:

template <typename T, typename F>
auto f_weak(F comparator)
{
    return [comparator](T a, T b) {
               return comparator(a, b) // true if a <= b
                        && a != b;
    };
}

and then pass f_weak<T>(f) as the last parameter to std::sort. This code is untested, and uses some modern C++ features, but I'm sure you get the gist of it.