在現代實作 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) 複雜性，但對於絕大多數用戶來說，操作應該是恆定時間。