What’s the difference between SortedList and SortedDictionary?

by

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

More Related Contents:

  1. SortedList, SortedDictionary and Dictionary
  2. When to use a SortedList over a SortedDictionary?
  3. What exactly is an “open generic type” in .NET? [duplicate]
  4. Generics in C#, using type of a variable as parameter [duplicate]
  5. Create instance of generic type whose constructor requires a parameter?
  6. A generic list of anonymous class
  7. No generic implementation of OrderedDictionary?
  8. Why must I provide explicitly generic parameter types While the compiler should infer the type?
  9. Func with out parameter
  10. Is there a Lower Bound function on a SortedList?
  11. Why isn’t ArrayList marked [Obsolete]?
  12. Convert string to nullable type (int, double, etc…)
  13. How to initialize a List to a given size (as opposed to capacity)?
  14. Generic Type in constructor
  15. A reusable pattern to convert event into task
  16. Collection of generic types
  17. C# Sortable collection which allows duplicate keys
  18. What does denote in C# [duplicate]
  19. How do I create a generic class from a string in C#? [duplicate]
  20. Parse string to enum type
  21. Wildcard equivalent in C# generics
  22. Ambiguous call between two C# extension generic methods one where T:class and other where T:struct
  23. How do I tell if a type is a “simple” type? i.e. holds a single value
  24. Generics can’t infer second parameter? [duplicate]
  25. Can I have a variable number of generic parameters?
  26. How to define generic type limit to primitive types?
  27. Which C# method overload is chosen?
  28. Are static members of a generic class tied to the specific instance?
  29. Convert DataTable to List
  30. generic NOT constraint where T : !IEnumerable

Leave a Comment