Get last element in a SortedDictionary

Question

I see this question.

How can I get the last element in a SortedDictionary in .Net 3.5.

Answer 1

You can use LINQ:

var lastItem = sortedDict.Values.Last();

You can also get the last key:

var lastkey = sortedDict.Keys.Last();

You can even get the last key-value pair:

var lastKeyValuePair = sortedDict.Last();

This will give you a KeyValuePair<TKey, TValue> with Key and Value properties.

Note that this will throw an exception if the dictionary is empty; if you don't want that, call LastOrDefault.

Answer 2

Last extension method will give you the result, but it will have to enumerate the entire collection to get you there. It's such a shame SortedDictionary<K, V> doesn't expose Min and Max members especially considering internally it is backed by a SortedSet<KeyValuePair<K, V>> which has Min and Max properties.

If O(n) is not desirable, you have a few options:

1. Switch to a SortedList<K, V>. Again for some reason BCL doesn't pack this by default. You can use indexers to get max (or min) value in O(1) time. Extending with extension methods will be nice.

   //Ensure you dont call Min Linq extension method.
   public KeyValuePair<K, V> Min<K, V>(this SortedList<K, V> dict)
   {
       return new KeyValuePair<K, V>(dict.Keys[0], dict.Values[0]); //is O(1)
   }
   
   //Ensure you dont call Max Linq extension method.
   public KeyValuePair<K, V> Max<K, V>(this SortedList<K, V> dict)
   {
       var index = dict.Count - 1; //O(1) again
       return new KeyValuePair<K, V>(dict.Keys[index], dict.Values[index]);
   }
   

   SortedList<K, V> comes with other penalties. So you might want to see: What's the difference between SortedList and SortedDictionary?

2. Write your own SortedDictionary<K, V> class. This is very trivial. Have a SortedSet<KeyValuePair<K, V>> as the internal container and base the comparison on the Key part. Something like:

   public class SortedDictionary<K, V> : IDictionary<K, V>
   {
       SortedSet<KeyValuePair<K, V>> set; //initialize with appropriate comparer
   
       public KeyValuePair<K, V> Min { get { return set.Min; } } //O(log n)
       public KeyValuePair<K, V> Max { get { return set.Max; } } //O(log n)
   }
   

   This is O(log n). Not documented, but I checked the code.

3. Use fiddly reflection to access the backing set which is private member of SortedDictionary<K, V> class and invoke Min and Max properties. One can rely on expressions to compile a delegate and cache it for performance. It's a very poor choice to do so. Can't believe I suggested this.

4. Rely on other implementations, for eg. For TreeDictionary<K, V> from C5. They have FindMin and FindMax both of which are O(log n)

Answer 3

You can use SortedDictionary.Values.Last();

or if you want the key and the value

SortedDictionary.Last();