c# - .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 :

Retrieving the value of this property is an O(1) operation.

这保证访问 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> ，因此它们仅从 Count “继承”了 ICollection 属性。)