SortedList Generic Class (System.Collections.Generic)

Collapse All

Language Filter

This page is specific to

Microsoft Visual Studio 2005/.NET Framework 2.0

Other versions are also available for the following:

SortedList Generic Class

Represents a collection of key/value pairs that are sorted by key based on the associated IComparer implementation.

Namespace: System.Collections.Generic
Assembly: System (in system.dll)

Syntax

Visual Basic (Declaration)

<SerializableAttribute> _
<ComVisibleAttribute(False)> _
Public Class SortedList(Of TKey, TValue)
    Implements IDictionary(Of TKey, TValue), ICollection(Of KeyValuePair(Of TKey, TValue)), _
    IEnumerable(Of KeyValuePair(Of TKey, TValue)), IDictionary, ICollection, _
    IEnumerable

Visual Basic (Usage)

Dim instance As SortedList(Of TKey, TValue)

[SerializableAttribute] 
[ComVisibleAttribute(false)] 
public class SortedList<TKey,TValue> : IDictionary<TKey,TValue>, ICollection<KeyValuePair<TKey,TValue>>, 
    IEnumerable<KeyValuePair<TKey,TValue>>, IDictionary, ICollection, IEnumerable

C++

[SerializableAttribute] 
[ComVisibleAttribute(false)] 
generic<typename TKey, typename TValue>
public ref class SortedList : IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, 
    IEnumerable<KeyValuePair<TKey, TValue>>, IDictionary, ICollection, IEnumerable

J# supports the use of generic types and methods, but not the declaration of new ones.

JScript

JScript does not support generic types and methods.

XAML

Not applicable.

Type Parameters

: TKey
The type of keys in the collection.

: TValue
The type of values in the collection.

Remarks

The SortedList 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 SortedDictionary 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 uses less memory than SortedDictionary.
SortedDictionary has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList.
If the list is populated all at once from sorted data, SortedList is faster than SortedDictionary.

Another difference between the SortedDictionary and SortedList classes is that SortedList supports efficient indexed retrieval of keys and values through the collections returned by the Keys and Values properties. It is not necessary to regenerate the lists when the properties are accessed, because the lists are just wrappers for the internal arrays of keys and values. The following code shows the use of the Values property for indexed retrieval of values from a sorted list of strings:

Visual Basic

Dim v As String = mySortedList.Values(3)

string v = mySortedList.Values[3];

C++

String^ v = mySortedList->Values[3];

SortedList is implemented as an array of key/value pairs, sorted by the key. Each element can be retrieved as a KeyValuePair object.

Key objects must be immutable as long as they are used as keys in the SortedList. Every key in a SortedList must be unique. A key cannot be a null reference (Nothing in Visual Basic), but a value can be, if the type of values in the list, TValue, is a reference type.

SortedList requires a comparer implementation to sort and to perform comparisons. The default comparer Comparer.Default checks whether the key type TKey implements System.IComparable and uses that implementation, if available. If not, Comparer.Default checks whether the key type TKey implements System.IComparable. If the key type TKey does not implement either interface, you can specify a System.Collections.Generic.IComparer implementation in a constructor overload that accepts a comparer parameter.

The capacity of a SortedList is the number of elements the SortedList can hold. As elements are added to a SortedList, the capacity is automatically increased as required by reallocating the internal array. The capacity can be decreased by calling TrimExcess or by setting the Capacity property explicitly. Decreasing the capacity reallocates memory and copies all the elements in the SortedList.

The foreach statement of the C# language (for each in C++, For Each in Visual Basic) requires the type of the elements in the collection. Since the elements of the SortedList are key/value pairs, the element type is not the type of the key or the type of the value. Instead, the element type is KeyValuePair. For example:

foreach (KeyValuePair<int, string> kvp in mySortedList) {...}

C++

for each (KeyValuePair<int, String^> kvp in mySortedList) {...}

Visual Basic

For Each kvp As KeyValuePair(Of Integer, String) In mySortedList
    ...
Next kvp

