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

Question

最近，我注意到有人提到 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)，为什么开发者会选择这样做呢？

原文由 foraidt 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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() 为 O(N)，为了“最少意外”，标准应该要求任何实现 size() 的容器在 O(1) 中实现它时尚。如果容器不能做到这一点，它根本不应该实现 size() 。在这种情况下，容器的用户将被告知 size() 不可用，如果他们仍然想要或需要获取容器中仍然可以使用的元素数量 container::distance( begin(), end()) 获得该值 - 但他们将完全意识到这是一个 O(N) 操作。

我想我倾向于同意他的大部分推理。但是，我不喜欢他对 splice() 重载的提议。必须传入 n 必须等于 distance( first, last) 以获得正确的行为似乎是难以诊断错误的秘诀。

我不确定接下来应该或可以做什么，因为任何更改都会对现有代码产生重大影响。但就目前而言，我认为现有代码已经受到影响 - 对于应该明确定义的东西，行为可能会因一种实现与另一种实现有很大不同。也许 onebyone 的关于将大小“缓存”并标记为已知/未知的评论可能效果很好 - 你会得到分摊的 O(1) 行为 - 你得到 O(N) 行为的唯一时间是当列表被某些 splice() 操作修改时.这样做的好处是，今天的实现者可以在不改变标准的情况下完成它（除非我遗漏了一些东西）。

据我所知，C++0x 并没有改变这方面的任何东西。

原文由 Michael Burr 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

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

n2923 引入了标准的更改：指定 size() 的复杂性（修订版 1） 。

但是，在 libstdc++ 中 .size() 的实现仍然在 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.0 时， std::list::size() 是 正确的 O(1 )。

---

顺便说一句，libc++ 中的 .size() 是正确的 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();}

原文由 kennytm 发布，翻译遵循 CC BY-SA 3.0 许可协议