list::size()真的是o(n)吗?

C++11之前的答案

您是正确的,标准没有说明list::size()的复杂性必须是什么——但是,它确实建议它“应该具有恒定的复杂性”(表65中的注释a)。

Here's an interesting article by 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() (比如他的一个例子 清单:() 在持有锁时调用)。
• 而不是允许 尺寸() 为O(N),为了“最不令人惊讶”,标准应要求任何实现 尺寸() 以O(1)方式实现它。如果容器不能做到这一点,则不应实现 尺寸() 完全。在这种情况下,容器的用户将意识到 尺寸() 不可用,如果他们仍然想要或需要获取容器中的元素数量,他们仍然可以使用 container::distance( begin(), end()) 为了得到这个值——但是他们会完全意识到这是一个O(N)操作。

我想我倾向于同意他的大部分推理。不过,我不喜欢他提议的添加到 splice() 超载。必须通过 n 必须等于 distance( first, last) 要获得正确的行为似乎是一个难以诊断的错误的处方。

我不确定应该或可以做些什么,因为任何更改都会对现有代码产生重大影响。但就目前的情况而言,我认为现有的代码已经受到了影响——对于一些本应得到很好定义的实现,行为可能与一个实现和另一个实现有很大的不同。也许OneByone关于“缓存”大小和标记为“已知/未知”的评论可以很好地工作-您得到了摊销的o(1)行为-您获得o(n)行为的唯一时间是当列表被某些splice()操作修改时。这方面的好处在于,它可以由今天的实现人员完成,而不需要更改标准(除非我遗漏了一些东西)。

据我所知,C++0X不会改变这个区域中的任何东西。

在C++ 11中,需要 任何 标准容器 .size() 操作必须在“恒定”复杂性下完成(O(1))。(表96“集装箱要求”)。以前在C++ 03中 siz() 应该 具有恒定的复杂性,但不是必需的(请参见 Is std::string size() a O(1) operation? )

标准的变化是由 n2923: Specifying the complexity of size() (Revision 1) .

但是,实施 siz() 在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()); }

也见 Why is std::list bigger on c++11? 详细说明为什么要这样保存。

更新 : std::list::size() 是 properly O(1) 使用GCC时 五 在C++ 11模式(或以上)。

顺便说一下, siz() 在libc++中,正确的o(1):

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

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

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

我之前已经研究过GCC 3.4的列表::SIZE,所以我可以这样说:

1. 它使用std::距离(头、尾)
2. Std::Distance有两种实现:对于满足RandomAccessIterator的类型,它使用“tail head”,对于仅满足inputiTerator的类型,它使用依赖于“iterator++”的O(n)算法,直到它到达给定的尾部。
3. std::list不是satsify randomaccessiterator,所以大小是o(n)。

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

我个人并不认为拼接为O(N)的问题是允许尺寸为O(N)的唯一原因。 你不为你不使用的东西付钱 是一个重要的C++座右铭。在这种情况下,无论您是否检查列表的大小,维护列表的大小都需要在每次插入/删除时进行额外的递增/递减。这是一个小的固定开销,但它仍然需要考虑。

很少需要检查列表的大小。从头到尾迭代而不考虑总大小是非常常见的。

我会去 source . SGI的STL页面说它允许具有线性复杂性。我相信他们遵循的设计准则是允许列表实现尽可能的通用,从而允许在使用列表时有更多的灵活性。

此错误报告: [C++0x] std::list::size complexity 在极其复杂的细节中捕获了GCC 4×x中的实现是线性时间的事实,以及由于ABI兼容性的考虑,C++ 11的转换到恒定时间的方式是缓慢的(在5中可用)。

GCC4.9系列的手册页仍然包含以下免责声明:

对C++ 11的支持仍然是 在将来的版本中,可能会以不兼容的方式进行更改。

这里引用了相同的bug报告: Should std::list::size have constant complexity in C++11?

如果您正确使用列表,您可能不会注意到任何差异。

对于要在插入后保留有效指针的数据,列表适用于要重新排列而不复制的大数据结构。

在第一种情况下没有区别,在第二种情况下,我更喜欢旧的(较小的)size()实现。

不管怎样,std更多的是关于正确性和标准行为以及“用户友好性”,而不是原始速度。