Pritam_19's blog

Exploring std::sort
By Pritam_19, history, 4 months ago, In English

Recently, I was solving this problem : 2219C - Coloring a Red Black Tree While writing the solution, I encountered a runtime error with my submission 377542151.

After trying to find out the bug for 30 mins I finally got the error. I have written a decent amount of C++ but this is the first time I have encountered a runtime error caused by std::sort

The exact problem lies in this part of the code : 

    sort (tree[u].adj.begin(), tree[u].adj.end(), [&tree](int a, int b) {
        return ((tree[a].exp0 - tree[a].exp1) <= (tree[b].exp0 - tree[b].exp1));
    });

while it looks pretty normal the bug is caused by the use of <= in std::sort while investigating I found out that there are some properties that must be satisfied while using std::sort

  • The comparator must obey strict weak ordering i.e compare(A, A) must return false
  • If compare(A, B) returns true, compare(B, A) must return false.
  • If compare(A, B) returns true, compare(B, C) returns true, then compare(A, C) must also be true.

While the last point seems obvious, the other 2 are important findings.

How does it cause the segfault?

Quicksort partitions the array using two pointers moving toward each other. The pointers stop moving when they hit an element equal to the pivot, allowing the algorithm to swap them. This happens because a valid < comparator returns false when comparing two equal elements, acting as a brake.

By using <=, my comparator returned true when it hit elements equal to the pivot. The pointer never hit the brake.

Boom—Segmentation Fault.

Don't downvote bcz it's a common thing to know as I DID NOT KNOW ABOUT IT ! ( T_T )

  • Vote: I like it
  • +52
  • Vote: I do not like it

»
4 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

https://codeforces.me/blog/entry/70237

→ Reply
»
4 months ago, hide # |
← Rev. 3  
Vote: I like it +11 Vote: I do not like it

In other words, the binary operation (comparator) must be irreflexive, asymmetric, and transitive. (Technically it also needs to have transitivity of incomparability/equivalency.)

→ Reply
»
4 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

I'd recommend std::ranges::sort(), available in C++20 and later.

ranges::sort() lets you pass a vector (actually a random-access range) instead of a pair of iterators. Also it supports projection; projection applies a transformation on each value and the sorter uses the transformed values instead of the raw values.

With these, your code would become:

ranges::sort(tree[u].adj, {}, [&tree](int a) {
        return tree[a].exp0 - tree[a].exp1;
    });

(The second argument is the comparator, and the default comparator is good in this case.)

→ Reply
  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it +13 Vote: I do not like it

    I don't recommend it. It's harder to read, requires extra skill to learn and doesn't fix anything that's broken in competitions except typing out small chunks of code faster once you're really used to typing out those particular chunks. A pair of random access iterators already describes a random access range and that range be nicely customised. Stacking multiple operations into one line makes it less obvious what's happening and harder to debug. Sorting pairs (compared value, id) is often useful. Just because there's a newer way to do something doesn't mean it's always a better way and has to be applied across all code from now on.

    → Reply
»
4 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

I mean, if the latter 2 properties are not true for your sort comparator you should not use it.

→ Reply
»
4 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

There's actually one more condition:

Define equiv(A, B) as !compare(A, B) && !compare(B, A). Then, if equiv(A, B) && equiv(B, C) is true, equiv(A, C) should also be true.

→ Reply
»
4 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

I don't know much about C++ but I've had the same problem long ago. Surely, the main lesson you should take out of this situation is that you sould always make sure that your comparator satisfies the conditions you mentioned. However, I also noticed the following interesting property: in situations like this when you get runtime error because of std::sort, replacing it with std::stable_sort gets rid of RE. I don't know if it always works but it worked every time I encountered this problem. This is definitely not a good idea to do this! Please don't! And I don't know why it works. Please see it as a fun fact, not a piece of advice. Here is your code with std::sort replaced with std::stable_sort getting AC: 377751788

→ Reply
  • »
    »
    4 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it -8 Vote: I do not like it

    I researched a bit into it.while std::sort is mainly built on quicksort, std::stable_sort primarily is built on mergesort. The bug that causes runtime error is very specific to quicksort in a specific step. Moreover, stable_sort ensures that the order of similar elements remain same as the order in the original array whereas std::sort does not. Also, as stable_sort uses mergesort, it requires O(n) memory as well. That's more or less the difference between both

    → Reply