在现代实现中 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) 复杂性，但对于绝大多数用户来说，操作应该是恒定时间。