<Collection> .Count是否使用昂贵？

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.如果count 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>,因此它们Count仅从from "继承"该属性ICollection.)

Answer 2

您的问题未指定特定的 Collection类,因此......

这取决于Collection类.ArrayList有一个跟踪计数的内部变量,List也是如此.但是,它是特定于实现的,并且根据集合的类型,理论上可以在每次调用时重新计算.

Answer 3

它是一个内部值,不计算.该文档指出获取值是O(1)的操作.

Answer 4

正如其他人所说,修改集合时会保留Count.框架中的每个集合类型几乎都是这种情况.这与在IEnumerable上使用Count扩展方法有很大不同,IEnumerable每次都会枚举集合.

此外,对于较新的集合类,Count属性不是虚拟的,这意味着抖动可以内联对Count访问器的调用,这使得它实际上与访问字段相同.换句话说,非常快.