[ACCEPTED]-Get last element in a SortedDictionary-sorteddictionary

Accepted answer
Score: 25

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

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

  1. Switch to a SortedList<K, V>. Again for 16 some reason BCL doesn't pack this by default. You 15 can use indexers to get max (or min) value 14 in O(1) time. Extending with extension methods 13 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 12 you might want to see: What&#39;s the difference between SortedList and SortedDictionary?

  2. Write your own SortedDictionary<K, V> class. This 11 is very trivial. Have a SortedSet<KeyValuePair<K, V>> as the internal 10 container and base the comparison on the 9 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 8 documented, but I checked the code.

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

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

Score: 21

You can use LINQ:

var lastItem = sortedDict.Values.Last();

You can also get the last 5 key:

var lastkey = sortedDict.Keys.Last();

You can even get the last key-value 4 pair:

var lastKeyValuePair = sortedDict.Last();

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

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

Score: 2

You can use SortedDictionary.Values.Last();

or if you want the key and the 1 value

Score: 0

SortedList list...

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


Score: 0

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

  1. SortedSet Removal Elapsed ms 3 : 8

  2. SortedDict Removal Elapsed ms : 3697

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

     while (ss.Count != 0)
     Console.WriteLine("SortedSet Removal Elapsed ms : {0}", sw.ElapsedMilliseconds);
     while (sd.Count != 0)
     Console.WriteLine("Dict Removal Elapsed ms : {0}", sw.ElapsedMilliseconds);

More Related questions