Why Does `std::sort` Crash When the Comparison Function Isn't a Strict '

Why Does std::sort Crash If Comparison Function is Not a Strict Operator "<"?

The provided C code snippet demonstrates a crash while utilizing std::sort due to an incorrect comparison function. As std::sort expects a sorter that satisfies the strict weak ordering rule, let's delve into the issue and its resolution.

In the code, the comparison function for the A struct checks if a is less than or equal to (<=) other.a. However, this violates the strict weak ordering rule.

Strict Weak Ordering

A strict weak ordering defines a relation that is:

• Irreflexive: a cannot be related to itself (a ≱ a).
• Transitive: If a is related to b, and b is related to c, then a is related to c.
• Anti-Symmetric: If a is related to b, and b is related to a, then a is equal to b (a ≈ b).

In the code, the comparison function doesn't satisfy the anti-symmetry property, as it returns true even when a is equal to other.a. This can lead to non-deterministic behavior in std::sort, such as an infinite loop.

Solution

To resolve the issue, the comparison function should be modified to adhere to the strict weak ordering rule by returning true only when a is strictly less than other.a, as shown below:

struct A
{
    bool operator <(const A& other) const
    {
        return a < other.a; // Return true only when a is strictly less than other.a
    }
};

This corrected comparison function ensures that the strict weak ordering rule is observed, enabling std::sort to function as expected without crashing.

The above is the detailed content of Why Does `std::sort` Crash When the Comparison Function Isn't a Strict '. For more information, please follow other related articles on the PHP Chinese website!