Mengapakah `std::sort` Elakkan Memanggil Fungsi `Swap` Tersuai untuk Julat Kecil?

std::sort Boleh Elakkan std::swap for Efficiency

Soalan:

Pertimbangkan kod berikut menggunakan jenis A yang ditentukan pengguna dengan fungsi swap tersuai:

<code class="cpp">struct A {
    double a;
    double* b;
    bool operator<(const A& rhs) const {
        return this->a < rhs.a;
    }
};

void swap(A& lhs, A& rhs) {
    std::cerr << "My swap.\n"; // Custom swap function
}</code>

Apabila n ditetapkan kepada 20, fungsi swap tersuai digunakan dan tatasusunan diisih. Walau bagaimanapun, apabila n ditetapkan kepada 4, fungsi swap tersuai tidak dipanggil.

Jawapan:

Untuk julat kecil (seperti apabila n ialah 4), std::isih pelaksanaan dalam stdlibc GCC (dan pelaksanaan perpustakaan standard lain) tukar kepada isihan sisipan atas sebab prestasi.

Pengoptimuman Isih Sisipan:

Isih sisipan dalam pelaksanaan GCC menggunakan pendekatan yang berbeza untuk bertukar-tukar:

1. Ia menggerakkan keseluruhan julat nilai pada satu masa, menggunakan std::move_backward secara dalaman.
2. Jika ciri eksperimen C 11 pengkompil tidak didayakan, std::move_backward boleh menggunakan penyalinan dan bukannya bergerak.

Pengoptimuman ini meningkatkan prestasi dengan mengelakkan pertukaran yang tidak perlu. Daripada menukar elemen secara individu, sebahagian daripada tatasusunan dialihkan, dengan berkesan melaksanakan berbilang swap dalam satu operasi.

Kesimpulan:

Apabila mengisih tatasusunan kecil, std:: isihan boleh menggunakan isihan sisipan untuk mengelak menggunakan fungsi swap tersuai. Pengoptimuman ini boleh meningkatkan prestasi tetapi harus dipertimbangkan apabila menyalin objek adalah mahal.

Atas ialah kandungan terperinci Mengapakah `std::sort` Elakkan Memanggil Fungsi `Swap` Tersuai untuk Julat Kecil?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!