Pourquoi `std::sort` plante-t-il avec un opérateur inférieur à non strict ?

std::sort Exception avec fonction de comparaison non stricte

Le programme suivant, compilé avec VC 2012, présente un comportement inattendu :

#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;
}

Problème Explication

Le problème se pose car l'opérateur de fonction de comparaison< ne suit pas strictement les exigences de std::sort. Selon la bibliothèque standard C (Sect. 25.3.1.1), std::sort nécessite des fonctions de comparaison qui remplissent la propriété dite « d'ordre faible strict ». Cependant, la fonction de comparaison dans le programme donné permet uniquement de considérer les éléments comme égaux mais pas strictement inférieurs les uns aux autres. Cela peut provoquer une ambiguïté et potentiellement conduire à des boucles infinies dans l'algorithme de tri.

Règle de classement faible stricte

La règle de classement faible stricte stipule que pour une fonction de comparaison '> ;' (également applicable à '<') :

• Si un > b, puis b !&Lt ; a
• Si a >= b et b >= a, alors a == b

Implication pour la fonction de comparaison

Dans le code donné, l'opérateur de fonction de comparaison< viole la règle stricte d'ordre faible car elle autorise les cas où les éléments peuvent être égaux (a == b) mais pas strictement inférieurs les uns aux autres (pas a < b). Ce comportement non strict viole les exigences de std::sort et peut conduire à un comportement indéfini, y compris un crash.

Solution

Pour résoudre le problème, la comparaison la fonction doit être modifiée pour comparer strictement les éléments :

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

Avec cette modification, le programme devrait fonctionner comme prévu sans planter.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!