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

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

在标准C++ 11说大小（名单）应该是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 ::列表的新的实现是默认启用，用O（1）尺寸（）函数”

来源

2014-10-27 MichaelMoser

g ++ 4.5 is from 2010.获取最新版本！ – 2014-10-27 03:31:50

很不错，在4.6.3中它也是一样的东西 – MichaelMoser 2014-10-27 03:39:41

在4.8.3中也是一样的！ – Galik 2014-10-27 04:00:45

在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对于实现者来说是一件大事。它给客户带来了很大的痛苦。所以它只会在一段时间内完成一次，并且会有相当大的夸夸其谈。

来源

2014-10-27 03:39:54

那他们怎么经常更改名称修改算法呢？您无法将新的二进制文件链接到使用旧的名称修改算法编译的二进制文件。 https://gcc.gnu.org/onlinedocs/gcc/C_002b_002b-Dialect-Options.html – MichaelMoser 2014-10-27 03:48:37

@MichaelMoser这个名字是* *不是由标准规定的。它依赖于实现。 – 2014-10-27 04:05:01

@MarkRansom仍然能够链接到使用旧版本编译器编译的二进制文件，它就像ABI更改一样突破。 – MichaelMoser 2014-10-27 04:06:41

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

回答

相关问题