是<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属性。