list :: size()真的是O(n)吗？

最近,我注意到有些人提到它std::list::size()具有线性复杂性.
根据一些 消息来源,这实际上是依赖于实现的,因为标准没有说复杂性必须是什么.此博客条目中
的评论说:

实际上,这取决于您使用的STL.Microsoft Visual Studio V6将size()实现为{return(_Size); 而gcc(至少在版本3.3.2和4.1.0中)将其作为{return std :: distance(begin(),end()); 第一个具有恒定速度,第二个具有o(N)速度

所以我的猜测是因为VC++人群的size()复杂程度不变,因为自VC6以来Dinkumware可能不会改变这一事实.我在那儿吗？


目前看起来像gcc什么？如果它真的是O(n),开发人员为什么选择这样做？

kennytm.. 73

在C++ 11中,要求对于任何标准容器,.size()操作必须以"常量"复杂度完成(O(1)).(表96-容器要求).以前在C++ 03中.size() 应该具有恒定的复杂性,但不是必需的(参见Is std :: string size()是否为O(1)操作？).

标准的变化由n2923引入:指定size()(修订版1)的复杂性.

但是,.size() libstdc ++中的实现仍然使用gcc中的O(N)算法,最高可达4.8:

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

另请参阅为什么std :: list在c ++ 11上更大？详细说明为什么它保持这种方式.

更新:std::list::size()是正确O(1)使用gcc时 5.0在C++ 11模式(或以上).

---

顺便说一下,.size()在libc ++中是正确的O(1):

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

这应该被接受,不幸的是ppl不要看旧Q. :) (3认同)

---

Michael Burr.. 52

前C++ 11答案

你是正确的,标准没有说明list :: size()的复杂性必须是什么 - 但是,它确实建议它"应该具有恒定的复杂性"(表65中的注释A).

这是Howard Hinnant的一篇有趣的文章解释了为什么有些人认为list :: size()应该具有O(N)复杂度(主要是因为他们认为O(1)list :: size()使得list :: splice()具有O(N)复杂度)以及为什么O(1)list :: size()是一个好主意(在作者看来):

http://howardhinnant.github.io/On_list_size.html

我认为论文的要点是:

保持内部计数的情况很少,因此list::size()O(1)会导致拼接操作变为线性

可能还有更多的情况,有人可能不知道可能发生的负面影响,因为他们称之为O(N)size()(例如他list::size()拿着锁时调用的一个例子).

为了size()"最小惊喜",标准应该要求任何实现size()以O(1)方式实现它的容器,而不是允许为O(N).如果容器不能这样做,它根本不应该实现size().在这种情况下,容器的用户将被告知size()不可用,并且如果他们仍然想要或需要获得容器中的元素数量,他们仍然可以使用它container::distance( begin(), end())来获得该值 - 但他们将完全意识到它是O(N)操作.

我想我倾向于同意他的大多数推理.但是,我不喜欢他提出的splice()过载增加.传递n必须等于distance( first, last)获得正确的行为似乎是难以诊断错误的方法.

我不确定未来应该做什么或可以做什么,因为任何改变都会对现有代码产生重大影响.但就目前而言,我认为现有的代码已经受到影响 - 对于应该已经明确定义的内容,行为可能在一个实现与另一个实现之间存在相当大的差异.也许onebyone关于将大小"缓存"并标记为已知/未知的评论可能效果很好 - 你得到了摊销的O(1)行为 - 唯一一次得到O(N)行为的是当某些splice()操作修改了列表时.关于这一点的好处是它可以由实现者在今天完成而无需更改标准(除非我遗漏了一些东西).

据我所知,C++ 0x并没有改变这个领域的任何东西.

1> kennytm..：

---

在C++ 11中,要求对于任何标准容器,.size()操作必须以"常量"复杂度完成(O(1)).(表96-容器要求).以前在C++ 03中.size() 应该具有恒定的复杂性,但不是必需的(参见Is std :: string size()是否为O(1)操作？).

标准的变化由n2923引入:指定size()(修订版1)的复杂性.

但是,.size() libstdc ++中的实现仍然使用gcc中的O(N)算法,最高可达4.8:

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

另请参阅为什么std :: list在c ++ 11上更大？详细说明为什么它保持这种方式.

更新:std::list::size()是正确O(1)使用gcc时 5.0在C++ 11模式(或以上).

---

顺便说一下,.size()在libc ++中是正确的O(1):

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

---

这应该被接受,不幸的是ppl不要看旧Q. :)

