c++ - 为什么 GCC 中 std::list O(n) 的 size() 方法？

Question

在 GCC 中，std::list 的 size() 方法是 O(n)。为什么？

对于 C++11，标准是 size() of list should be O(1)

但是在 glibc 中我们有以下内容:

/usr/include/c++/4.6.3/bits/stl_list.h

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class list : protected _List_base<_Tp, _Alloc>
{
 ...
 size_type
  size() const
  { return std::distance(begin(), end()); }

问题是:为什么三年前的要求还没有在 GCC 中实现？

编辑:

gcc 5 改变了这一点:尽管以 ABI 改变为代价；这意味着使用 gcc 5.0 编译的 C++ 代码将无法与旧版本的 C++ 运行时库一起使用。

来自 https://gcc.gnu.org/gcc-5/changes.html

A new implementation of std::list is enabled by default, with an O(1) size() function

Answer 1

在 C++98/03 中，未指定 std::list::size() 是 O(1) 还是 O(N)。任何一个决定都需要权衡。

在 C++11 中，委员会指定 std::list::size() 为 O(1)。对于具有 O(N) std::list::size() 的实现，这是一个破坏 ABI 的更改，而 gcc 就是这样一个实现。打破 ABI 对实现者来说是一件大事。它给客户带来了很多痛苦。所以它在很长一段时间内只做一次，而且声势相对较大。