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

StackOverflow https://stackoverflow.com/questions/228908

题

最近，我注意到有人提到 std::list::size() 具有线性复杂度。
根据 一些 来源, ，这实际上取决于实现，因为标准没有说明复杂性必须是多少。
评论 在这篇博客文章中 说：

实际上，这取决于您 正在使用。Microsoft Visual Studio V6 将 size() 实现为 {return (_Size)；} 而 gcc（至少在版本 3.3.2 和 4.1.0）的做法是 { return std::distance(begin(),end())；} 前者速度恒定，后者 速度为o(N)

  1. 所以我的猜测是对于 VC++ 人群来说 size() 自从VC6以来，Dinkumware可能不会改变这一事实，因此具有不断的复杂性。我在吗？
  2. 目前情况如何 gcc？如果确实是O（n），为什么开发人员选择这样做？
有帮助吗？

解决方案

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() 是 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 并没有改变这方面的任何内容。

其他提示

在C ++ 11中，要求对于任何标准容器， .size（）操作必须在“常量”中完成。复杂性（O（1））。 （表96和＃8212;容器要求）。以前在C ++ 03 .size（） 应该具有恒定的复杂性，但不是必需的（参见 std :: string size（）是否为O（1）操作？）。

标准的变化由 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上更大？详细说明为什么要保持这种方式。

更新 ： std :: list :: size（）是在C ++ 11模式（或更高版本）中使用gcc 5.0 时正确为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();}

之前我必须查看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）。

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

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

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

我会去来源（存档）。 SGI的STL页面表示允许线性复杂性。我相信他们遵循的设计准则是允许列表实现尽可能通用，从而允许更灵活地使用列表。

此错误报告： [C ++ 0x] std :: list： ：大小复杂度，捕捉到令人难以忍受的细节，即GCC 4.x中的实现是线性时间，以及由于ABI兼容性，C ++ 11的转换到等待时间很慢（5.0中可用）顾虑。

GCC 4.9系列的联机帮助页仍包含以下免责声明：

  

仍然支持C ++ 11   实验性的，可能会在未来版本中以不兼容的方式发生变化。

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

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

列表适用于您想要重新排列而无需复制的大数据结构，以及您希望在插入后保留有效指针的数据。

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

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

不隶属于 StackOverflow
scroll top