This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

.NET Framework
.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 a hybrid of the Hashtable and Array data structures. It is a dictionary that contains key / value pairs that 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.

You can think of the SortedList having two arrays to 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 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 as long as the key part is not null, is unique and supports the IComparable interface that permits items to be compared and sorted.

The SortedList provides additional functionality over the Hashtable because of its ability to be addressed by index number and due to its automatic sorting. It should be noted that this additional functionality gives reduced performance.

Implemented Collection Interfaces

The SortedList collection implements 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


The SortedList class provides six constructors for instantiating a new dictionary. The first is the most basic, requiring 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 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.

SortedList myList = new SortedList();

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

SortedList myList = new SortedList(25);

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

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

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.

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

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 populates a SortedList using the contents of any other collection that implements IDictionary. In the following example, the contents of a Hashtable are used to populate the new SortedList.

Hashtable myTable = new Hashtable();
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 comparer for ordering the items. To do so, pass the dictionary as the constructor's first parameter and the comparer as its second.

Hashtable myTable = new Hashtable();
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 supported by the SortedList class. As described above, keys 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","value2");                // Duplicate: ArgumentException
myList.Add(null,"value2");                  // Null Key: ArgumentNullException

Updating Using the Key

The SortedList can be modified directly using the key as an index. If you assign a value to a key that 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";
29 May 2007