Sorted Dictionaries
The Framework provides two dictionary classes internally structured such that their
content is always sorted by key:
• SortedDictionary<TKey,TValue>
• SortedList<TKey,TValue>*
(In this section, we will abbreviate <TKey,TValue> to <,>.)
SortedDictionary<,> uses a red/black tree: a data structure designed to perform
consistently well in any insertion or retrieval scenario.
SortedList<,> is implemented internally with an ordered array pair, providing fast
retrieval (via a binary-chop search) but poor insertion performance (because existing
values have to be shifted to make room for a new entry).
SortedDictionary<,> is much faster than SortedList<,> at inserting elements in a
random sequence (particularly with large lists). SortedList<,>, however, has an ex-
tra ability: to access items by index as well as by key. With a sorted list, you can go
directly to the nth element in the sorting sequence (via the indexer on the Keys/
Values properties). To do the same with a SortedDictionary<,>, you must manually
enumerate over n items. (Alternatively, you could write a class that combines a sorted
dictionary with a list class.)
None of the three collections allows duplicate keys (as is the case with all
dictionaries).
The following example uses reflection to load all the methods defined in
System.Object into a sorted list keyed by name, and then enumerates their keys
and values:
var sorted = new SortedList <string, MethodInfo>();
foreach (MethodInfo m in typeof (object).GetMethods())
sorted [m.Name] = m;
foreach (string name in sorted.Keys)
Console.WriteLine (name);
foreach (MethodInfo m in sorted.Values)
Console.WriteLine (m.Name + " returns a " + m.ReturnType);
Here’s the result of the first enumeration:
Equals
GetHashCode
GetType
ReferenceEquals
ToString
Here’s the result of the second enumeration:
Equals returns a System.Boolean
GetHashCode returns a System.Int32
GetType returns a System.Type
ReferenceEquals returns a System.Boolean
ToString returns a System.String
Notice that we populated the dictionary through its indexer. If we instead used the
Add method, it would throw an exception because the object class upon which we’re
reflecting overloads the Equals method, and you can’t add the same key twice to a
dictionary. By using the indexer, the later entry overwrites the earlier entry, pre-
venting this error.
You can store multiple members of the same key by making each
value element a list:
SortedList <string, List<MethodInfo>>
Extending our example, the following retrieves the MethodInfo whose key is "GetHash
Code", just as with an ordinary dictionary:
Console.WriteLine (sorted ["GetHashCode"]); // Int32 GetHashCode()
So far, everything we’ve done would also work with a SortedDictionary<,>. The
following two lines, however, which retrieve the last key and value, work only with
a sorted list:
Console.WriteLine (sorted.Keys [sorted.Count - 1]); // ToString
Console.WriteLine (sorted.Values[sorted.Count - 1].IsVirtual); // True
Monday, 17 December 2012
c# for dummies: c sharp programming
c# for dummies: c sharp programming: OrderedDictionary An OrderedDictionary is a nongeneric dictionary that maintains elements in the same order that they were added. With an Or...
c sharp programming
OrderedDictionary
An OrderedDictionary is a nongeneric dictionary that maintains elements in the same
order that they were added. With an OrderedDictionary, you can access elements
both by index and by key.
An OrderedDictionary is not a sorted dictionary.
An OrderedDictionary is a combination of a Hashtable and an ArrayList. This means
it has all the functionality of a Hashtable, plus functions such as RemoveAt, as well as
an integer indexer. It also exposes Keys and Values properties that return elements
in their original order.
This class was introduced in .NET 2.0, yet peculiarly, there’s no generic version.
ListDictionary and HybridDictionary
ListDictionary uses a singly linked list to store the underlying data. It doesn’t pro-
vide sorting, although it does preserve the original entry order of the items.
ListDictionary is extremely slow with large lists. Its only real “claim to fame” is its
efficiency with very small lists (fewer than 10 items).
HybridDictionary is a ListDictionary that automatically converts to a Hashtable
upon reaching a certain size, to address ListDictionary’s problems with perform-
ance. The idea is to get a low memory footprint when the dictionary is small, and
good performance when the dictionary is large. However, given the overhead in
converting from one to the other—and the fact that a Dictionary is not excessively
heavy or slow in either scenario—you wouldn’t suffer unreasonably by using a
Dictionary to begin with.
Both classes come only in nongeneric form.
An OrderedDictionary is a nongeneric dictionary that maintains elements in the same
order that they were added. With an OrderedDictionary, you can access elements
both by index and by key.
An OrderedDictionary is not a sorted dictionary.
An OrderedDictionary is a combination of a Hashtable and an ArrayList. This means
it has all the functionality of a Hashtable, plus functions such as RemoveAt, as well as
an integer indexer. It also exposes Keys and Values properties that return elements
in their original order.
This class was introduced in .NET 2.0, yet peculiarly, there’s no generic version.
ListDictionary and HybridDictionary
ListDictionary uses a singly linked list to store the underlying data. It doesn’t pro-
vide sorting, although it does preserve the original entry order of the items.
ListDictionary is extremely slow with large lists. Its only real “claim to fame” is its
efficiency with very small lists (fewer than 10 items).
HybridDictionary is a ListDictionary that automatically converts to a Hashtable
upon reaching a certain size, to address ListDictionary’s problems with perform-
ance. The idea is to get a low memory footprint when the dictionary is small, and
good performance when the dictionary is large. However, given the overhead in
converting from one to the other—and the fact that a Dictionary is not excessively
heavy or slow in either scenario—you wouldn’t suffer unreasonably by using a
Dictionary to begin with.
Both classes come only in nongeneric form.
c# for dummies: c sharp programming
c# for dummies: c sharp programming: IDictionary The nongeneric IDictionary interface is the same in principle as IDictionary, apart from two important...
c sharp programming
IDictionary
The nongeneric IDictionary interface is the same in principle as
IDictionary<TKey,TValue>, apart from two important functional differences.
It’s important to be aware of these differences, because IDictionary appears in
legacy code (including the .NET Framework itself in places):
• Retrieving a nonexistent key via the indexer returns null (rather than throwing
an exception).
• Contains tests for membership rather than ContainsKey.
Enumerating over a nongeneric IDictionary returns a sequence of DictionaryEn
try structs:
public struct DictionaryEntry
{
public object Key { get; set; }
public object Value { get; set; }
}
Dictionary<TKey,TValue> and Hashtable
The generic Dictionary class is one of the most commonly used collections (along
with the List<T> collection). It uses a hashtable data structure to store keys and
values, and it is fast and efficient.
The nongeneric version of Dictionary<TKey,TValue> is
called Hashtable; there is no nongeneric class called Diction
ary. When we refer simply to Dictionary, we mean the generic
Dictionary<TKey,TValue> class.
Dictionary implements both the generic and nongeneric IDictionary interfaces, the
generic IDictionary being exposed publicly. Dictionary is, in fact, a “textbook” im-
plementation of the generic IDictionary.
Here’s how to use it:
var d = new Dictionary<string, int>();
d.Add("One", 1);
d["Two"] = 2; // adds to dictionary because "two" not already present
d["Two"] = 22; // updates dictionary because "two" is now present
d["Three"] = 3;
Console.WriteLine (d["Two"]); // Prints "22"
Console.WriteLine (d.ContainsKey ("One")); // true (fast operation)
Console.WriteLine (d.ContainsValue (3)); // true (slow operation)
int val = 0;
if (!d.TryGetValue ("onE", out val))
Console.WriteLine ("No val"); // "No val" (case sensitive)
// Three different ways to enumerate the dictionary:
foreach (KeyValuePair<string, int> kv in d) // One ; 1
Console.WriteLine (kv.Key + "; " + kv.Value); // Two ; 22
// Three ; 3
foreach (string s in d.Keys) Console.Write (s); // OneTwoThree
Console.WriteLine();
foreach (int i in d.Values) Console.Write (i); // 1223
Its underlying hashtable works by converting each element’s key into an integer hash
code—a pseudounique value—and then applying an algorithm to convert the hash
code into a hash key. This hash key is used internally to determine which “bucket”
an entry belongs to. If the bucket contains more than one value, a linear search is
performed on the bucket. A hashtable typically starts out maintaining a 1:1 ratio of
buckets to values (a 1:1 load factor), meaning that each bucket contains only one
value. However, as more items are added to the hashtable, the load factor dynami-
cally increases, in a manner designed to optimize insertion and retrieval performance
as well as memory requirements.
A dictionary can work with keys of any type, providing it’s able to determine equality
between keys and obtain hash codes. By default, equality is determined via the key’s
object.Equals method, and the pseudounique hash code is obtained via the key’s
GetHashCode method. This behavior can be changed, either by overriding these
methods or by providing an IEqualityComparer object when constructing the dic-
tionary. A common application of this is to specify a case-insensitive equality com-
parer when using string keys:
var d = new Dictionary<string, int> (StringComparer.OrdinalIgnoreCase);
The nongeneric IDictionary interface is the same in principle as
IDictionary<TKey,TValue>, apart from two important functional differences.
It’s important to be aware of these differences, because IDictionary appears in
legacy code (including the .NET Framework itself in places):
• Retrieving a nonexistent key via the indexer returns null (rather than throwing
an exception).
• Contains tests for membership rather than ContainsKey.
Enumerating over a nongeneric IDictionary returns a sequence of DictionaryEn
try structs:
public struct DictionaryEntry
{
public object Key { get; set; }
public object Value { get; set; }
}
Dictionary<TKey,TValue> and Hashtable
The generic Dictionary class is one of the most commonly used collections (along
with the List<T> collection). It uses a hashtable data structure to store keys and
values, and it is fast and efficient.
The nongeneric version of Dictionary<TKey,TValue> is
called Hashtable; there is no nongeneric class called Diction
ary. When we refer simply to Dictionary, we mean the generic
Dictionary<TKey,TValue> class.
Dictionary implements both the generic and nongeneric IDictionary interfaces, the
generic IDictionary being exposed publicly. Dictionary is, in fact, a “textbook” im-
plementation of the generic IDictionary.
Here’s how to use it:
var d = new Dictionary<string, int>();
d.Add("One", 1);
d["Two"] = 2; // adds to dictionary because "two" not already present
d["Two"] = 22; // updates dictionary because "two" is now present
d["Three"] = 3;
Console.WriteLine (d["Two"]); // Prints "22"
Console.WriteLine (d.ContainsKey ("One")); // true (fast operation)
Console.WriteLine (d.ContainsValue (3)); // true (slow operation)
int val = 0;
if (!d.TryGetValue ("onE", out val))
Console.WriteLine ("No val"); // "No val" (case sensitive)
// Three different ways to enumerate the dictionary:
foreach (KeyValuePair<string, int> kv in d) // One ; 1
Console.WriteLine (kv.Key + "; " + kv.Value); // Two ; 22
// Three ; 3
foreach (string s in d.Keys) Console.Write (s); // OneTwoThree
Console.WriteLine();
foreach (int i in d.Values) Console.Write (i); // 1223
Its underlying hashtable works by converting each element’s key into an integer hash
code—a pseudounique value—and then applying an algorithm to convert the hash
code into a hash key. This hash key is used internally to determine which “bucket”
an entry belongs to. If the bucket contains more than one value, a linear search is
performed on the bucket. A hashtable typically starts out maintaining a 1:1 ratio of
buckets to values (a 1:1 load factor), meaning that each bucket contains only one
value. However, as more items are added to the hashtable, the load factor dynami-
cally increases, in a manner designed to optimize insertion and retrieval performance
as well as memory requirements.
A dictionary can work with keys of any type, providing it’s able to determine equality
between keys and obtain hash codes. By default, equality is determined via the key’s
object.Equals method, and the pseudounique hash code is obtained via the key’s
GetHashCode method. This behavior can be changed, either by overriding these
methods or by providing an IEqualityComparer object when constructing the dic-
tionary. A common application of this is to specify a case-insensitive equality com-
parer when using string keys:
var d = new Dictionary<string, int> (StringComparer.OrdinalIgnoreCase);
c# for dummies: c sharp programming
c# for dummies: c sharp programming: The DictionaryEntry Structure System.Collections defines one structure type called DictionaryEntry. Non-generic collections that hold key/...
c sharp programming
The DictionaryEntry Structure
System.Collections defines one structure type called DictionaryEntry. Non-generic
collections that hold key/value pairs store those pairs in a DictionaryEntry object. This
structure defines the following two properties:
public object Key { get; set; }
public object Value { get; set; }
These properties are used to access the key or value associated with an entry. You can
construct a DictionaryEntry object by using the following constructor:
public DictionaryEntry(object k, object v)
Here, k is the key and v is the value.
A dictionary is a collection in which each element is a key/value pair. Dictionaries
are most commonly used for lookups and sorted lists.
The Framework defines a standard protocol for dictionaries, via the interfaces
IDictionary and IDictionary <TKey, TValue>, as well as a set of general-purpose
dictionary classes. The classes each differ in the following regard:
• Whether or not items are stored in sorted sequence
• Whether or not items can be accessed by position (index) as well as by key
• Whether generic or nongeneric
• Their performance when large
IDictionary<TKey,TValue>
IDictionary<TKey,TValue> defines the standard protocol for all key/value-based col-
lections. It extends ICollection<T> by adding methods and properties to access el-
ements based on a key of arbitrary type:
public interface IDictionary <TKey, TValue> :
ICollection <KeyValuePair <TKey, TValue>>, IEnumerable
{
bool ContainsKey (TKey key);
bool TryGetValue (TKey key, out TValue value);
void Add (TKey key, TValue value);
bool Remove (TKey key);
TValue this [TKey key] { get; set; } // Main indexer - by key
ICollection <TKey> Keys { get; } // Returns just keys
ICollection <TValue> Values { get; } // Returns just values
}
To add an item to a dictionary, you either call Add or use the index’s set accessor—
the latter adds an item to the dictionary if the key is not already present (or updates
the item if it is present). Duplicate keys are forbidden in all dictionary implementa-
tions, so calling Add twice with the same key throws an exception.
To retrieve an item from a dictionary, use either the indexer or the TryGetValue
method. If the key doesn’t exist, the indexer throws an exception whereas TryGet
Value returns false. You can test for membership explicitly by calling ContainsKey;
however, this incurs the cost of two lookups if you then subsequently retrieve the
item.
Enumerating directly over an IDictionary<TKey,TValue> returns a sequence of
KeyValuePair structs:
public struct KeyValuePair <TKey, TValue>
{
public TKey Key { get; }
public TValue Value { get; }
}
You can enumerate over just the keys or values via the dictionary’s Keys/Values
properties.
We demonstrate the use of this interface with the generic Dictionary class in the
following section.
System.Collections defines one structure type called DictionaryEntry. Non-generic
collections that hold key/value pairs store those pairs in a DictionaryEntry object. This
structure defines the following two properties:
public object Key { get; set; }
public object Value { get; set; }
These properties are used to access the key or value associated with an entry. You can
construct a DictionaryEntry object by using the following constructor:
public DictionaryEntry(object k, object v)
Here, k is the key and v is the value.
A dictionary is a collection in which each element is a key/value pair. Dictionaries
are most commonly used for lookups and sorted lists.
The Framework defines a standard protocol for dictionaries, via the interfaces
IDictionary and IDictionary <TKey, TValue>, as well as a set of general-purpose
dictionary classes. The classes each differ in the following regard:
• Whether or not items are stored in sorted sequence
• Whether or not items can be accessed by position (index) as well as by key
• Whether generic or nongeneric
• Their performance when large
IDictionary<TKey,TValue>
IDictionary<TKey,TValue> defines the standard protocol for all key/value-based col-
lections. It extends ICollection<T> by adding methods and properties to access el-
ements based on a key of arbitrary type:
public interface IDictionary <TKey, TValue> :
ICollection <KeyValuePair <TKey, TValue>>, IEnumerable
{
bool ContainsKey (TKey key);
bool TryGetValue (TKey key, out TValue value);
void Add (TKey key, TValue value);
bool Remove (TKey key);
TValue this [TKey key] { get; set; } // Main indexer - by key
ICollection <TKey> Keys { get; } // Returns just keys
ICollection <TValue> Values { get; } // Returns just values
}
To add an item to a dictionary, you either call Add or use the index’s set accessor—
the latter adds an item to the dictionary if the key is not already present (or updates
the item if it is present). Duplicate keys are forbidden in all dictionary implementa-
tions, so calling Add twice with the same key throws an exception.
To retrieve an item from a dictionary, use either the indexer or the TryGetValue
method. If the key doesn’t exist, the indexer throws an exception whereas TryGet
Value returns false. You can test for membership explicitly by calling ContainsKey;
however, this incurs the cost of two lookups if you then subsequently retrieve the
item.
Enumerating directly over an IDictionary<TKey,TValue> returns a sequence of
KeyValuePair structs:
public struct KeyValuePair <TKey, TValue>
{
public TKey Key { get; }
public TValue Value { get; }
}
You can enumerate over just the keys or values via the dictionary’s Keys/Values
properties.
We demonstrate the use of this interface with the generic Dictionary class in the
following section.
Subscribe to:
Posts (Atom)