Adakah std::list::size() Benar-benar O(1) dalam Semua Pelaksanaan?

std::list::size(): Benar-benar O(n)?

Walaupun sesetengah individu mendakwa bahawa std: :list::size() mempunyai kerumitan linear, kebenaran mengenai kerumitannya bergantung pada pelaksanaan. Piawaian C tidak menyatakan keperluan kerumitan untuk fungsi ini.

Variasi Pelaksanaan

• Microsoft Visual Studio VC : Dalam versi lama (seperti VC6), size() sememangnya mempunyai kerumitan yang berterusan kerana ia hanya mengembalikan yang disimpan saiz dalam struktur data dalamannya.
• GNU Compiler Collection (GCC): Dari segi sejarah (sehingga GCC 4.1.0), size() menggunakan O(n ) pendekatan dengan mengulangi senarai untuk mengira bilangan elemen.

Keadaan Semasa dalam GCC

Dalam C 11, piawai C mewajibkan bahawa operasi saiz() untuk semua bekas standard, termasuk std::list, mesti mempunyai pemalar kerumitan (O(1)). Ini adalah untuk memastikan gelagat masa jalan yang konsisten dan cekap merentas platform dan pelaksanaan.

Pelaksanaan dalam Libstdc

Walaupun mandat C 11, pelaksanaan saiz() dalam libstdc (pustaka standard yang digunakan oleh GCC) kekal O(n) dalam versi GCC sehingga 4.8. Ini dilakukan atas sebab prestasi dan untuk meminimumkan overhed untuk mengekalkan medan saiz tambahan dalam struktur senarai.

Kemas kini: O(1) Pelaksanaan dalam GCC 5.0

Dengan keluaran GCC 5.0, pelaksanaan size() untuk std::list akhirnya dioptimumkan untuk mencapai kerumitan O(1) dalam mod C 11. Ini dicapai dengan memperkenalkan medan saiz dalaman yang menjejaki bilangan elemen dalam senarai, menyediakan akses masa tetap kepada maklumat saiz.

Kesimpulan

Sementara kerumitan std::list::size() ialah topik perbahasan pada masa lalu, standard C semasa memerlukan O(1) kerumitan untuk semua bekas standard. Pelaksanaan dalam GCC 5.0 dan versi yang lebih baru mematuhi keperluan ini, memastikan pelaksanaan size() yang cekap dan boleh diramal untuk std::list.

Atas ialah kandungan terperinci Adakah std::list::size() Benar-benar O(1) dalam Semua Pelaksanaan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!