CODEWITHSUNDEEP
c#collectionssorteddictionary
leora
leora

Reputation: 196539

Get last element in a SortedDictionary

I see this question.

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

Upvotes: 16

Views: 21436

Answers (5)

Ujjwal Uttaray
Ujjwal Uttaray

Reputation: 1

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);

Upvotes: 0

DakotaTimber
DakotaTimber

Reputation: 11

SortedList list...

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

Upvotes: 0

nawfal
nawfal

Reputation: 73183

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)

Upvotes: 28

SLaks
SLaks

Reputation: 887459

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.

Upvotes: 21

kemiller2002
kemiller2002

Reputation: 115488

You can use SortedDictionary.Values.Last();

or if you want the key and the value

SortedDictionary.Last();

Upvotes: 2

Related Questions