Mengapa `std::sort` Saya Ranap? (Dan Cara Memperbaikinya)

Memahami Ranap Pengkompil dengan std::sort

Fungsi C Standard Library, std::sort, memainkan peranan penting dalam menyusun data struktur. Walau bagaimanapun, tidak semua fungsi perbandingan berfungsi seperti yang diharapkan dengan std::sort, berpotensi membawa kepada ranap program.

Pertimbangkan coretan kod berikut:

#include <algorithm>

struct A
{
    int a;
};

bool compare(const A& a, const A& b)
{
    return a.a <= b.a; // Corrected from original code (<)
}

int main()
{
    A coll[8];
    std::sort(&coll[0], &coll[8]);
}

Masalah:

Dalam kod asal, fungsi perbandingan bandingkan menggunakan a.a <= b.a untuk membandingkan elemen, yang membolehkan elemen yang sama dianggap disusun. Ini melanggar peraturan pemesanan lemah yang ketat yang diperlukan oleh std::sort.

Penyelesaian:

Mengikut peraturan pesanan lemah yang ketat, untuk sebarang unsur A, B, dan C dalam urutan, syarat berikut mesti tahan:

• Jika A < B, kemudian B > A.
• Jika A < B dan B < C, kemudian A < C.
• A tidak boleh sama dengan dirinya sendiri (iaitu, A != A).

Fungsi perbandingan asal membandingkan tidak memenuhi peraturan ini kerana ia membenarkan A sama dengan itu sendiri, membawa kepada potensi gelung tak terhingga dalam std::sort. Untuk membetulkannya, fungsi perbandingan perlu digantikan dengan versi yang diperbetulkan yang ditunjukkan dalam coretan kod di atas.

Atas ialah kandungan terperinci Mengapa `std::sort` Saya Ranap? (Dan Cara Memperbaikinya). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!