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 BCL 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 BCL 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 ILis
t interface (see Section 3.4.2.5). 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 on an
ArrayList
that has been sorted but is otherwise
inefficient (and requires each item be checked).
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
bool
s, 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( ); 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 stored 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), 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 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
implements
ICollection
and can be manipulated like a normal
collection (see 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 BCL 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.Collections; public class MyCollection : IEnumerable { // ... public virtual IEnumerator GetEnumerator ( ) { return new MyCollection.Enumerator(this); } private class Enumerator : IEnumerator { private MyCollection collection; private int currentIndex = -1; internal Enumerator (MyCollection collection) { this.collection = collection; } public object Current { get { if (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 XXX foreach (XXX item in mcoll) { Console.WriteLine(item); ... } // Using IEnumerator: substitute your typename for XXX IEnumerator ie = myc.GetEnumerator( ); while (myc.MoveNext( )) { XXX item = (XXX)myc.Current; Console.WriteLine(item); ... }
public interface ICollection : IEnumerable { void CopyTo(Array array, int index); int Count {get;} bool IsReadOnly {get;} bool IsSynchronized {get;} object SyncRoot {get;} }
ICollection
is the interface implemented by all
collections, including arrays, and provides the following methods:
CopyTo(Array array, int index)
This method copies all the elements into the array starting at the specified index.
Count
This property returns the number of elements in the collection.
IsReadOnly
IsSynchronized
( )This method allows you to determine whether a collection is
thread-safe. The collections provided in the BCL are not themselves
thread-safe, but each one includes a Synchronized
method that returns a thread-safe wrapper of the collection.
SyncRoot
( )This property returns an object (usually the collection itself) that can be locked to provide basic thread-safe support for the collection.
public interface IComparer { int Compare(object x, object y); }
IComparer
is a standard interface that compares
two objects for sorting in Array
s. 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 IList : ICollection, IEnumerable { object this [int index] {get; set} 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); }
IList
is an interface for array-indexable
collections, such as ArrayList
.
public interface IDictionary : ICollection, IEnumerable { object this [object key] {get; set}; ICollection Keys {get;} ICollection Values {get;} void Clear( ); bool Contains(object value); IDictionaryEnumerator GetEnumerator( ); void Remove(object key); }
IDictionary
is an interface for key/value-based
collections, such as Hashtable
and
SortedList
.
3.133.141.219