C# – What’s the difference between SortedList and SortedDictionary

cgenericsnetsorteddictionarysortedlist

Is there any real practical difference between a SortedList<TKey,TValue> and a SortedDictionary<TKey,TValue>? Are there any circumstances where you would specifically use one and not the other?

Best Answer

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

This is the style that Microsoft tends to use in their examples.

It appears that the guidance in this area may have changed, as StyleCop now enforces the use of the C# specific aliases.

C# – the difference between const and readonly in C#

Apart from the apparent difference of

having to declare the value at the time of a definition for a const VS readonly values can be computed dynamically but need to be assigned before the constructor exits.. after that it is frozen.
const's are implicitly static. You use a ClassName.ConstantName notation to access them.

There is a subtle difference. Consider a class defined in AssemblyA.

public class Const_V_Readonly
{
  public const int I_CONST_VALUE = 2;
  public readonly int I_RO_VALUE;
  public Const_V_Readonly()
  {
     I_RO_VALUE = 3;
  }
}

AssemblyB references AssemblyA and uses these values in code. When this is compiled:

in the case of the const value, it is like a find-replace. The value 2 is 'baked into' the AssemblyB's IL. This means that if tomorrow I update I_CONST_VALUE to 20, AssemblyB would still have 2 till I recompile it.
in the case of the readonly value, it is like a ref to a memory location. The value is not baked into AssemblyB's IL. This means that if the memory location is updated, AssemblyB gets the new value without recompilation. So if I_RO_VALUE is updated to 30, you only need to build AssemblyA and all clients do not need to be recompiled.

So if you are confident that the value of the constant won't change, use a const.

public const int CM_IN_A_METER = 100;

But if you have a constant that may change (e.g. w.r.t. precision).. or when in doubt, use a readonly.

public readonly float PI = 3.14;

Update: Aku needs to get a mention because he pointed this out first. Also I need to plug where I learned this: Effective C# - Bill Wagner

Best Answer

Related Solutions

C# – the difference between String and string in C#

This is the style that Microsoft tends to use in their examples.

C# – the difference between const and readonly in C#

Related Topic