为什么在GCC中std :: list O(n)的size()方法?

问题描述 投票:6回答:1

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

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

默认情况下启用std::list的新实现,具有O(1)size()函数

c++ c++11 gcc size stdlist
1个回答
8
投票

在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对于实现者来说是一件大事。它给客户带来了很多痛苦。因此它只在很长一段时间内完成,而且相对较大。

© www.soinside.com 2019 - 2024. All rights reserved.