sorted collections

Question

I'm trying to get my head around the C# sorted collections such as SortedList and SortedDictionary. I have two main mental blockers and I can't find anywhere that explains them clearly. I understand that there is a default way in which these collections keep themselves sorted, and that you can also specify this.

I suppose my question is simply; How is this done? I can't find any simple examples of how to write these things.

Say for example I wanted a collection to store key value pairs from float to int, I want to be able to grab the int by querying the collection for the lowest float value. In other words I want to get the int with the lowest associated float key. Am I right in thinking that the fact that the collection is sorted makes it more efficient to do this kind of thing? Does this also mean that I can just grab the first element in the collection like: collection[0]? and it will be the lowest? (if i've sorted it that way)

Sorry this question is not more succinct, I'm just not sure where to start.

Answer 1

SortedDictionary doesn't give you an integer indexer nor a "get minimum key" function; SortedList does. SortedList is super inefficient, however, if you're inserting the data out of order. You should order it first and then build the list.

If the only function you require that's missing from SortedDictionary is "get minimum key" then you can use the First or FirstOrDefault linq method, since the enumerator returns the key-value pairs in key order. If you need other similar functions (like "get maximum key"), and you also require more efficient insertions and deletions of randomly-distributed values, you should probably make your own implementation of a binary tree (which SortedDictionary is) that exposes these functions.

To implement IComparer<T>, create a new class:

public class FloatComparer : IComparer<float>
{
    public int Compare(float a, float b)
    {
        //your logic goes here; return -1 if a should be considered smaller or 1 if b should be considered smaller
    }
}

Then pass it to the constructor of the sorted collection in the usual way:

var collection = new SortedDictionary<float>(new IComparer<float>());

Answer 2

read up on data structures like trees and heaps etc. start with Red Black Tree. I guess that is the classic example. google and wikipedia helps.

Basically the stuff you insert has some kind of a definition which allows it to be compared for larger, equal, smaller than. On insertion the elements are compared and sorted. So when you search for the first or last you know that they are smallest or largest. You can also efficiently check if there is an integer equal to 4 in the structure for example.

Answer 3

The SortedDictionary is a balanced tree, while SortedList is just a continuous slab of memory that happens to contain ordered elements. In both cases, we need to define what "less than" means, so the tree can organize its nodes and the sorted list can order its elements:

• If you pass an object that implements IComparer to the constructor of these containers, that is what gets used. As long as it is a strict weak ordering it will work fine. For example, it's easy to sort the container in reverse by supplying a "greater than" comparer.
• Otherwise, a default comparer is used.

In your case (where float is the key), the default comparer will do the right thing and order the elements from lowest to highest value. Getting the first element will be efficient and the first element also happens to be the lowest value.

Answer 4

It's easy.

Say you have a Sorted Dictionary called series that associates an array of doubles with a date.

public SortedDictionary series = new SortedDictionary();

And you have loaded it up with data.

You can get the first item (first in sorted order) as follows:

  var firstItem = series.First();

  firstItem.Key is the first date.

  firstItem.Value is the array of doubles associated with the first date

Happy programming!