title: When to use a SortedList<TKey, TValue> over a SortedDictionary<TKey, TValue>?
body: <p>This may appear to be a duplicate of this <a href="https://stackoverflow.com/questions/935621/whats-the-difference-between-sortedlist-and-sorteddictionary">question</a>, which asks "What’s the difference between <a href="http://msdn.microsoft.com/en-us/library/ms132319.aspx" rel="noreferrer">SortedList</a> and <a href="http://msdn.microsoft.com/es-mx/library/f7fta44c.aspx" rel="noreferrer">SortedDictionary</a>?" Unfortunately, the answers do nothing more than quote the MSDN documentation (which clearly states that there are performance and memory use differences between the two) but don't actually answer the question.</p>
  
  <p>In fact (and so this question doesn't get the same answers), according to MSDN:</p>
  
  <blockquote>
    <p>The <code>SortedList&lt;TKey, TValue&gt;</code> 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
    <code>SortedDictionary&lt;TKey, TValue&gt;</code> 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:</p>
    
    <ul>
    <li><p><code>SortedList&lt;TKey, TValue&gt;</code> uses less
    memory than <code>SortedDictionary&lt;TKey,
    TValue&gt;</code>.</p></li>
    <li><p><code>SortedDictionary&lt;TKey, TValue&gt;</code> has
    faster insertion and removal
    operations for unsorted data, O(log n)
    as opposed to O(n) for
    <code>SortedList&lt;TKey, TValue&gt;</code>.</p></li>
    <li><p>If the list is populated all at once
    from sorted data, <code>SortedList&lt;TKey,
    TValue&gt;</code> is faster than
    <code>SortedDictionary&lt;TKey, TValue&gt;</code>.</p></li>
    </ul>
  </blockquote>
  
  <p>So, clearly this would indicated that <code>SortedList&lt;TKey, TValue&gt;</code> is the better choice <strong>unless</strong> you need faster insert and remove operations for <strong>unsorted</strong> data.</p>
  
  <p>The question still remains, given the information above what are the practical (real-world, business case, etc.) reasons for using a <code>SortedDictionary&lt;TKey, TValue&gt;</code>? Based on the performance information, it would imply that there really is no need to have <code>SortedDictionary&lt;TKey, TValue&gt;</code> at all.</p>