When to Use a Sortedlist<Tkey, Tvalue> Over a Sorteddictionary<Tkey, Tvalue>

What's the difference between SortedList and SortedDictionary?

Yes - their performance characteristics differ significantly. It would probably be better to call them SortedList and SortedTree as that reflects the implementation more closely.

Look at the MSDN docs for each of them (SortedList, SortedDictionary) for details of the performance for different operations in different situtations. Here's a nice summary (from the SortedDictionary docs):

The SortedDictionary<TKey, TValue> generic
class is a binary search tree with
O(log n) retrieval, where n is the
number of elements in the dictionary.
In this, it is similar to the
SortedList<TKey, TValue> generic
class. The two classes have similar
object models, and both have O(log n)
retrieval. Where the two classes
differ is in memory use and speed of
insertion and removal:

• SortedList<TKey, TValue> uses less
  memory than SortedDictionary<TKey,
TValue>.

• SortedDictionary<TKey, TValue> has
  faster insertion and removal
  operations for unsorted data, O(log n)
  as opposed to O(n) for
  SortedList<TKey, TValue>.

• If the list is populated all at once
  from sorted data, SortedList<TKey,
TValue> is faster than
  SortedDictionary<TKey, TValue>.

(SortedList actually maintains a sorted array, rather than using a tree. It still uses binary search to find elements.)

SortedList, SortedDictionary and Dictionary

1. When iterating over the elements in either of the two, the elements will be sorted. Not so with Dictionary<T,V>.

2. MSDN addresses the difference between SortedList<T,V> and SortedDictionary<T,V>:

The SortedDictionary(TKey, TValue) generic class is a binary search
tree with O(log n) retrieval, where n is the number of elements in
the dictionary. In this respect, it is similar to the SortedList(TKey,
TValue) generic class. The two classes have similar object models, and
both have O(log n) retrieval. Where the two classes differ is in
memory use and speed of insertion and removal:

SortedList(TKey, TValue) uses less memory than SortedDictionary(TKey,
TValue).

SortedDictionary(TKey, TValue) has faster insertion and removal
operations for unsorted data: O(log n) as opposed to O(n) for
SortedList(TKey, TValue).

If the list is populated all at once from sorted data,
SortedList(TKey, TValue) is faster than SortedDictionary(TKey,
TValue).

Why SortedListTKey, TValue doesn't use pointers for the values?

This should not surprise you, it is well documented in the MSDN article for SortedList:

SortedDictionary has faster insertion and removal operations for unsorted data, O(logn) as opposed to O(n) for SortedList.

SortedDictionary uses a red-black tree (i.e. "pointers"), SortedList is an array. You choose between the two based on what you do with the collection. Both are O(logn) for lookup, but if you iterate the collection frequently then you can be ahead with SortedList a great deal. It uses the cpu caches much more effectively. Makes a huge difference on modern machines.

Also do note that the efficiency of adding items to the collections is heavily dependent on how sorted the items are. A SortedDictionary really likes random data, gives it much better odds of not having to re-balance the trees. Having it sorted gives it worst-case O(n) behavior. SortedList really likes sorted items, makes adding O(1).

Can a SortedList/SortedDictionary with a properly implemented comparer be used to guarantee insertion order?

A comparer must obey the law

Compare(a, b) == -Compare(b, a) //assuming only possible values are -1, 0, 1

This is the symmetry property. Your sample code does not obey it. Therefore the BCL collections do not give you any guarantee at all. You have violated the documented contract.

You can't do this.

Instead, you could add a new field to M where you store the insertion order as an int. You can then use that field in the comparer.

Dictionary vs SortedList for data storage and processing

Use SortedDictionary<TKey, TValue> Class.

SortedDictionary<DateTime, Class2> dict = new SortedDictionary<DateTime, Class2>();

Following from the documentation explains well about the difference between using a SortedList vs SortedDictionary

The SortedDictionary<TKey, TValue> generic class is a binary search
tree with O(log n) retrieval, where n is the number of elements in
the dictionary. In this respect, it is similar to the
SortedList<TKey, TValue> generic class. The two classes have similar
object models, and both have O(log n) retrieval. Where the two classes
differ is in memory use and speed of insertion and removal:

• SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data: O(log n) as opposed to
  O(n) for SortedList<TKey, TValue>.

• If the list is populated all at once from sorted data, SortedList<TKey, TValue> is faster than SortedDictionary<TKey, TValue>.

For your question:

What's the best practice for creating the list (of Value1)?

List<decimal> list = dict.Values.Select(r=> r.Value1).ToList();

For your comment:

how to form a list consisting of Values1, say, for the last 3 days

List<decimal> listOfValue1 = dict.Where(r=> r.Key >= DateTime.Today.AddDays(-3) 
                                            &&  r.Key <= DateTime.Today)
                                 .Select(r=> r.Value.Value1)
                                 .ToList();

C#: does SortedListTKey,TValue implement IReadOnlyDictionaryTKey,TValue?

It doesn't say you can't pass them, it just says it doesn't know how. You can manually cast the objects to IReadOnlyCollection.

        funcIROCollKvp1((IReadOnlyCollection < KeyValuePair<int, string> > )listkvp);
        funcIROCollKvp1((IReadOnlyCollection < KeyValuePair<int, string> > )dict);

Which class type should I use for sorted collection with key updating and value lookup

You could use a List<Character>, or an array excluding the player's character. You keep the List<Character> sorted with the highest aggro value at the front. To keep everything sorted every frame you run quicksort first. Once a Character has a lower aggro value than the player's aggro threshhold you escape out of the method.

If aggro is above the threshold just run the aggro check.

You could extend this to work for multiplayer by having a List<Player>.
Something like:

void quicksort(List<Enemy> enemies, int first, int last)
{
   int left = first;
   int right = last;
   int pivot = first;
   first++;

   while (last >= first)
   {
       if(enemies[first].Aggro >= enemies[pivot].Aggro &&
           enemies[last].Aggro < enemies[pivot].Aggro)
           swapp(enemies, first, last)
       else if(enemies[first].Aggro >= enemies[pivot].Aggro)
         last--;
       else if(enemies[last].Aggro < colliders[pivot].Aggro)
         first++;
       else
       {
            last--;
            first++;
       }
   }

   swap(enemies, pivot, last);
   pivot = last;
   if(pivot > left)
      quicksort(enemies, left, pivot);
   if(right > pivot + 1)
     quicksort(enemies, pivot + 1, right);
}

void swap(List<Enemy> enemies, int left, right)
{
   var temp = enemies[right];
   enemies[right] = enemies[left];
   enemies[left] = temp;
}

void CheckAggro()
{
   quicksort(enemies, 0, enemies.Count - 1);
   for(int = 0; i < players.Count; i++)
   {
       for(int j = 0 < enemies.Count; j++)
       {
           if(players[i].AggroThreshhold < enemies[j].Aggro)
           {
                break;
           }
           // Perform what happens when enemy is high on aggro threshold.
       }
   }
}

If players have different aggro thresholds you could save all of the enemies who have aggro above the minimum to a separate List, and then do a check against that from the player with the lowest to highest threshold. Just keep the list of players sorted with the lowest aggro threshold first.

Is there a usual style for using C#'s SortedDictionaryKey, Value when you don't care about the value?

If Value is a reference type, storing it would waste from 4 to 8 bytes, depending on whether the process is 32-bit or 64-bit. If Value is a value type, it may waste even more.

If you don't need it, you can set Value to Byte. You can't go lower than 1 byte even with an empty struct. You can set to any value, probably 0 is a good choice.

Ideally, if all you need is a set, you should use a set.

There's a SortedSet<T> in .NET 4.0+ which uses a tree internally. In fact, SortedDictionary<TKey, TValue> uses SortedSet<KeyValuePair<TKey, TValue>> internally.

The set counterpart of SortedList<TKey, TValue> is a List<T>, I guess. You'll just need to use binary search and insert values into sorted positions. Implementing ISet<T> should be simple.

---

Related Topics