c++ - list::size() 真的是 O(n) 吗？

Question

最近，我注意到有人提到 std::list::size() 具有线性复杂度。
根据some sources ，这实际上取决于实现，因为标准没有说明复杂性必须是什么。
评论in this blog entry说:

Actually, it depends on which STL you are using. Microsoft Visual Studio V6 implements size() as {return (_Size); } whereas gcc (at least in versions 3.3.2 and 4.1.0) do it as { return std::distance(begin(), end()); } The first has constant speed, the second has o(N) speed

1. 所以我的猜测是，对于 VC++ 人群，size() 与 Dinkumware 一样具有恒定的复杂性自 VC6 以来可能不会改变这一事实。我在吗？
   
2. 目前在 gcc 中是什么样子的？如果真的是 O(n)，为什么开发者选择这样做？

Answer 1

在 C++11 中，any 标准容器要求 .size() 操作必须以“恒定”复杂度完成 (O(1)) . (表 96——容器要求)。以前在 C++03 中 .size() 应该 具有恒定的复杂性，但不是必需的(参见 Is std::string size() a O(1) operation? )。

标准的变化是由 n2923: Specifying the complexity of size() (Revision 1) 引入的。 .

不过，libstdc++中.size()的实现，在gcc 4.8之前仍然使用O(N)算法:

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

另见 Why is std::list bigger on c++11?详细了解为什么要这样保存。

更新:std::list::size() 为 properly O(1)在 C++11 模式(或更高版本)下使用 gcc 5.0 时。

---

顺便说一句，libc++ 中的 .size() 是正确的 O(1):

_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();}