Comparatorul pentru sort în C++: greșeli frecvente
Scrie un comparator strict pentru sort și verifică egalitățile. Înțelege de ce <= este greșit și cum definești corect criteriile secundare.
În acest material
Comparatorul folosit de sort răspunde la întrebarea „trebuie a să apară înaintea lui b?”. El nu verifică dacă două elemente sunt acceptabil ordonate și nu întoarce numărul de poziții dintre ele. Rezultatul trebuie să descrie o relație strictă și coerentă.
De ce <= nu este un comparator corect
Pentru ordinea crescătoare a întregilor, criteriul este a<b. Dacă folosești a<=b, comparația unui element cu el însuși devine adevărată. Comparatorul spune astfel că elementul trebuie să fie înaintea lui însuși, încălcând cerința de ordine strictă.
Consecința nu este doar o ordine diferită a duplicatelor. Algoritmul primește o relație care nu îndeplinește precondițiile sale, deci nu mai ai garanția unui rezultat corect. Testele fără duplicate pot ascunde această greșeală.
La punctaj descrescător și număr de concurs crescător, ordinea este (90,3), (90,12), (80,1).Mărește schema ↗
Criteriul secundar se aplică numai la egalitate
Imaginează-ți înregistrări cu punctaj și număr de concurs. Vrei punctaj descrescător, iar pentru punctaje egale număr crescător. Compari întâi punctajele: dacă diferă, criteriul este punctajul mai mare. Numai dacă sunt egale compari numerele.
Pentru perechile (90,12), (90,3) și (80,1), ordinea dorită este (90,3), (90,12), (80,1). Numărul 1 nu mută punctajul 80 înaintea celor cu 90. Un „sau” între cele două criterii poate produce exact această contradicție.
Trei întrebări pentru verificare
Comparatorul întoarce fals când compari un element cu el însuși? Dacă a este înaintea lui b, este fals că b este înaintea lui a? Dacă a este înaintea lui b și b înaintea lui c, rezultă că a este înaintea lui c? Aceste teste simple nu reprezintă o demonstrație completă pentru orice comparator, dar descoperă multe erori de proiectare.
Mai trebuie ca echivalența indusă de comparator să fie coerentă. Pentru criteriul „doar punctaj”, două înregistrări cu același punctaj sunt echivalente în sensul sortării, chiar dacă alte câmpuri diferă.
Stabilitatea este o cerință separată
std::sort nu garantează păstrarea ordinii inițiale a elementelor echivalente. Dacă aceasta este cerută, poți folosi std::stable_sort sau poți adăuga poziția inițială drept criteriu secundar. Nu confunda egalitatea după comparator cu identitatea completă a înregistrărilor.
Comparatorul trebuie să producă rezultate consecvente. Nu îl baza pe un contor care se schimbă la fiecare apel și nu modifica elementele comparate. Nici scăderea a-b nu este un substitut general sigur pentru comparație: poate depăși domeniul tipului.
Exercițiu înainte de implementare
Scrie cinci înregistrări, cu două egalități după criteriul principal, și ordonează-le manual. Compară apoi toate perechile dintr-un grup egal. Dacă cerința spune doar „descrescător după punctaj”, decide dacă ordinea la egalitate este liberă sau impusă de o frază separată.
Recapitulează sortarea vectorilor, înregistrările struct și pair și iteratorii. Cerința de ordine strictă este documentată în specificația algoritmilor de sortare C++.
Întrebări frecvente
De ce nu folosesc <= în comparatorul pentru sort?
Comparatorul trebuie să exprime o ordine strictă. Pentru orice element a, comparația lui a cu el însuși trebuie să fie falsă. a <= a este adevărat, deci încalcă această cerință.
Cum sortez după două criterii în C++?
Compară mai întâi criteriul principal. Numai când valorile lui sunt egale folosește criteriul secundar. De exemplu, ordonează după punctaj descrescător și apoi după nume crescător, cu relații stricte la ambele niveluri.
Păstrează sort ordinea inițială a elementelor echivalente?
Nu există această garanție pentru std::sort. Dacă ordinea inițială dintre elementele echivalente după comparator contează, folosește o sortare stabilă sau un criteriu explicit suplimentar.