Sortedlist<>, Sorteddictionary<> and Dictionary<>

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

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

when should I use a sorteddictionary instead of a dictionary

A SortedDictionary is implemented as a binary search tree. Therefore, accessing an element is O(lg(n)). A Dictionary is a hash table, and has a complexity of O(1) for access.

A SortedDictionary is quite useful when you need the data to be sorted (a Dictionary has no defined order). Dictionary is appropriate for most cases.

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

How do you sort a dictionary by value?

Use:

using System.Linq.Enumerable;
...
List<KeyValuePair<string, string>> myList = aDictionary.ToList();

myList.Sort(
    delegate(KeyValuePair<string, string> pair1,
    KeyValuePair<string, string> pair2)
    {
        return pair1.Value.CompareTo(pair2.Value);
    }
);

Since you're targeting .NET 2.0 or above, you can simplify this into lambda syntax -- it's equivalent, but shorter. If you're targeting .NET 2.0 you can only use this syntax if you're using the compiler from Visual Studio 2008 (or above).

var myList = aDictionary.ToList();

myList.Sort((pair1,pair2) => pair1.Value.CompareTo(pair2.Value));

Getting i-th value from a SortedList or SortedDictionary

Try something like this:

list.Values[list.Count / 2];

Note that a true median would average the two numbers in the middle if Count is even.

C# Sortable collection which allows duplicate keys

Thanks a lot for your help. While searching more, I found this solution. (Available in Stackoverflow.com in other question)

First, I created a class which would encapsulate my objects for classes (Headers,Footer etc)

public class MyPosition
{
    public int Position { get; set; }
    public object MyObjects{ get; set; }
}

So this class is supposed to hold on the objects, and PosX of each object goes as int Position

List<MyPosition> Sequence= new List<MyPosition>();
Sequence.Add(new MyPosition() { Position = 1, Headerobject });
Sequence.Add(new MyPosition() { Position = 2, Headerobject1 });
Sequence.Add(new MyPosition() { Position = 1, Footer });

League.Sort((PosA, PosB) => PosA.Position.CompareTo(PosB.Position));

What eventually I get is the sorted "Sequence" list.

How to iterate over a dictionary?

foreach(KeyValuePair<string, string> entry in myDictionary)
{
    // do something with entry.Value or entry.Key
}

.NET HashTable Vs Dictionary - Can the Dictionary be as fast?

System.Collections.Generic.Dictionary<TKey, TValue> and System.Collections.Hashtable classes both maintain a hash table data structure internally. None of them guarantee preserving the order of items.

Leaving boxing/unboxing issues aside, most of the time, they should have very similar performance.

The primary structural difference between them is that Dictionary relies on chaining (maintaining a list of items for each hash table bucket) to resolve collisions whereas Hashtable uses rehashing for collision resolution (when a collision occurs, tries another hash function to map the key to a bucket).

There is little benefit to use Hashtable class if you are targeting for .NET Framework 2.0+. It's effectively rendered obsolete by Dictionary<TKey, TValue>.

---

Related Topics