Why Does `std::sort` Crash with a Non-Strict Less-Than Operator?

std::sort Exception with Non-Strict Comparison Function

The following program, compiled with VC 2012, exhibits unexpected behavior:

#include <algorithm>

struct A {
    int a;
    bool operator<(const A& other) const {
        return a <= other.a; // Potential issue
    }
};

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

Problem Explanation

The issue arises because the comparison function operator< does not strictly follow the requirements of std::sort. According to the C Standard Library (Sect. 25.3.1.1), std::sort requires comparison functions that fulfill the so-called "strict weak ordering" property. However, the comparison function in the given program only allows elements to be considered equal but not strictly less than each other. This can cause ambiguity and potentially lead to infinite loops in the sorting algorithm.

Strict Weak Ordering Rule

The strict weak ordering rule states that for a comparison function '>' (also applicable to '<'):

• If a > b, then b !< a
• If a >= b and b >= a, then a == b

  Implication for the Comparison Function

  In the given code, the comparison function operator< violates the strict weak ordering rule because it allows for cases where elements can be equal (a == b) but not strictly less than each other (not a < b). This non-strict behavior violates the requirements of std::sort and can lead to undefined behavior, including a crash.

  Solution

  To fix the issue, the comparison function should be modified to strictly compare elements:

  struct A {
      int a;
      bool operator<(const A& other) const {
          return a < other.a; // Strict comparison
      }
  };

  With this modification, the program should run as expected without crashing.

  The above is the detailed content of Why Does `std::sort` Crash with a Non-Strict Less-Than Operator?. For more information, please follow other related articles on the PHP Chinese website!