Performance of First() vs Last() on a SortedDictionary

Question

I'm using SortedDictionaries to simulate a Queue (due to some requirements that I have), and I'm calling Last() over the sorted dictionary to get the item that I need to dequeue.

I was just wondering about the performance of using a custom comparer and calling First() or keep calling Last().

After decompiling the .NET 3.5 assemblies, I found that the SortedDictionary class does have a Count property, so I'm guessing the framework just returns the item at position 0 when First is called, and the item at position [count-1] when Last is called, am I right?

Answer 1

No.

Since SortedDictionary does not implement IList<TValue> (which has a this[int] indexer), Last() has no choice but to iterate through the whole thing.

Answer 2

The Last method is an extension method in the Enumerable class. The implementation of Last first tries to cast the IEnumerable (your SortedDictionary) to IList<T>. If it can, then it uses the Count property to directly access the last element. If it can't, then it has to iterate over all elements to get to the last one. SortedDictionary doesn't implement IList<T>, so Last will iterate over all elements.