Warum stürzt „std::sort' mit einem nicht strikten Less-Than-Operator ab?

std::sort-Ausnahme mit nicht strikter Vergleichsfunktion

Das folgende Programm, das mit VC 2012 kompiliert wurde, zeigt unerwartetes Verhalten:

#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 Erläuterung

Das Problem entsteht, weil der Vergleichsfunktionsoperator< hält sich nicht strikt an die Anforderungen von std::sort. Laut der C-Standardbibliothek (Abschn. 25.3.1.1) erfordert std::sort Vergleichsfunktionen, die die sogenannte „Streng schwache Ordnung“-Eigenschaft erfüllen. Die Vergleichsfunktion im gegebenen Programm ermöglicht jedoch nur, dass Elemente als gleich, aber nicht streng kleiner als einander betrachtet werden. Dies kann zu Mehrdeutigkeiten führen und möglicherweise zu Endlosschleifen im Sortieralgorithmus führen.

Strenge schwache Ordnungsregel

Die strikte schwache Ordnungsregel besagt, dass für eine Vergleichsfunktion '> ;' (gilt auch für '<'):

• Wenn ein > b, dann b !< a
• Wenn a >= b und b >= a, dann a == b

  Implikation für die Vergleichsfunktion

  Im angegebenen Code ist der Vergleichsfunktionsoperator< verstößt gegen die strenge Regel der schwachen Ordnung, da sie Fälle zulässt, in denen Elemente gleich sein können (a == b), aber nicht streng kleiner als einander sein können (nicht a < b). Dieses nicht strikte Verhalten verstößt gegen die Anforderungen von std::sort und kann zu undefiniertem Verhalten, einschließlich eines Absturzes, führen.

  Lösung

  Um das Problem zu beheben, der Vergleich Die Funktion sollte geändert werden, um Elemente strikt zu vergleichen:

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

  Mit dieser Änderung sollte das Programm wie erwartet ohne Absturz laufen.

  Das obige ist der detaillierte Inhalt vonWarum stürzt „std::sort' mit einem nicht strikten Less-Than-Operator ab?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!