是<Collection>。使用昂貴的計數？

Question

我寫高速緩存彈出方法，基本上是這樣的：

while (myHashSet.Count > MAX_ALLOWED_CACHE_MEMBERS) 
{ 
    EjectOldestItem(myHashSet); 
} 

我的問題是關於如何Count確定：是它只是一個private或protected int，抑或是通過計算每個元素計算它的時間被稱爲？

Answer 1

從http://msdn.microsoft.com/en-us/library/ms132433.aspx：

檢索該屬性的值是O（1）的操作。

這保證訪問Count不會遍歷整個集合。

---

編輯：然而許多其他海報建議，IEnumerable<...>.Count()是不保證是O（1）。小心使用！

IEnumerable<...>.Count()是在System.Linq.Enumerable中定義的擴展方法。如果計數的IEnumerable<T>確實是ICollection<T>的一個實例，並且如果可能的話使用ICollection<T>.Count，則當前的實現進行明確的測試。否則，它會遍歷IEnumerable<T>（可能使延遲評估展開）並逐個計數項目。

在文檔中我還沒有發現是否確保IEnumerable<...>.Count()使用O（1），如果可能的話，我只使用Reflector在.NET 3.5中檢查實現。

---

必要下旬另外：許多流行的容器不從Collection<T>衍生的，但儘管如此，他們的Count屬性爲O（1）（即，不會在整個訪問集合）。例子是HashSet<T>.Count（這個很可能是OP想要詢問的），Dictionary<K, V>.Count,LinkedList<T>.Count,List<T>.Count,Queue<T>.Count，Stack<T>.Count等等。

所有這些集合實施ICollection<T>或只是ICollection，所以他們Count是ICollection<T>.Count（或ICollection.Count）的實現。根據文檔，對ICollection<T>.Count的實現不需要執行O（1）操作，但上面提到的操作是這樣做的。

（注旁白：一些容器，例如，Queue<T>，實行非通用ICollection但不ICollection<T>，所以他們「繼承」只有從ICollection的Count財產。）

Answer 2

在HashSet的情況下，它只是一個內部int場和偶數SortedSet（二叉樹基於.net的4集）有它的內場數。

Answer 3

這是一個內部值，不計算。 documentation指出獲取該值是O（1）操作。

Answer 4

這是一個內部的int，每次向該集合中添加新項目時都會增加。

Answer 5

你的問題沒有指定特定收集類等等......

這取決於集合類。 ArrayList有一個跟蹤計數的內部變量，就像List一樣。但是，它是特定於實現的，並且根據集合的類型，理論上可以在每次調用時重新計算。

Answer 6

正如其他人所指出的，修改集合時保持Count。框架中的每種集合類型幾乎都是這種情況。這與在每次枚舉集合的IEnumerable上使用Count擴展方法大不相同。

另外，對於較新的集合類，Count屬性不是虛擬的，這意味着抖動可以內聯對Count訪問器的調用，這使得它實際上與訪問字段相同。換句話說，非常快。

Answer 7

根據反射器，它是作爲

public int Count{ get; } 

所以它是由派生類型

Answer 8

只是一個快速的音符定義。當使用System.Linq時，有兩種方法可以計算.NET 3.5中的集合。對於一個普通的集合，第一個選擇應該是使用Count屬性，因爲其他答案中已經描述過的原因。

另一種方法，通過LINQ .Count（）擴展方法也可用。關於.Count（）的有趣之處在於，它可以在任何枚舉上調用，而不管基礎類是否實現ICollection，或者它是否具有Count屬性。如果您曾經調用過.Count（），請注意，它會遍歷集合以動態生成計數。這通常會導致O（n）的複雜性。

我想要說明的唯一原因是，使用IntelliSense，通常很容易意外地最終使用Count（）擴展而不是Count屬性。