現代 C 實作中的 std::list::size() 真的是 O(1) 嗎？

std::list::size() 在現代實作中真的是 O(n) 嗎？

最近，一些開發人員建議std::list::size() 具有線性時間複雜度 (O(n))。但是，根據 C 標準，複雜性沒有定義，並且可能會因實現而異。

在 C 標準的早期版本（C 03）中，建議 size() 操作具有恆定的複雜性(O(1))。然而，隨著 C 11 的引入，它成為所有標準容器的要求。 C 11 標準的表 96 明確指出 .size() 對於所有容器應該具有恆定的複雜度。

歷史上，GCC 的libstdc 函式庫使用std::distance(begin ) 實作複雜度為O(n) 的size() (), end())，如您所引用的部落格文章所述。然而，在C 11 模式中，這種行為發生了變化：

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

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

在GCC 5.0 及更高版本中，size() 函數使用內部資料結構來追蹤元素的數量，有效地使操作O(1)。這符合所有標準容器的 C 11 要求。

需要注意的是，一些利基用例可能仍然會導致 size() 的 O(n) 複雜性，但對於絕大多數用戶來說，操作應該是恆定的時間。

以上是現代 C 實作中的 std::list::size() 真的是 O(1) 嗎？的詳細內容。更多資訊請關注PHP中文網其他相關文章！