是list :: size（）真的是O（n）？
最近，我注意到有人提到std::list::size()具有线性复杂性。
根据一些 消息来源 ，这实际上是依赖于实现的，因为标准并没有说明复杂性是什么。
在这个博客条目中的评论说：
其实，这取决于你正在使用的STL。 Microsoft Visual Studio V6实现size（）为{return（_Size）; }而gcc（至less在版本3.3.2和4.1.0）做{return std :: distance（begin（），end（））; }第一个是恒定速度，第二个是o（N）速度
- 所以我的猜测是，对于VC ++人群
size()，Dinkumware自从VC6以来可能不会改变这个事实。 我在吗？ - 它在
gcc看起来像什么？ 如果真的是O（n），为什么开发者select这样做呢？
Pre-C ++ 11的答案
这个标准没有说明list :: size（）的复杂性是否正确 – 但是，它确实build议它“应该具有恒定的复杂性”（表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）操作。
我想我倾向于赞同他的大部分推理。 但是，我不喜欢他的build议除了splice()重载。 为了得到正确的行为，必须通过一个必须等于distance( first, last)的n似乎是难以诊断错误的秘诀。
我不知道应该怎么做或者能够做什么，因为任何改变都会对现有代码产生重大影响。 但是，就目前而言，我认为现有的代码已经受到了影响 – 对于一些应该已经明确定义的内容，行为在执行上可能会有相当大的差异。 也许onebyone的评论关于有'caching'和标记已知/未知的大小可能会奏效 – 你得到分期O（1）的行为 – 唯一一次你得到O（N）的行为是当这个列表被splice 。 关于这一点的好处是，今天可以通过实现者来完成，而不必改变标准（除非我错过了某些东西）。
据我所知，C ++ 0x并没有改变这个领域的任何东西。
在C ++ 11中，要求任何标准容器的.size()操作都必须以“常量”复杂度（O（1））完成。 （表96 – 容器要求）。 以前在C ++ 03中.size() 应该具有不变的复杂性，但不是必需的（请参阅std :: string size（）是一个O（1）操作？ ）。
标准的变化由n2923引入：指定size（）（修订1）的复杂性 。
但是，libstdc ++中.size()的实现仍然使用gcc中的O（N）algorithm，最大为4.8：
/** Returns the number of elements in the %list. */ size_type size() const _GLIBCXX_NOEXCEPT { return std::distance(begin(), end()); }
另请参见为什么在c + + 11上std :: list更大？ 为什么它保持这种方式。
更新 ：在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();}
我不得不查看gcc 3.4的list :: size之前，所以我可以这样说：
- 它使用std :: distance（head，tail）
- std :: distance有两个实现：对于满足RandomAccessIterator的types，它使用“tail-head”，对于仅仅满足InputIterator的types，它使用依赖于“iterator ++”的O（n）algorithm，直到碰到给定的尾巴。
- std :: list不会占用RandomAccessIterator，所以size是O（n）。
至于“为什么”，我只能说std :: list适合需要顺序访问的问题。 将大小存储为一个类variables会在每个插入，删除等操作中引入额外的开销，而且这个浪费对于STL的意图来说是一个很大的禁忌。 如果你真的需要一个恒定的大小（），使用std :: deque。
我个人并不认为拼接是O（N）是尺寸允许为O（N）的唯一原因。 你不支付你不使用的是一个重要的C ++座右铭。 在这种情况下，无论您是否检查列表的大小，维护列表大小都需要在每次插入/擦除时额外增加/减less。 这是一个小的固定开销，但它仍然是重要的考虑。
检查列表的大小是很less需要的。 从头到尾循环不关心总大小是无限多的。
我会去源 。 SGI的STL页面表示，它被允许具有线性复杂性。 我相信他们所遵循的devise指引是为了让清单的实施尽可能通用，从而使清单更具灵活性。
这个错误报告： [C ++ 0x] std :: list :: size复杂性 ，非常详细地捕捉到GCC 4.x中的实现是线性时间，以及C ++ 11的稳定时间过渡是如何慢在即将到来（在5.0中可用）由于ABI兼容性问题。
GCC 4.9系列的手册页还包含以下免责声明：
对C ++ 11的支持仍然是实验性的，并可能在未来版本中以不兼容的方式进行更改。
在这里引用同样的错误报告： 应该std :: list :: size在C ++ 11中有恒定的复杂性吗？
如果你正确使用列表，你可能不会注意到任何区别。
列表对于想要重新排列而不需要复制的大数据结构是很好的，对于希望在插入后保持有效指针的数据。
在第一种情况下，没有什么区别，在第二个我更喜欢旧的（较小）size（）实现。
无论如何，std更多的是正确性和标准的行为和“用户友好性”比原始速度。
