是list :: size（）真的O（n）吗？ [英] Is list::size() really O(n)?

问题描述

最近，我注意到一些人提到 std :: list :: size（）有一个线性复杂度。

根据一些 来源，这实际上取决于实现，因为标准没有说明复杂性。

注释在此博客条目中说：

Recently, I noticed some people mentioning that std::list::size() has a linear complexity.
According to some sources, this is in fact implementation dependent as the standard doesn't say what the complexity has to be.
The comment in this blog entry says:

，这取决于你
使用的STL。 Microsoft Visual Studio V6
实现size（）as {return（_Size）;
}，而gcc（至少在版本
3.3.2和4.1.0中）做为{return std :: distance（begin（），end（））; }
先有恒定速度，第二个
有o（N）速度

Actually, it depends on which STL you are using. Microsoft Visual Studio V6 implements size() as {return (_Size); } whereas gcc (at least in versions 3.3.2 and 4.1.0) do it as { return std::distance(begin(), end()); } The first has constant speed, the second has o(N) speed

1. 所以我的猜测是，对于VC ++群体 size（）有不变的复杂性，因为Dinkumware
   可能不会改变这个事实，因为VC6。我在那里吗？
   


2. 目前在 gcc 中看起来像什么？如果它真的是O（n），为什么
   开发人员选择这样做？

1. So my guess is that for the VC++ crowd size() has constant complexity as Dinkumware probably won't have changed that fact since VC6. Am I right there?
   
2. What does it look like currently in gcc? If it is really O(n), why did the developers choose to do so?

推荐答案

Pre-C ++ 11 answer

你是正确的，标准没有说明list :: size（）的复杂性。 ，它建议它应该有不断的复杂性（表65中的注释A）。

Pre-C++11 answer

You are correct that the standard does not state what the complexity of list::size() must be - however, it does recommend that it "should have constant complexity" (Note A in Table 65).

这是Howard Hinnant的一篇有趣的文章，解释了为什么有些人认为list :: size（）应该有O（N）复杂性（基本上因为他们相信O list :: size（）使得list :: splice（）具有O（N）复杂度）以及为什么一个O（1）list :: size（）是一个好主意（作者认为）：

Here's an interesting article by Howard Hinnant that explains why some people think list::size() should have O(N) complexity (basically because they believe that O(1) list::size() makes list::splice() have O(N) complexity) and why an O(1) list::size() is be a good idea (in the author's opinion):

• http：//howardhinnant.github。 io / On_list_size.html

• http://howardhinnant.github.io/On_list_size.html

我认为论文的要点是：

• 很少有情况下维护一个内部计数，因此 list :: size（）可以是O剪接操作变为线性


• 可能有更多的情况，其中某人可能不知道可能发生的负面影响，因为他们调用O（N）大小（）（例如 list :: size（）在持有锁时被调用）。


• 为了最小惊喜，标准应该要求任何容器实现<$ c（c），而不是允许 size（） $ c> size（）以O（1）方式实现它。如果容器不能这样做，它不应该实现 size（）。在这种情况下，容器的用户将意识到 size（）不可用，并且如果他们仍然想要或需要获取容器中的元素数量，仍然可以使用 container :: distance（begin（），end（））获得该值 - 但他们将完全知道它是一个O / li>
  

• there are few situations where maintaining an internal count so list::size() can be O(1) causes the splice operation to become linear
• there are probably many more situations where someone might be unaware of the negative effects that might happen because they call an O(N) size() (such as his one example where list::size() is called while holding a lock).
• that instead of permitting size() be O(N), in the interest of 'least surprise', the standard should require any container that implements size() to implement it in an O(1) fashion. If a container cannot do this, it should not implement size() at all. In this case, the user of the container will be made aware that size() is unavailable, and if they still want or need to get the number of elements in the container they can still use container::distance( begin(), end()) to get that value - but they will be completely aware that it's an O(N) operation.

我认为我倾向于同意他的大部分推理。但是，我不喜欢他建议添加到 splice（）重载。必须传递 n ，必须等于 distance（first，last）才能获得正确的行为难以诊断错误的配方。

I think I tend to agree with most of his reasoning. However, I do not like his proposed addition to the splice() overloads. Having to pass in an n that must be equal to distance( first, last) to get correct behavior seems like a recipe for hard to diagnose bugs.

我不确定应该或可以做什么，因为任何更改都会对现有代码产生重大影响。但是现在，我认为现有的代码已经受到影响 - 行为可能会相当显着不同，从一个实现到另一个应该已经明确定义的东西。也许关于大小为'缓存'和标记为已知/未知的一个人的评论可能工作很好 - 你得到摊销O（1）行为 - 唯一的时间，你得到O（N）行为是当列表被一些splice 。关于这一点的好处是，它可以由今天的实现者做，而不改变标准（除非我缺少一些东西）。

I'm not sure what should or could be done moving forward, as any change would have a significant impact on existing code. But as it stands, I think that existing code is already impacted - behavior might be rather significantly different from one implementation to another for something that should have been well-defined. Maybe onebyone's comment about having the size 'cached' and marked known/unknown might work well - you get amortized O(1) behavior - the only time you get O(N) behavior is when the list is modified by some splice() operations. The nice thing about this is that it can be done by implementors today without a change to the standard (unless I'm missing something).

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

这篇关于是list :: size（）真的O（n）吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！