問題描述

最近，我注意到有人提到 std::list::size() 具有線性復雜度.
根據 some sources，這實際上取決于實現，因為標準沒有說明復雜性是什么.
在此博客條目中的評論說:

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正在使用.微軟 Visual Studio V6將 size() 實現為 {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 答案

您是正確的，標準沒有說明 list::size() 的復雜性必須是什么 - 但是，它確實建議它應該具有恒定的復雜性"(表中的注釋 A65).

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(1) 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

我認為論文的主要觀點是:

I think the main points in the paper are:

• 很少有維護內部計數的情況，所以 list::size() 可以是 O(1) 導致拼接操作變成線性
• 可能還有更多情況，某人可能不知道可能發生的負面影響，因為他們調用了 O(N) size()(例如他的一個示例，其中 list::size() 在持有鎖時被調用).
• 不是允許 size() 是 O(N)，為了最少驚喜"，標準應該要求任何實現 size() 的容器以 O(1) 的方式實現它.如果容器不能做到這一點，它根本不應該實現 size().在這種情況下，容器的用戶將知道 size() 不可用，如果他們仍然想要或需要獲取容器中元素的數量，他們仍然可以使用 container::distance( begin(), end()) 來獲取該值 - 但他們會完全意識到這是一個 O(N) 操作.

• 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() 重載的添加.必須傳入必須等于 distance( first, last) 的 n 才能獲得正確的行為，這似乎是難以診斷錯誤的秘訣.

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) 嗎?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！