How fast are Count and Capacity?

Question

I often write code like this:

if ( list.Count > 0 ) { }

Is this efficient? Does this operation look like:

• Iterate through the list and count its elements
• Result: 986,000 elements
• Is 986,000 greater than 0?
• return true

Or like this:

• Retrieve the stored number of elements in the list (986,000)
• Is 986,000 greater than 0?
• return true

That is, to get the number of elements in the list, do you have to count all the way through the list, or is the number of elements recorded somewhere? And is this the case for all ICollection classes?

What about the Capacity of the list?

Answer 1

I often write code like this: if ( list.Count > 0 ) { } Is this efficient?

Yes. That retrieves the count in the list, which is stored in a field inside the list, and compares it to zero.

Now a question you did not ask:

What about if ( sequence.Count() > 0 ) { } ? (Notice the parentheses on Count().)

We interrogate the sequence at runtime to see if it is a list that has a Count property that can be computed efficiently. If it does, we call it. If not, we count the entire sequence one item at a time, and then compare that to zero.

Isn't that incredibly inefficient?

Yes.

What would be more efficient?

if (sequence.Any())

Why is that more efficient?

Because it attempts to iterate over one element. If it succeeds, then Any is true; if it fails then Any is false. You don't need to count the number of jellybeans in the jar in order to know if there are more than zero. You only need to look to see if there is at least one.

In addition to being considerably more efficient, the code now reads like the intended meaning of the code. If you are intending to ask "are there any items in the list?" then ask "are there any items in the list?" and not "is the number of items in the list greater than zero?"

What about the Capacity property of a list?

That tells you how much space has been pre-allocated in the list's internal data structures. It is the amount of items the list can store before it has to allocate more memory.

Answer 2

The Count property in List<T> - and all other ICollection<T> implementations in the BCL - is an O(1) operation, that means it is fast and independent of the number of the number of elements in the list.

There also exists an extension method Count() that can be called on any IEnumerable<T>. This method is O(n), which means its runtime depends on the number of elements in the enumerable. However, there is one exception: If the enumerable really is an implementation of ICollection<T> or ICollection it uses the Count property making it again an O(1) operation.

---

The Capacity property is normally nothing you need to worry about.