| only for RuBoard - do not distribute or recompile | |
Collections are standard data structures that supplement arrays, the only built-in data structures in C#. This differs from languages such as Perl and Python, which incorporate key-value data structures and dynamically sized arrays into the language itself.
The FCL includes a set of types that provide commonly required data structures and support for creating your own. These types are typically broken down into two categories: interfaces that define a standardized set of design patterns for collection classes in general, and concrete classes that implement these interfaces and provide a usable range of data structures.
This section introduces all the concrete collection classes and abstract collection interfaces and provides examples of their use. Unless otherwise stated, the types mentioned in this section all exist in the System.Collections namespace.
The FCL includes the concrete implementations of the collection design patterns that are described in this section.
Unlike C++, C# doesn't yet support templates, so these implementations work generically by accepting elements of type System.Object.
ArrayList is a dynamically sized array of objects that implements the IList interface (see Section 3.4.2.5 later in this chapter). An ArrayList works by maintaining an internal array of objects that is replaced with a larger array when it reaches its capacity of elements. It is very efficient at adding elements (since there is usually a free slot at the end) but is inefficient at inserting elements (since all elements have to be shifted to make a free slot). Searching can be efficient if the BinarySearch method is used, but you must Sort( ) the ArrayList first. You could use the Contains( ) method, but it performs a linear search in O(n) time.
ArrayList a = new ArrayList( );
a.Add("Vernon");
a.Add("Corey");
a.Add("William");
a.Add("Muzz");
a.Sort( );
for(int i = 0; i < a.Count; i++)
Console.WriteLine(a [i]);
A BitArray is a dynamically sized array of Boolean values. It is more memory-efficient than a simple array of bools because it uses only one bit for each value, whereas a bool array uses two bytes for each value. Here is an example of its use:
BitArray bits = new BitArray( 0 ); // initialize a zero-length bit array bits.Length = 2; bits[1] = true; bits.Xor(bits); // Xor the array with itself
A Hashtable is a standard dictionary (key/value) data structure that uses a hashing algorithm to store and index values efficiently. This hashing algorithm is performed using the hashcode returned by the GetHashCode method on System.Object. Types used as keys in a Hashtable should therefore override GetHashCode to return a good hash of the object's internal value.
Hashtable ht = new Hashtable( ); ht["One"] = 1; ht["Two"] = 2; ht["Three"] = 3; Console.WriteLine(ht["Two"]); // Prints "2"
Hashtable also implements IDictionary (see Section 3.4.2.6 later in this chapter), and therefore, can be manipulated as a normal dictionary data structure.
A Queue is a standard first-in, first-out (FIFO) data structure, providing simple operations to enqueue, dequeue, peek, etc. Here is an example:
Queue q = new Queue( ); q.Enqueue(1); q.Enqueue(2); Console.WriteLine(q.Dequeue( )); // Prints "1" Console.WriteLine(q.Dequeue( )); // Prints "2"
A SortedList is a standard dictionary data structure that uses a binary-chop search to index efficiently. SortedList implements IDictionary (see the later section Section 3.4.2.6):
SortedList s = new SortedList( ); s["Zebra"] = 1; s["Antelope"] = 2; s["Eland"] = 3; s["Giraffe"] = 4; s["Meerkat"] = 5; s["Dassie"] = 6; s["Tokoloshe"] = 7; Console.WriteLine(s["Meerkat"]); // Prints "5" in 3 lookups
A Stack is a standard last-in first-out (LIFO) data structure:
Stack s = new Stack( ); s.Push(1); // Stack = 1 s.Push(2); // Stack = 1,2 s.Push(3); // Stack = 1,2,3 Console.WriteLine(s.Pop( )); // Prints 3, Stack=1,2 Console.WriteLine(s.Pop( )); // Prints 2, Stack=1 Console.WriteLine(s.Pop( )); // Prints 1, Stack=
A StringCollection is a standard collection data structure for storing strings. StringCollection lives in the System.Collections.Specialized namespace and implements ICollection. It can be manipulated like a normal collection (see the later section Section 3.4.2.3):
StringCollection sc = new StringCollection( );
sc.Add("s1");
string[] sarr = {"s2", "s3", "s4"};
sc.AddRange(sarr);
foreach (string s in sc)
Console.Write("{0} ", s); // s1 s2 s3 s4
The collection interfaces provide standard ways to enumerate, populate, and author collections. The FCL defines the interfaces in this section to support the standard collection design patterns.
public interface IEnumerable {
IEnumerator GetEnumerator( );
}
The C# foreach statement works on any collection that implements the IEnumerable interface. The IEnumerable interface has a single method that returns an IEnumerator object.
public interface IEnumerator {
bool MoveNext( );
object Current {get;}
void Reset( );
}
The IEnumerator interface provides a standard way to iterate over collections. Internally, an IEnumerator maintains the current position of an item in the collection. If the items are numbered (inclusive) to n (exclusive), the current position starts off as -1, and finishes at n.
IEnumerator is typically implemented as a nested type and is initialized by passing the collection to the constructor of the IEnumerator:
using System;
using System.Collections;
public class MyCollection : IEnumerable {
// Contents of this collection.
private string[] items = {"hello", "world"};
// Accessors for this collection.
public string this[int index] {
get { return items[index]; }
}
public int Count {
get { return items.Length; }
}
// Implement IEnumerable.
public virtual IEnumerator GetEnumerator ( ) {
return new MyCollection.Enumerator(this);
}
// Define a custom enumerator.
private class Enumerator : IEnumerator {
private MyCollection collection;
private int currentIndex = -1;
internal Enumerator (MyCollection collection) {
this.collection = collection;
}
public object Current {
get {
if (currentIndex==-1 || currentIndex == collection.Count)
throw new InvalidOperationException( );
return collection [currentIndex];
}
}
public bool MoveNext ( ) {
if (currentIndex > collection.Count)
throw new InvalidOperationException( );
return ++currentIndex < collection.Count;
}
public void Reset ( ) {
currentIndex = -1;
}
}
}
The collection can then be enumerated in either of these two ways:
MyCollection mcoll = new MyCollection( );
// Using foreach: substitute your typename for
string
foreach (
string item in mcoll) {
Console.WriteLine(item);
}
// Using IEnumerator: substitute your typename for
string
IEnumerator ie = mcoll.GetEnumerator( );
while (ie.MoveNext( )) {
string item = (
string) ie.Current;
Console.WriteLine(item);
}
public interface ICollection : IEnumerable {
void CopyTo(Array
array, int
index);
int Count {get;}
bool IsSynchronized {get;}
object SyncRoot {get;}
}
ICollection is the interface implemented by all collections, including arrays, and provides the following methods:
This method copies all the elements into the array starting at the specified index in the source collection.
This property returns the number of elements in the collection.
This method allows you to determine whether or not a collection is thread-safe. The collections provided in the FCL are not themselves thread-safe, but each one includes a Synchronized method that returns a thread-safe wrapper of the collection.
This property returns an object (usually the collection itself) that can be locked to provide basic thread-safe support for the collection.
IComparer is a standard interface that compares two objects for sorting in Arrays. You generally don't need to implement this interface, since a default implementation that uses the IComparable interface is already provided by the Comparer type, which is used by the Array type.
public interface IComparer {
int Compare(object x, object y);
}
IList is an interface for array-indexable collections, such as ArrayList.
public interface IList : ICollection, IEnumerable {
object this [int index] {get; set}
bool IsFixedSize { get; }
bool IsReadOnly { get; }
int Add(object o);
void Clear( );
bool Contains(object value);
int IndexOf(object value);
void Insert(int index, object value);
void Remove(object value);
void RemoveAt(int index);
}
IDictionary is an interface for key/value-based collections, such as Hashtable and SortedList.
public interface IDictionary : ICollection, IEnumerable {
object this [object key] {get; set};
bool IsFixedSize { get; }
bool IsReadOnly { get; }
ICollection Keys {get;}
ICollection Values {get;}
void Clear( );
bool Contains(object key);
IDictionaryEnumerator GetEnumerator( );
void Remove(object key);
}
IDictionaryEnumerator is a standardized interface that enumerates over the contents of a dictionary.
public interface IDictionaryEnumerator : IEnumerator {
DictionaryEntry Entry {get;}
object Key {get;}
object Value {get;}
}
IHashCodeProvider is a standard interface used by the Hashtable collection to hash its objects for storage.
public interface IHashCodeProvider {
int GetHashCode(object o);
}
| only for RuBoard - do not distribute or recompile | |