C#: Is <Collection>.Count Expensive to Use?

Question

I'm writing a cache-eject method that essentially looks like this:

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

My question is about how Count is determined: is it just an internal int, or is it calculated by counting the elements each time its called?

Answer 1

In case of a HashSet it's just an internal int field and even SortedSet (a binary tree based set for .net 4) has its count in an internal field.

Answer 2

It is an internal value, and is not calculated. The documentation states that getting the value is an O(1) operation.

Answer 3

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

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

This guarantees that accessing the Count won't iterate over the whole collection.

---

Edit: as many other posters suggested, IEnumerable<...>.Count() is however not guaranteed to be O(1). Use with care!

IEnumerable<...>.Count() is an extension method defined in System.Linq.Enumerable. The current implementation makes an explicit test if the counted IEnumerable<T> is indeed an instance of ICollection<T>, and makes use of ICollection<T>.Count if possible. Otherwise it traverses the IEnumerable<T> (possible making lazy evaluation expand) and counts items one by one.

I've not however found in the documentation whether it's guaranteed that IEnumerable<...>.Count() uses O(1) if possible, I only checked the implementation in .NET 3.5 with Reflector.

Answer 4

It's an internal int that get incremented each time a new item is added to the collection.

Answer 5

Your question does not specify a specific Collection class so...

It depends on the Collection class. ArrayList has an internal variable that tracks the count, as does List. However, it is implementation specific, and depending on the type of the collection, it could theoretically get recalculated on each call.

Answer 6

As others have noted, Count is maintained when modifying the collection. This is nearly always the case with every collection type in the framework. This is considerably different than using the Count extension method on an IEnumerable which will enumerate the collection each time.

Also, with the newer collection classes the Count property is not virtual which means that the jitter can inline the call to the Count accessor which makes it practically the same as accessing a field. In other words, very quick.

Answer 7

According to Reflector, it is implemented as

public int Count{ get; }

so it is defined by the derived type

Answer 8

Just a quick note. Be ware that there are two ways to count a collection in .NET 3.5 when System.Linq is used. For a normal collection, the first choice should be to use the Count property, for the reasons already described in other answers.

An alternative method, via the LINQ .Count() extension method, is also available. The intriguing thing about .Count() is that it can be called on ANY enumerable, regardless of whether the underlying class implements ICollection or not, or whether it has a Count property. If you ever do call .Count() however, be aware that it WILL iterate over the collection to dynamically generate a count. That generally results in O(n) complexity.

The only reason I wanted to note this is, using IntelliSense, it is often easy to accidentally end up using the Count() extension rather than the Count property.