在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 ++ 98/03中,没有说明std::list::size()
是O(1)还是O(N)。两种决定都有权衡。
在C ++ 11中,委员会指定std::list::size()
是O(1)。对于具有O(N)std::list::size()
的实现,这是ABI突破性更改,而gcc就是这样的实现。打破ABI对于实现者来说是一件大事。它给客户带来了很多痛苦。因此它只在很长一段时间内完成,而且相对较大。