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

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

Kebimbangan telah dibangkitkan mengenai kerumitan masa std ::list::size() dalam C . Sesetengah mencadangkan ia mungkin bergantung kepada pelaksanaan, walaupun standard tidak menyatakan kerumitannya.

Gelagat Khusus Pelaksanaan

Dalam versi C yang terdahulu, kerumitan std: :list::size() berbeza-beza bergantung pada pelaksanaan STL yang digunakan. Microsoft Visual Studio V6 melaksanakannya dengan kerumitan berterusan, manakala GCC sehingga 4.1.0 menggunakan pendekatan berasaskan jarak, menghasilkan kerumitan O(n).

Penstandardan dan Kerumitan

Dalam C 11, perubahan telah diperkenalkan oleh n2923, yang memerlukan semua operasi bekas .size() standard mempunyai kerumitan masa yang berterusan (O(1)). Ini kini merupakan keperluan yang jelas, memastikan prestasi yang konsisten merentas pelaksanaan.

Pelaksanaan GCC

Walau bagaimanapun, walaupun terdapat penyeragaman, pelaksanaan std::list::size( ) dalam GCC sehingga versi 4.8 terus menggunakan algoritma O(n). Ini diterangkan secara terperinci dalam entri blog yang dipautkan dalam soalan asal.

Kemas kini dalam GCC 5.0

Adalah penting untuk ambil perhatian bahawa isu ini diselesaikan dalam GCC 5.0 dan nanti. Dalam mod C 11, std::list::size() dilaksanakan dengan betul dengan kerumitan O(1) dalam GCC 5.0 dan ke atas.

Pelaksanaan libc

Dalam Berbeza dengan pendekatan GCC, pelaksanaan libc std::list::size() telah dioptimumkan secara konsisten untuk O(1) kerumitan sejak penubuhannya.

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