The foreach statement is a wrapper around the enumerator, which only allows reading from, not writing to, the collection.

Example

The following code example creates an empty SortedList of strings with string keys and uses the Add method to add some elements. The example demonstrates that the Add method throws an ArgumentException when attempting to add a duplicate key.

The example uses the Item property (the indexer in C#) to retrieve values, demonstrating that a KeyNotFoundException is thrown when a requested key is not present, and showing that the value associated with a key can be replaced.

The example shows how to use the TryGetValue method as a more efficient way to retrieve values if a program often must try key values that are not in the sorted list, and it shows how to use the ContainsKey method to test whether a key exists before calling the Add method.

The example shows how to enumerate the keys and values in the sorted list and how to enumerate the keys and values alone using the Keys property and the Values property.

Finally, the example demonstrates the Remove method.

Visual Basic

Imports System
Imports System.Collections.Generic

Public Class Example
    
    Public Shared Sub Main() 

        ' Create a new sorted list of strings, with string 
        ' keys. 
        Dim openWith As New SortedList(Of String, String)
        
        ' Add some elements to the list. There are no 
        ' duplicate keys, but some of the values are duplicates.
        openWith.Add("txt", "notepad.exe")
        openWith.Add("bmp", "paint.exe")
        openWith.Add("dib", "paint.exe")
        openWith.Add("rtf", "wordpad.exe")
        
        ' The Add method throws an exception if the new key is 
        ' already in the list.
        Try
            openWith.Add("txt", "winword.exe")
        Catch 
            Console.WriteLine("An element with Key = ""txt"" already exists.")
        End Try

        ' The Item property is the default property, so you 
        ' can omit its name when accessing elements. 
        Console.WriteLine("For key = ""rtf"", value = {0}.", _
            openWith("rtf"))
        
        ' The default Item property can be used to change the value
        ' associated with a key.
        openWith("rtf") = "winword.exe"
        Console.WriteLine("For key = ""rtf"", value = {0}.", _
            openWith("rtf"))
        
        ' If a key does not exist, setting the default Item property
        ' for that key adds a new key/value pair.
        openWith("doc") = "winword.exe"

        ' The default Item property throws an exception if the requested
        ' key is not in the list.
        Try
            Console.WriteLine("For key = ""tif"", value = {0}.", _
                openWith("tif"))
        Catch 
            Console.WriteLine("Key = ""tif"" is not found.")
        End Try

        ' When a program often has to try keys that turn out not to
        ' be in the list, TryGetValue can be a more efficient 
        ' way to retrieve values.
        Dim value As String = ""
        If openWith.TryGetValue("tif", value) Then
            Console.WriteLine("For key = ""tif"", value = {0}.", value)
        Else
            Console.WriteLine("Key = ""tif"" is not found.")
        End If

        ' ContainsKey can be used to test keys before inserting 
        ' them.
        If Not openWith.ContainsKey("ht") Then
            openWith.Add("ht", "hypertrm.exe")
            Console.WriteLine("Value added for key = ""ht"": {0}", _
                openWith("ht"))
        End If

        ' When you use foreach to enumerate list elements,
        ' the elements are retrieved as KeyValuePair objects.
        Console.WriteLine()
        For Each kvp As KeyValuePair(Of String, String) In openWith
            Console.WriteLine("Key = {0}, Value = {1}", _
                kvp.Key, kvp.Value)
        Next kvp

        ' To get the values alone, use the Values property.
        Dim ilistValues As IList(Of String) = openWith.Values
        
        ' The elements of the list are strongly typed with the
        ' type that was specified for the SortedList values.
        Console.WriteLine()
        For Each s As String In ilistValues
            Console.WriteLine("Value = {0}", s)
        Next s

        ' The Values property is an efficient way to retrieve
        ' values by index.
        Console.WriteLine(vbLf & "Indexed retrieval using the " & _
            "Values property: Values(2) = {0}", openWith.Values(2))

        ' To get the keys alone, use the Keys property.
        Dim ilistKeys As IList(Of String) = openWith.Keys
        
        ' The elements of the list are strongly typed with the
        ' type that was specified for the SortedList keys.
        Console.WriteLine()
        For Each s As String In ilistKeys 
            Console.WriteLine("Key = {0}", s)
        Next s

        ' The Keys property is an efficient way to retrieve
        ' keys by index.
        Console.WriteLine(vbLf & "Indexed retrieval using the " & _
            "Keys property: Keys(2) = {0}", openWith.Keys(2))

        ' Use the Remove method to remove a key/value pair.
        Console.WriteLine(vbLf + "Remove(""doc"")")
        openWith.Remove("doc")
        
        If Not openWith.ContainsKey("doc") Then
            Console.WriteLine("Key ""doc"" is not found.")
        End If

    End Sub

End Class

' This code example produces the following output:
'
'An element with Key = "txt" already exists.
'For key = "rtf", value = wordpad.exe.
'For key = "rtf", value = winword.exe.
'Key = "tif" is not found.
'Key = "tif" is not found.
'Value added for key = "ht": hypertrm.exe
'
'Key = bmp, Value = paint.exe
'Key = dib, Value = paint.exe
'Key = doc, Value = winword.exe
'Key = ht, Value = hypertrm.exe
'Key = rtf, Value = winword.exe
'Key = txt, Value = notepad.exe
'
'Value = paint.exe
'Value = paint.exe
'Value = winword.exe
'Value = hypertrm.exe
'Value = winword.exe
'Value = notepad.exe
'
'Indexed retrieval using the Values property: Values(2) = winword.exe
'
'Key = bmp
'Key = dib
'Key = doc
'Key = ht
'Key = rtf
'Key = txt
'
'Indexed retrieval using the Keys property: Keys(2) = doc
'
'Remove("doc")
'Key "doc" is not found.
'

using System;
using System.Collections.Generic;

public class Example
{
    public static void Main()
    {
        // Create a new sorted list of strings, with string
        // keys.
        SortedList<string, string> openWith = 
            new SortedList<string, string>();

        // Add some elements to the list. There are no 
        // duplicate keys, but some of the values are duplicates.
        openWith.Add("txt", "notepad.exe");
        openWith.Add("bmp", "paint.exe");
        openWith.Add("dib", "paint.exe");
        openWith.Add("rtf", "wordpad.exe");

        // The Add method throws an exception if the new key is 
        // already in the list.
        try
        {
            openWith.Add("txt", "winword.exe");
        }
        catch (ArgumentException)
        {
            Console.WriteLine("An element with Key = \"txt\" already exists.");
        }

        // The Item property is another name for the indexer, so you 
        // can omit its name when accessing elements. 
        Console.WriteLine("For key = \"rtf\", value = {0}.", 
            openWith["rtf"]);

        // The indexer can be used to change the value associated
        // with a key.
        openWith["rtf"] = "winword.exe";
        Console.WriteLine("For key = \"rtf\", value = {0}.", 
            openWith["rtf"]);

        // If a key does not exist, setting the indexer for that key
        // adds a new key/value pair.
        openWith["doc"] = "winword.exe";

        // The indexer throws an exception if the requested key is
        // not in the list.
        try
        {
            Console.WriteLine("For key = \"tif\", value = {0}.", 
                openWith["tif"]);
        }
        catch (KeyNotFoundException)
        {
            Console.WriteLine("Key = \"tif\" is not found.");
        }

        // When a program often has to try keys that turn out not to
        // be in the list, TryGetValue can be a more efficient 
        // way to retrieve values.
        string value = "";
        if (openWith.TryGetValue("tif", out value))
        {
            Console.WriteLine("For key = \"tif\", value = {0}.", value);
        }
        else
        {
            Console.WriteLine("Key = \"tif\" is not found.");
        }

        // ContainsKey can be used to test keys before inserting 
        // them.
        if (!openWith.ContainsKey("ht"))
        {
            openWith.Add("ht", "hypertrm.exe");
            Console.WriteLine("Value added for key = \"ht\": {0}", 
                openWith["ht"]);
        }

        // When you use foreach to enumerate list elements,
        // the elements are retrieved as KeyValuePair objects.
        Console.WriteLine();
        foreach( KeyValuePair<string, string> kvp in openWith )
        {
            Console.WriteLine("Key = {0}, Value = {1}", 
                kvp.Key, kvp.Value);
        }

        // To get the values alone, use the Values property.
        IList<string> ilistValues = openWith.Values;

        // The elements of the list are strongly typed with the 
        // type that was specified for the SorteList values.
        Console.WriteLine();
        foreach( string s in ilistValues )
        {
            Console.WriteLine("Value = {0}", s);
        }

        // The Values property is an efficient way to retrieve
        // values by index.
        Console.WriteLine("\nIndexed retrieval using the Values " +
            "property: Values[2] = {0}", openWith.Values[2]);

        // To get the keys alone, use the Keys property.
        IList<string> ilistKeys = openWith.Keys;

        // The elements of the list are strongly typed with the 
        // type that was specified for the SortedList keys.
        Console.WriteLine();
        foreach( string s in ilistKeys )
        {
            Console.WriteLine("Key = {0}", s);
        }

        // The Keys property is an efficient way to retrieve
        // keys by index.
        Console.WriteLine("\nIndexed retrieval using the Keys " +
            "property: Keys[2] = {0}", openWith.Keys[2]);

        // Use the Remove method to remove a key/value pair.
        Console.WriteLine("\nRemove(\"doc\")");
        openWith.Remove("doc");

        if (!openWith.ContainsKey("doc"))
        {
            Console.WriteLine("Key \"doc\" is not found.");
        }
    }
}

/* This code example produces the following output:

An element with Key = "txt" already exists.
For key = "rtf", value = wordpad.exe.
For key = "rtf", value = winword.exe.
Key = "tif" is not found.
Key = "tif" is not found.
Value added for key = "ht": hypertrm.exe

Key = bmp, Value = paint.exe
Key = dib, Value = paint.exe
Key = doc, Value = winword.exe
Key = ht, Value = hypertrm.exe
Key = rtf, Value = winword.exe
Key = txt, Value = notepad.exe

Value = paint.exe
Value = paint.exe
Value = winword.exe
Value = hypertrm.exe
Value = winword.exe
Value = notepad.exe

Indexed retrieval using the Values property: Values[2] = winword.exe

Key = bmp
Key = dib
Key = doc
Key = ht
Key = rtf
Key = txt

Indexed retrieval using the Keys property: Keys[2] = doc

Remove("doc")
Key "doc" is not found.
 */

Inheritance Hierarchy

System.Object
System.Collections.Generic.SortedList

Thread Safety

Public static (Shared in Visual Basic) members of this type are thread safe. Any instance members are not guaranteed to be thread safe.

A SortedList can support multiple readers concurrently, as long as the collection is not modified. Even so, enumerating through a collection is intrinsically not a thread-safe procedure. To guarantee thread safety during enumeration, you can lock the collection during the entire enumeration. To allow the collection to be accessed by multiple threads for reading and writing, you must implement your own synchronization.

Platforms

Windows 98, Windows Server 2000 SP4, Windows Millennium Edition, Windows Server 2003, Windows XP Media Center Edition, Windows XP Professional x64 Edition, Windows XP SP2, Windows XP Starter Edition

The Microsoft .NET Framework 3.0 is supported on Windows Vista, Microsoft Windows XP SP2, and Windows Server 2003 SP1.

Version Information

.NET Framework

Supported in: 3.0, 2.0

.NET Compact Framework

Supported in: 2.0

XNA Framework

Supported in: 1.0

Reference

SortedList Members
System.Collections.Generic Namespace
IDictionary Generic Interface
Dictionary Generic Class
SortedDictionary Generic Class
KeyValuePair Generic Structure
IComparer Generic Interface