Why will std::sort crash if the comparison function is not as operator

Question

The following program is compiled with VC++ 2012.

#include <algorithm>

struct A
{
    A()
        : a()
    {}

    bool operator <(const A& other) const
    {
        return a <= other.a;
    }

    int a;
};

int main()
{
    A coll[8];
    std::sort(&coll[0], &coll[8]); // Crash!!!
}

If I change return a <= other.a; to return a < other.a; then the program runs as expected with no exception.

Why?

The comparator for `std::sort` requires a strict weak ordering, which `<=` does *not* supply. — WhozCraig, Aug 17 '13 at 17:48
You should write a(0) for the A ctor... but it does not crash here anyways! — László Papp, Aug 17 '13 at 17:49
@WhozCraig: The default constructor initializes them to zero. — GManNickG, Aug 17 '13 at 17:49
@GManNickG, no, it does not. Not deterministically, that is. — László Papp, Aug 17 '13 at 17:51
@LaszloPapp: Yes it does. It value-initializes `a()` (that's what `a()` means), which for `int` means 0. — GManNickG, Aug 17 '13 at 17:52
@LaszloPapp: http://stackoverflow.com/questions/14259602/default-values-in-c-initializer-lists — GManNickG, Aug 17 '13 at 17:58
@LaszloPapp a dissection of value-initialization vs. default initialization can also be found [here](http://stackoverflow.com/questions/14829158/default-value-of-a-function-pointer-in-c), though as a pointer rather than an `int`. — WhozCraig, Aug 17 '13 at 18:02
GManNickG: thanks! That is what I also guessed after your initial write, but I thought it is better to double check with the standard, but I did not have enough time to open it up. :) By the way, it is off-topic, but I think it makes more sense to be explicit, and initialize it to zero explicitly. — László Papp, Aug 17 '13 at 18:06

score 37 · Accepted Answer · edited May 23 '17 at 11:53

37

std::sort requires a sorter which satisfies the strict weak ordering rule, which is explained here

So, your comparer says that a < bwhen a == b which doesn't follow the strict weak ordering rule, it is possible that the algorithm will crash because it'll enter in an infinite loop.

edited May 23 '17 at 11:53

Community

1
1

answered Aug 17 '13 at 17:53

xorguy

2,594
1
16
14

6

+1 This states the requirements of `std::sort`'s comparator well. I would follow this with using `std::sort(std::begin(coll), std::end(coll));` if your compiler is compliant with C++11 (and the OPs *is* compliant; VS2012). If you ever change the dimensions of your array, or instead use any of the standard containers, you'll be glad you did. – WhozCraig Aug 17 '13 at 18:04
Entering an infinite loop should just cause it to get stuck. Instead it dumps core. Why? – btilly Aug 17 '13 at 21:02
1

@btilly I think because `std::sort` uses a recursive algorithm which will cause a stack overflow in case of an infinite loop. – xorguy Aug 17 '13 at 21:17
1

You'd have to get into specifics of what it checks, but the standard sort routines are intended to run very, very fast, so they don't check everything you do to see if it's okay, they just rely on it. If your comparisons are returning impossible results then impossible things are going to happen -- say it's got the results of some comparison and it's using that as an index for where to look, only it "knows" what values are possible and "knows" the resulting reference will be in valid storage so it just fetches it. Kaboom: SIGSEGV with any luck. With bad luck, it'll silently hose your data. – jthill Aug 18 '13 at 02:16

score 10 · Answer 2 · edited Jun 20 '20 at 09:12

The answer for xorguy is pretty good.

I would just add some quote from the standard :

25.4 Sorting and related operations [alg.sorting]

For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values.

The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering.

So xorguy explains it very well : You comp function says that a < b when a == b which doesn't follow the strict weak ordering rule...

score -1 · Answer 3 · answered Feb 21 '20 at 06:38

The problem with your code is that you are accessing invalid memory. Code

coll[8]

trying to access the element after the last array element (the last element index is 7). I would suggest using std::array instead plain C arrays.

std::array<A, 8> a;

// fill it somehow

std::sort(a.begin(), a.end());

Why will std::sort crash if the comparison function is not as operator

3 Answers3

Linked

Related