.NET 1.1

The SortedList Collection

The thirty-ninth part of the C# Fundamentals tutorial describes the use of the SortedList class. This dictionary collection provides a hybrid of the Hashtable and Array types; each entry being a key / value pair sorted according to the key's contents.

The SortedList Collection

The SortedList collection is described above as a hybrid between the Hashtable and Array data structures. The collection type is a dictionary, containing key / value pairs as with other dictionaries, such as the Hashtable. However, the items in the SortedList are automatically sorted according to the data in the key. This means that, unlike the Hashtable, the SortedList's contents have a definite order and can be accessed using an index number as well as by looking up the key.

Internally, the Sorted list has two arrays that store the keys and the values separately. As items are added, the key is inserted into the keys array in the correct place to maintain the sort order. The value is then inserted at the corresponding position in the values array. As with a Hashtable, this pairing of key and value can be accessed as a DictionaryEntry. Each DictionaryEntry may have objects for its key and value although the key part may not be null, must be unique and must support the IComparable interface that permits items to be compared and therefore sorted.

The SortedList provides additional functionality over the Hashtable because of its ability to be addressed by index numbers and due to its automatic sorting. However, it should be noted that this additional functionality reduces the performance of the SortedList when compared with the Hashtable.

Implemented Collection Interfaces

The SortedList collection implements the properties and methods of the IDictionary and ICollection interfaces. This behaviour is described in the earlier Collection Interfaces article. The rest of this article describes the additional functionality provided by SortedList.

Declaring a SortedList

Constructors

The SortedList class provides six constructors for instantiating a new dictionary. The first constructor is the most basic, as it requires no parameters. The new, empty collection is generated with the capacity to store several items. When additional items are added, the capacity of the collection doubles automatically. It doubles again each time the capacity of the SortedList is exceeded.

The SortedList class is found in the System.Collections namespace so to execute the examples, add using System.Collections; to the source code.

If the maximum number of items that will be stored in a SortedList is known before the collection is created, it is more efficient to declare the capacity required when the object is created. If the size is underestimated and the stated capacity is exceeded, the capacity will still be doubled to accommodate extra items. To declare the initial capacity of a SortedList, the capacity is passed to the constructor as an integer parameter.

One of the key features of the SortedList collection is the facility to have the keys automatically ordered. By default, the sort order is based upon the IComparer interface implementation of each key. However, this can be overridden with alternative ordering by passing a comparer to the constructor. The use of IComparer is a complex subject that is beyond the scope of a beginner's tutorial. However, as an example, the following code creates a SortedList that performs case-insensitive sorting of the keys.

NB: With a case-insensitive sort, the keys themselves are case-insensitive. This means that adding keys of "abc" and "ABC" generates an exception as the keys are not considered to be unique.

The functionality of the above two constructors can be combined. When the comparer and the initial capacity of the SortedList are to be specified, both may be passed as parameters. The comparer is the first parameter and the capacity is the second.

In some cases you may already have a dictionary collection that you wish to use to initialise the contents of a SortedList. The fifth constructor creates and fully populates a SortedList using the contents of any other collection that supports the IDictionary interface. Every item in the dictionary passed as the constructor's only parameter is copied into the new collection. In the following example, the contents of a Hashtable are used to populate the new SortedList.

Hashtable myTable = new Hashtable();

myTable.Add("key1","value1");

SortedList myList = new SortedList(myTable);    // Copies myTable into myList

Finally, you may wish to populate a SortedList from an existing dictionary's contents and also specify the comparison type to use for ordering the items. By passing the dictionary as the constructor's first parameter and the comparer as its second, this can be achieved.

Hashtable myTable = new Hashtable();

myTable.Add("key1","value1");

SortedList myList = new SortedList(myTable, new CaseInsensitiveComparer());

Modifying SortedList Contents

Adding an Item

