Adakah `std::list::size()` Sentiasa O(1)?

Adakah senarai::size() Benar-benar O(1)?

Walaupun pernah benar bahawa std::list::size () mempamerkan kerumitan berubah-ubah merentas pelaksanaan, C 11 telah menyeragamkan kelakuannya. Jadual 96 Keperluan Bekas mewajibkan kerumitan berterusan (O(1)) untuk operasi .size() pada semua bekas standard.

Walau bagaimanapun, pengecualian ketara kekal sebagai pelaksanaan libstdc gcc sebelum versi 5.0. Walaupun keperluan standard C 11, fungsi .size()nya menggunakan algoritma O(N), seperti yang dilihat dalam petikan berikut:

size_type
size() const _GLIBCXX_NOEXCEPT
{ return std::distance(begin(), end()); }

Keputusan ini berpunca daripada pertimbangan pengoptimuman dalam libstdc . Mengekalkan kiraan elemen yang berasingan daripada melintasi senarai meningkatkan prestasi untuk sesetengah kes penggunaan, walaupun ia bercanggah dengan keperluan kerumitan standard.

Pelaksanaan Libc, sebaliknya, mematuhi O(1) dengan betul kerumitan, seperti yang digambarkan oleh coretan kod berikut:

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type __node_allocator> __size_alloc_;

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

Kesimpulannya, manakala piawaian C 11 memberi mandat Kerumitan O(1) untuk std::list::size(), pelaksanaan libstdc gcc sebelum versi 5.0 kekal sebagai anomali, sebaliknya menggunakan algoritma O(N).

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