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

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

Baru-baru ini, beberapa pembangun telah mencadangkan supaya std::list::size() mempunyai kerumitan masa linear (O(n)). Walau bagaimanapun, menurut piawaian C, kerumitan tidak ditakrifkan dan mungkin berbeza-beza bergantung pada pelaksanaan.

Dalam versi terdahulu piawai C (C 03), operasi saiz() disyorkan untuk mempunyai kerumitan yang berterusan (O(1)). Walau bagaimanapun, dengan pengenalan C 11, ia menjadi keperluan untuk semua bekas standard. Jadual 96 standard C 11 secara eksplisit menyatakan bahawa .size() harus mempunyai kerumitan malar untuk semua bekas.

Secara sejarah, perpustakaan libstdc GCC melaksanakan size() dengan kerumitan O(n) menggunakan std::distance(begin (), end()), seperti yang diterangkan dalam entri blog yang anda petik. Walau bagaimanapun, dalam mod C 11, tingkah laku ini telah berubah:

size_type
size() const _GLIBCXX_NOEXCEPT
{ return __size_alloc_.first(); }

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

Dalam GCC 5.0 dan ke atas, fungsi size() menggunakan struktur data dalaman untuk menjejaki bilangan elemen, membuat operasi dengan berkesan O(1). Ini sejajar dengan keperluan C 11 untuk semua bekas standard.

Adalah penting untuk ambil perhatian bahawa sesetengah kes penggunaan khusus mungkin masih membawa kepada kerumitan O(n) untuk saiz(), tetapi untuk sebahagian besar pengguna, operasi mestilah masa yang tetap.

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