All dictionary collection types that implement IDictionary include the basic Add method for adding a new item. This is therefore supported by the SortedList class. As described above, the key being added must be unique and may not be null. Duplicate keys cause an ArgumentException to be thrown. If an attempt is made to add a null key, an ArgumentNullException occurs.

SortedList myList = new SortedList();

myList.Add("key1","value1");
myList.Add("key1","value2");                // Duplicate: ArgumentException
myList.Add(null,"value2");                  // Null Key: ArgumentNullException

Updating Using the Key

The SortedList can be modified directly using the key as if it were an array's index number. The key is appended to the collection's name between square brackets. If the key assigned to already exists, the value of the corresponding item is updated. If the key does not exist, the key and the value are added to the SortedList as a new item.

SortedList veg = new SortedList();

veg["cabbage"] = "Red";                     // New item created
veg["cabbage"] = "Savoy";                   // Item updated
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

Updating Using the Index Number

It is possible to access the items in a sorted list using their index numbers rather than using keys. Unlike an array, this is not possible by simply adding the index number in square brackets; this would cause potential conflicts between index numbers and numeric keys. To use the index number to change the value of an existing item, the SetByIndex method is called. The method has two parameters: the first is the index number of the entry to be updated, the second is the new value.

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

veg.SetByIndex(0, "Late Flat Dutch");       // Item updated

NB: Remember that the index number is not related to the order in which items were added to the collection. It is based upon the positions of the items after sorting. In the above example the update only works because we know that 'cabbage' is the first key when sorted alphabetically.

Removing an Item

As with all dictionaries, the SortedList permits items to be removed using the Remove method. This removes the item from the collection that matches a specified key. The SortedList also provides an addition method that removes an item based upon its index number. This is the RemoveAt method.

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

veg.RemoveAt(0);                            // Item removed

Reading SortedList Information

Retrieving an Item by Index

The SortedList collection is a dictionary and, as such, permits an item to be read using a key as a reference. In addition, the SortedList can access items using their index number. The GetByIndex method provides this functionality.

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

Console.WriteLine(veg.GetByIndex(0));       // Outputs "Savoy"

Retrieving a Key by Index

In addition to being able to retrieve a value from a SortedList by index number, the key may also be found in this manner. The GetKey method uses a similar syntax to GetByIndex, requiring a single integer parameter holding the index number to look up.

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

Console.WriteLine(veg.GetKey(0));           // Outputs "cabbage"

Iterating Using DictionaryEntry Objects

When an item is added to a SortedList, the key and the value elements are combined into a single object of the type DictionaryEntry. Using the foreach statement, it is possible to iterate through each item and extract its key and value from the DictionaryEntry object. The following example outputs the details of each key / value pair to the console. Note that the items in the collection have been sorted after they were added.

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

foreach(DictionaryEntry de in veg)
    Console.WriteLine("{0}\t: {1}", de.Key, de.Value);

/* OUTPUT

cabbage : Savoy
carrot  : Imperator
lettuce : Iceberg
potato  : King Edward

*/

Values

In most cases you will not want to iterate through the list of DictionaryEntry objects as you will only want to interrogate the value of each item. The Values property returns an ICollection object that contains only the values for each item in the SortedList. This can be looped through directly. The order of the items in the collection matches the order of the sorted keys.

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

foreach(string value in veg.Values)
    Console.WriteLine(value);

/* OUTPUT

Savoy
Imperator
Iceberg
King Edward

*/

Keys

The Keys property is similar to the Values property. It returns an ICollection object containing all of the keys of the items in a SortedList.

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

foreach(string value in veg.Keys)
    Console.WriteLine(value);

/* OUTPUT

cabbage
carrot
lettuce
potato

*/

GetValueList and GetKeyList Methods

The Values property returns a collection of all of the values within the SortedList. The functionality of this collection is limited to that of the ICollection interface. The GetValueList method returns the same information as Values except that the read only collection returned is based upon the IList interface. The GetKeyList method gives the same functionality for the keys in the SortedList. These methods can be useful because the IList interface has richer behaviour than ICollection. For more details of these interfaces, read the earlier Collection Interfaces article

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

