65

最近，我注意到有人提到它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) 速度

  1. 所以我的猜测是，对于 VC++ 人群来说size()，复杂性是恒定的，因为 Dinkumware 自 VC6 以来可能不会改变这一事实。我在吗？
  2. 它现在看起来像什么gcc？如果真的是O(n)，为什么开发者会选择这样做呢？
4

7 回答 7

81

在 C++11 中，要求对于任何标准容器，.size()操作必须以“恒定”复杂度 (O(1)) 完成。（表 96——容器要求）。以前在 C++03 中.size() 应该具有恒定的复杂性，但不是必需的（请参阅Is std::string size() a O(1) operation?）。

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 上更大？详细了解为什么以这种方式保存它。

更新：在 C++11 模式（或更高使用 gcc 5.0std::list::size()时正确为 O(1 )。

顺便说一句，.size()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();}
于 2012-12-06T20:17:28.343 回答
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()是一个好主意（作者认为）：

我认为论文的主要观点是：

  • 在少数情况下保持内部计数，因此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 并没有改变这方面的任何东西。

于 2008-10-23T08:14:05.640 回答
15

我之前不得不研究 gcc 3.4 list::size，所以我可以这样说：

  1. 它使用std::distance(head, tail).
  2. std::distance有两种实现：对于满足RandomAccessIterator的类型，它使用“tail-head”，对于仅满足InputIterator的类型，它使用依赖于“iterator++”的 O(n) 算法，计数直到它到达给定的尾部。
  3. std::list不满足RandomAccessIterator，因此大小为 O(n)。

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

于 2008-10-23T17:25:18.600 回答
13

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

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

于 2008-10-23T13:21:39.170 回答
5

我会去源头（存档）。SGI 的 STL 页面说它允许具有线性复杂性。我相信他们遵循的设计准则是让列表实现尽可能通用，从而在使用列表时允许更大的灵活性。

于 2008-10-23T08:18:07.770 回答
1

此错误报告：[C++0x] std::list::size complex由于 ABI 兼容性问题，即将推出（在 5.0 中可用）。

GCC 4.9 系列的手册页仍然包含以下免责声明：

对 C++11 的支持仍处于试验阶段，在未来的版本中可能会以不兼容的方式发生变化。

此处引用了相同的错误报告：Should std::list::size 在 C++11 中是否具有恒定的复杂性？

于 2015-12-04T01:57:25.847 回答
0

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

列表适用于您希望在不复制的情况下重新排列的大数据结构，对于您希望在插入后保留有效指针的数据。

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

无论如何，std 更多的是关于正确性和标准行为以及“用户友好性”，而不是原始速度。

于 2017-05-18T14:09:34.810 回答