2> Michael Burr..：

---

前C++ 11答案

你是正确的,标准没有说明list :: size()的复杂性必须是什么 - 但是,它确实建议它"应该具有恒定的复杂性"(表65中的注释A).

这是Howard Hinnant的一篇有趣的文章解释了为什么有些人认为list :: size()应该具有O(N)复杂度(主要是因为他们认为O(1)list :: size()使得list :: splice()具有O(N)复杂度)以及为什么O(1)list :: size()是一个好主意(在作者看来):

http://howardhinnant.github.io/On_list_size.html

我认为论文的要点是:

保持内部计数的情况很少,因此list::size()O(1)会导致拼接操作变为线性

可能还有更多的情况,有人可能不知道可能发生的负面影响,因为他们称之为O(N)size()(例如他list::size()拿着锁时调用的一个例子).

为了size()"最小惊喜",标准应该要求任何实现size()以O(1)方式实现它的容器,而不是允许为O(N).如果容器不能这样做,它根本不应该实现size().在这种情况下,容器的用户将被告知size()不可用,并且如果他们仍然想要或需要获得容器中的元素数量,他们仍然可以使用它container::distance( begin(), end())来获得该值 - 但他们将完全意识到它是O(N)操作.

我想我倾向于同意他的大多数推理.但是,我不喜欢他提出的splice()过载增加.传递n必须等于distance( first, last)获得正确的行为似乎是难以诊断错误的方法.

我不确定未来应该做什么或可以做什么,因为任何改变都会对现有代码产生重大影响.但就目前而言,我认为现有的代码已经受到影响 - 对于应该已经明确定义的内容,行为可能在一个实现与另一个实现之间存在相当大的差异.也许onebyone关于将大小"缓存"并标记为已知/未知的评论可能效果很好 - 你得到了摊销的O(1)行为 - 唯一一次得到O(N)行为的是当某些splice()操作修改了列表时.关于这一点的好处是它可以由实现者在今天完成而无需更改标准(除非我遗漏了一些东西).

据我所知,C++ 0x并没有改变这个领域的任何东西.

---

最新的C++ 0x草案要求`size()`具有恒定的时间复杂度(在N3000中对容器要求进行了更改).

---

也应该可以保持拼接O(1),但将大小标记为"未知".然后size()仍然是O(N)最坏情况,但最糟糕的情况是每次"不友好"拼接最多发生一次.因此,所有操作的性能都严格优于always-O(N)size().警告:我没想过这个.

3> 小智..：

---

我以前必须查看gcc 3.4的list :: size,所以我可以这样说:

它使用std :: distance(head,tail)

std :: distance有两个实现:对于满足RandomAccessIterator的类型,它使用"tail-head",对于仅满足InputIterator的类型,它使用依赖于"iterator ++"的O(n)算法,计数直到达到给定值尾巴.

std :: list不会使RandomAccessIterator饱和,因此大小为O(n).

至于"为什么",我只能说std :: list适用于需要顺序访问的问题.将大小存储为类变量会在每次插入,删除等时引入开销,并且根据STL的意图浪费是一个很大的禁忌.如果你真的需要一个常量时间(),请使用std :: deque.

4> Greg Rogers..：

---

我个人不认为splice是O(N)的问题是允许大小为O(N)的唯一原因.你不支付你不使用的是一个重要的C++座右铭.在这种情况下,无论您是否检查列表的大小,维护列表大小都需要在每次插入/删除时额外增加/减少.这是一个很小的固定开销,但它仍然很重要.

很少需要检查列表的大小.从头到尾迭代而不关心总大小是无限多见.

---

显然,C++ 11委员会不同意你的意见.可怜.