IList keys = veg.GetKeyList();
IList values = veg.GetValueList();

ContainsKey

All collections that implement IDictionary include a method named Contains that returns a Boolean value indicating if a specified key exists within the collection. The SortedList includes this method and another named ContainsKey that provides exactly the same functionality.

ContainsValue

In addition to determining if a specific key exists within a SortedList, it can be useful to check if a value occurs within the collection. The ContainsValue operates in a similar manner to Contains and ContainsKey; the object to test for is passed as the only parameter. The resultant Boolean is true if the object exists and false if not.

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

Console.WriteLine(veg.ContainsValue("Savoy"));          // Outputs "True"
Console.WriteLine(veg.ContainsValue("Cos"));            // Outputs "False"

IndexOfKey

The IndexOfKey method improves upon the ContainsKey method. Rather than simply returning true or false to indicate if the specified items exists as a key, an integer value is returned. If the value is zero or greater, this is the index of the matching key entry. If the key is not found, the method returns -1.

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

Console.WriteLine(veg.IndexOfKey("potato"));            // Outputs "3"
Console.WriteLine(veg.IndexOfKey("parsnip"));           // Outputs "-1"

IndexOfValue

In addition to being able to locate a key, it is possible to find the index of a value within a SortedList. The IndexOfValue method returns the index number of a value matching the passed criteria. If the value is not found, the result is -1. If there are multiple occurrences of the value within the collection then the index of the first occurrence is returned.

SortedList veg = new SortedList();

veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

Console.WriteLine(veg.IndexOfValue("King Edward"));     // Outputs "3"
Console.WriteLine(veg.IndexOfValue("Cos"));             // Outputs "-1"

SortedList Capacity

As previously mentioned, when a SortedList is created, it has a predetermined size. The size may be specified directly in the constructor, indirectly due to the manner in which the SortedList is initialised or as the default size, which varies according to the version of the .NET framework that is in use.

As items are added to the SortedList and the capacity is exceeded, the capacity automatically doubles to allow the new additions. Each time this occurs, there is an overhead in allocation of new memory and copying of SortedList data. It is advisable, therefore, to set the capacity of an SortedList when the maximum size of the collection is known and when the number of entries that may be required is reasonably stable.

The capacity of an SortedList can be obtained and modified using the Capacity property. This property holds an integer value.

SortedList myCollection = new SortedList();

int capacity = myCollection.Capacity;
Console.WriteLine("Default capacity is {0} items", capacity);

myCollection.Capacity = 25;
capacity = myCollection.Capacity;
Console.WriteLine("New capacity is {0} items", capacity);

/* OUTPUT

Default capacity is 16 items
New capacity is 25 items

*/

Once a SortedList has been fully populated and no further items will be added, the memory allocated to the unused part of the dictionary can be reclaimed. The TrimToSize method sets the capacity of the collection to match the current contents.

SortedList myCollection = new SortedList();

myCollection.Add("One", 1);
myCollection.Add("Two", 2);
myCollection.Add("Three", 3);
myCollection.Add("Four", 4);
myCollection.Add("Five", 5);

int capacity = myCollection.Capacity;
Console.WriteLine("Initial capacity is {0} items", capacity);

myCollection.TrimToSize();
capacity = myCollection.Capacity;
Console.WriteLine("New capacity is {0} items", capacity);

/* OUTPUT

Initial capacity is 16 items
New capacity is 5 items

*/

Creating a Thread-Safe SortedList Wrapper

In the earlier article discussing collection interfaces, the concept of a thread-safe synchronised collection was described. In order to create a thread-safe SortedList, a synchronised wrapper dictionary is generated using the static Synchronized method.

SortedList myDictionary = new SortedList();

SortedList myThreadSafe = SortedList.Synchronized(myDictionary);

Console.WriteLine(myThreadSafe.IsSynchronized);	        // Outputs "True"