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

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 2

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 3

You can use SortedDictionary.Values.Last();

or if you want the key and the value

SortedDictionary.Last();

Answer 4

SortedList list...

list[ Keys[Keys.Count - 1] ];  // returns the last entry in list

Answer 5

As folks have already pointed Last extension will enumerate the entire collection, its impact on perf can be deadly. Just to remove 10000 last elements from SortedDict, it took a lot more time than similar operation on SortedSet.

1. SortedSet Removal Elapsed ms : 8

2. SortedDict Removal Elapsed ms : 3697

   // In below code,ss is SortedSet and sd is SortedDictionary and both contain same 10000 elements.

    sw.Start();
    while (ss.Count != 0)
    {
        ss.Remove(ss.Max);
    }
   
    sw.Stop();
    Console.WriteLine("SortedSet Removal Elapsed ms : {0}", sw.ElapsedMilliseconds);
   
    sw.Reset();
   
    sw.Start();
    while (sd.Count != 0)
    {
        sd.Remove(sd.Keys.Last());
    }
   
    sw.Stop();
    Console.WriteLine("Dict Removal Elapsed ms : {0}", sw.ElapsedMilliseconds);