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

Question

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

for the C++ 11 in the standard说list的size()应该是O(1) http://en.cppreference.com/w/cpp/container/list/size

但是在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 5改变了这一点:虽然以ABI变化为代价; 这意味着使用gcc 5.0编译的c ++代码不适用于旧版本的c ++运行时库.

来自https://gcc.gnu.org/gcc-5/changes.html "默认情况下启用std :: list的新实现,带有O(1)size()函数"

Answer 1

在C++ 98/03中,没有说明std::list::size()是O(1)还是O(N).两种决定都有权衡.

在C++ 11中,委员会指定std::list::size()为O(1).对于具有O(N)的实现,这是ABI突破性更改std::list::size(),而gcc就是这样的实现.打破ABI对于实现者来说是一件大事.它给客户带来了很多痛苦.因此它只在很长一段时间内完成,而且相对较大.