6

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.

11
  • "The problem is that we allow users of the language to supply their own comparison routine, and (...) std::sort does not take kindly to routines that fail to be a strict order." Okay, but what requirements on comparison routines do you impose for your users to satisfy? If you require strict ordering and your API users fail to provide it, it's outside of the scope of your code to try and fix it.
    – Xion
    Jan 3, 2014 at 17:00
  • @Xion If the comparison routine is bad, I’m fine with not guaranteeing any kind of order. But I’m certainly not fine with crashing the interpreter with a segfault, which is what we’d currently get trying to use std::sort as a drop in. Jan 3, 2014 at 19:53
  • What implementation of std::sort is that? I've had my share of bugs in comparison operators, but the only think I've ever got from std::sort was an assertion, never segfault and never endless loop. True, you don't want assertion either.
    – Jan Hudec
    Jan 3, 2014 at 20:00
  • Nor can I imagine an implementation of sort that would run out of bounds on invalid comparison function. Normal implementation of either quick sort, merge sort nor heap sort can't do that.
    – Jan Hudec
    Jan 3, 2014 at 20:03
  • Well, the 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 have unchecked in their names and do things like while (*left < foo) --left; (quoted from memory, certainly wrong variable names). That runs out of bounds if your < routine actually is a <= operation. Jan 3, 2014 at 21:13

1 Answer 1

2
+50

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.

3
  • Thanks, but actually, my question was if someone saw a way to encapsulate some comparator routine which is not guaranteed to be a weak order at all, such that std::sort is guaranteed to terminate and not crash. I guess the answer is no … (BTW, I do not understand the name f_weak you suggest. Shouldn't that be f_strict instead?) Jan 9, 2014 at 8:12
  • Sorry I guess I misunderstood your question. Yeah the answer is pretty much: use a strict weak ordering relation or expect the unexpected. As for the name f_weak, I called it that to express that it converts a total order into a weak order. I suppose there are plenty of more descriptive names however ;)
    – bstamour
    Jan 9, 2014 at 16:30
  • Sorry, I am not sure what terminology you use. In mathematics, a total order is a weak order, no conversion necessary. Actually, there are (at least?) two meanings of “weak order”: A non-strict order (which is exactly what your utility converts from, to a strict order), or a partial order such that incomparability is transitive – which is what I assumed you mean, since you talk about “strict weak order”. Not that I see how to even pass one to std::sort, since it needs to be expressed with a bool return type. Jan 10, 2014 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.