The .NET Framework provides a rich suite of
collection
classes. With the advent of generics in 2.0 most of these collection
classes are now type-safe, making for a greatly enhanced programming
experience. These classes include the Array
,
List
, Dictionary
,
Sorted
Dictionary
,
Queue
, and Stack
.
The simplest collection is the Array
, the only
collection type for which C# provides built-in support. In this
chapter, you will learn to work with single, multidimensional, and
jagged arrays. Arrays have built-in indexers, allowing you to request
the nth member of the array. In this chapter you
will also be introduced to creating your own indexers, a bit of C#
syntactic sugar that makes it easier to access class properties as
though the class were indexed like an array.
The .NET Framework provides a number of interfaces, such as
IEnumerable
and ICollection
,
whose implementation provides you with standard ways to interact with
collections. In this chapter, you will see how to work with the most
essential of these. The chapter concludes with a tour of commonly
used .NET collections, including List
,
Dictionary
, Queue
, and
Stack
.
In previous versions of C#, the collection objects were not type-safe
(you could, for example, mix strings and integers in a
Dictionary
). The nontype-safe versions, of
List
(ArrayList
),
Dictionary
, and Queue
, and
Stack
are still available for backward
compatibility but won’t be covered in this book
because their use is similar to the generics-based versions and
because they are obsolete and deprecated.
An array is an indexed collection of objects, all of the same type. C# arrays are somewhat different from arrays in C++ because they are objects. This provides them with useful methods and properties.
C# provides native syntax for the declaration of
Arrays
. What is actually created, however, is an
object of type
System.Array
.[1] Arrays in C# thus
provide you with the best of both worlds: easy-to-use C-style syntax
underpinned with an actual class definition so that instances of an
array have access to the methods and properties of
System.Array
. These appear in Table 9-1.
Table 9-1. System.Array methods and properties
Method or property |
Purpose |
---|---|
Overloaded public static method that searches a one-dimensional sorted array. | |
Public static method that sets a range of elements in the array either to 0 or to a null reference. | |
Overloaded public static method that copies a section of one array to another array. | |
Overloaded public static method that instantiates a new instance of an array. | |
Overloaded public static method that returns the index (offset) of the first instance of a value in a one-dimensional array. | |
Overloaded public static method that returns the index of the last instance of a value in a one-dimensional array. | |
Overloaded public static method that reverses the order of the elements in a one-dimensional array. | |
Overloaded public static method that sorts the values in a one-dimensional array. | |
Required because | |
Public property (required because | |
Public property (required because | |
Public property that returns the length of the array. | |
Public property that returns the number of dimensions of the array. | |
Public property that returns an object that can be used to synchronize access to the array. | |
Public method that returns an | |
Public method that returns the length of the specified dimension in the array. | |
Public method that returns the lower boundary of the specified dimension of the array. | |
Public method that returns the upper boundary of the specified dimension of the array. | |
Initializes all values in a value type array by calling the default constructor for each value. With reference arrays, all elements in the array are set to null. | |
Overloaded public method that sets the specified array elements to a value. |
Declare a C# array with the following syntax:
type
[]array-name
;
For example:
int[] myIntArray;
You aren’t actually declaring an array. Technically,
you are declaring a variable (myIntArray
) that
will hold a reference to an array of integers. As always,
we’ll use the shorthand and refer to
myIntArray
as the array, knowing that what we
really mean is that it is a variable that holds a reference to an
(unnamed) array.
The square brackets
([]
) tell the C# compiler that you are declaring
an array, and the type specifies the type of the elements it will
contain. In the previous example, myIntArray
is an
array of integers.
Instantiate an array using the
new
keyword. For example:
myIntArray = new int[5];
This declaration creates and initializes an array of five integers,
all of which are initialized to the value 0
.
VB6 programmers take note: in C#, the value of the size of the array marks the number of elements in the array, not the upper bound. In fact, there is no way to set the upper or lower bounds (with the exception that you can set the lower bounds in multidimensional arrays (discussed later), but even that is not supported by the .NET Framework class library).
Thus, the first element in an array is 0. The following C# statement declares an array of 10 elements, with indices 0 through 9:
string myArray[10];
The upper bound is 9, not 10, and you can’t change
the size of the array (that is, there is no equivalent to the VB6
Redim
function).
It is important to distinguish between the array itself (which is a
collection of elements) and the elements of the array.
myIntArray
is the array (or, more accurately, the
variable that holds the reference to the array); its elements are the
five integers it holds.
C# arrays are reference
types, created on the heap. Thus, the array to which
myIntArray
refers is allocated on the
heap. The
elements
of an array are allocated based on their
own type. Since integers are value types, the elements in
myIntArray
will be value types,
not boxed integers, and thus all the elements
will be created inside the block of memory allocated for the array.
The block of memory allocated to an array of reference types will contain references to the actual elements, which are themselves created on the heap in memory separate from that allocated for the array.
When you create an array of value types, each element initially contains the default value for the type stored in the array (refer back to Table 4-2). The statement:
myIntArray = new int[5];
creates an array of five integers, each of whose value is set to
0
, which is the default value for integer types.
Unlike with arrays of value types, the reference types in an array aren’t initialized to their default value. Instead, the references held in the array are initialized to null. If you attempt to access an element in an array of reference types before you have specifically initialized the elements, you will generate an exception.
Assume you have created a Button
class. Declare an
array of Button
objects with the following
statement:
Button[] myButtonArray;
and instantiate the actual array like this:
myButtonArray = new Button[3];
You can shorten this to:
Button[] myButtonArray = new Button[3];
This statement doesn’t create an array with
references to three Button
objects. Instead, this
creates the array myButtonArray
with three null
references. To use this array, you must first construct and assign
the Button
objects for each reference in the
array. You can construct the objects in a loop that adds them one by
one to the array.
Access the elements of an array using
the
index
operator ([]
). Arrays are zero-based, which means
that the index of the first element is always 0—in this case,
myArray[0]
.
As explained previously, arrays are objects and thus have
properties. One of the more useful of
these is Length
, which tells you how many objects are
in an array. Array objects can be indexed from 0
to Length-1
. That is, if there are five elements
in an array, their indexes are 0,1,2,3,4.
Example 9-1 illustrates the array concepts covered
so far. In this example, a class named Tester
creates an array of Employees
and an array of
integers, populates the Employee
array, and then
prints the values of
both.
Example 9-1. Working with an array
namespace Programming_CSharp { // a simple class to store in the array public class Employee { public Employee(int empID) { this.empID = empID; } public override string ToString( ) { return empID.ToString( ); } private int empID; } public class Tester { static void Main( ) { int[] intArray; Employee[] empArray; intArray = new int[5]; empArray = new Employee[3]; // populate the array for (int i = 0;i<empArray.Length;i++) { empArray[i] = new Employee(i+5); } for (int i = 0;i<intArray.Length;i++) { Console.WriteLine(intArray[i].ToString( )); } for (int i = 0;i<empArray.Length;i++) { Console.WriteLine(empArray[i].ToString( )); } } } } Output: 0 0 0 0 0 5 6 7
The example starts with the definition of an
Employee
class that implements a constructor that
takes a single integer parameter. The ToString()
method inherited from Object
is overridden to
print the value of the Employee
object’s employee ID.
The test method declares and then instantiates a pair of arrays. The
integer array is automatically filled with integers whose values are
set to 0. The Employee
array contents must be
constructed by hand.
Finally, the contents of the arrays are printed to ensure that they
are filled as intended. The five integers print their value first,
followed by the three Employee
objects.
The
foreach
looping statement is new to the C
family of languages, though it is already well-known to VB
programmers. The foreach
statement allows you to
iterate through all the items in an array or other collection,
examining each item in turn. The syntax for the
foreach
statement is:
foreach (type identifier
inexpression
)statement
Thus, you might update Example 9-1 to replace the
for
statements that iterate over the contents of
the populated array with foreach
statements, as
shown in Example 9-2.
Example 9-2. Using foreach
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace UsingForEach { // a simple class to store in the array public classEmployee { // a simple class to store in the array public Employee( int empID ) { this.empID = empID; } public override string ToString( ) { return empID.ToString( ); } private int empID; } public class Tester { static void Main( ) { int[] intArray; Employee[] empArray; intArray = new int[5]; empArray = new Employee[3]; // populate the array for ( int i = 0; i < empArray.Length; i++ ) { empArray[i] = new Employee( i + 5 ); } foreach ( int i in intArray ) { Console.WriteLine( i.ToString( ) ); } foreach ( Employee e in empArray ) { Console.WriteLine( e.ToString( ) ); } } } } }
The output for Example 9-2 is identical to Example 9-1. However, instead of creating a
for
statement that measures the size of the array
and uses a temporary counting variable as an index into the array as
in the following, we try another approach:
for (int i = 0; i < empArray.Length; i++) { Console.WriteLine(empArray[i].ToString()); }
We iterate over the array with the foreach
loop,
which automatically extracts the next item from within the array and
assigns it to the temporary object you’ve created in
the head of the statement:
foreach (Employee e in empArray) { Console.WriteLine(e.ToString()); }
The object extracted from the array is of the appropriate type; thus, you may call any public method on that object.
It is possible to initialize the
contents of an array at the time it is instantiated by providing a
list of values delimited by curly brackets ({}
).
C# provides a longer and a shorter syntax:
int[] myIntArray = new int[5] { 2, 4, 6, 8, 10 } int[] myIntArray = { 2, 4, 6, 8, 10 }
There is no practical difference between these two statements, and most programmers will use the shorter syntax, but see the following note.
You can create a method that displays any number of integers to the
console by passing in an array of integers and then iterating over
the array with a foreach
loop. The
params
keyword allows
you to pass in a variable number of parameters without necessarily
explicitly creating the array.
In the next example, you create a method,
DisplayVals()
, that takes a variable number of
integer arguments:
public void DisplayVals(params int[] intVals)
The method itself can treat the array as if an integer array were explicitly created and passed in as a parameter. You are free to iterate over the array as you would over any other array of integers:
foreach (int i in intVals) { Console.WriteLine("DisplayVals {0}",i); }
The calling method, however, need not explicitly create an array: it
can simply pass in integers, and the compiler will assemble the
parameters into an array for the DisplayVals( )
method:
t.DisplayVals(5,6,7,8);
You are free to pass in an array if you prefer:
int [] explicitArray = new int[5] {1,2,3,4,5}; t.DisplayVals(explicitArray);
Example 9-3 provides the complete source code
illustrating the params
keyword.
Example 9-3. Using the params keyword
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace UsingParams { public classTester { static void Main( ) { Tester t = new Tester( ); t.DisplayVals(5,6,7,8); int [] explicitArray = new int[5] {1,2,3,4,5}; t.DisplayVals(explicitArray); } public void DisplayVals(params int[] intVals) { foreach (int i in intVals) { Console.WriteLine("DisplayVals {0}",i); } } } } Output: DisplayVals 5 DisplayVals 6 DisplayVals 7 DisplayVals 8 DisplayVals 1 DisplayVals 2 DisplayVals 3 DisplayVals 4 DisplayVals 5
Arrays can be thought of as long rows of slots into which values can be placed. Once you have a picture of a row of slots, imagine 10 rows, one on top of another. This is the classic two-dimensional array of rows and columns. The rows run across the array and the columns run up and down the array.
A third dimension is possible, but somewhat harder to imagine. Make your arrays three-dimensional, with new rows stacked atop the old two-dimensional array. OK, now imagine four dimensions. Now imagine 10.
Those of you who aren’t string-theory physicists have probably given up, as have I. Multidimensional arrays are useful, however, even if you can’t quite picture what they would look like.
C# supports two types of multidimensional arrays: rectangular and jagged. In a rectangular array, every row is the same length. A jagged array, however, is an array of arrays, each of which can be a different length.
A rectangular array is an array of two (or more) dimensions. In the classic two- dimensional array, the first dimension is the number of rows and the second dimension is the number of columns.
To declare a two-dimensional array, use the following syntax:
type
[,]array-name
For example, to declare and instantiate a two-dimensional rectangular
array named myRectangularArray
that contains two
rows and three columns of integers, you would write:
int [,] myRectangularArray = new int[2,3];
Example 9-4
declares, instantiates, initializes,
and prints the contents of a two- dimensional array. In this example,
a for
loop is used to initialize the elements of
the array.
Example 9-4. Rectangular array
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace RectangularArray { public classTester { static void Main( ) { const int rows = 4; const int columns = 3; // declare a 4x3 integer array int[,] rectangularArray = new int[rows, columns]; // populate the array for ( int i = 0; i < rows; i++ ) { for ( int j = 0; j < columns; j++ ) { rectangularArray[i, j] = i + j; } } // report the contents of the array for ( int i = 0; i < rows; i++ ) { for ( int j = 0; j < columns; j++ ) { Console.WriteLine( "rectangularArray[{0},{1}] = {2}", i, j, rectangularArray[i, j] ); } } } } } Output: rectangularArray[0,0] = 0 rectangularArray[0,1] = 1 rectangularArray[0,2] = 2 rectangularArray[1,0] = 1 rectangularArray[1,1] = 2 rectangularArray[1,2] = 3 rectangularArray[2,0] = 2 rectangularArray[2,1] = 3 rectangularArray[2,2] = 4 rectangularArray[3,0] = 3 rectangularArray[3,1] = 4 rectangularArray[3,2] = 5
In this example, you declare a pair of constant values:
const int rows = 4; const int columns = 3;
that are then used to dimension the array:
int[,] rectangularArray = new int[rows, columns];
Notice the syntax. The brackets in the int[,]
declaration indicate that the type is an array of integers, and the
comma indicates the array has two
dimensions (two commas would indicate three dimensions, and so on).
The actual instantiation of rectangularArray
with
new
int[rows
,
columns]
sets the size of each dimension. Here the
declaration and instantiation have been combined.
The program fills the rectangle with a pair of for
loops, iterating through each column in each row. Thus, the first
element filled is rectangularArray[0,0]
, followed
by rectangularArray[0,1]
and
rectangularArray[0,2]
. Once this is done, the
program moves on to the next rows:
rectangularArray[1,0]
,
rectangularArray[1,1]
,
rectangularArray[1,2]
, and so forth, until all the
columns in all the rows are filled.
Just as you can initialize a one-dimensional array using bracketed
lists of values, you can
initialize
a two-dimensional array using similar syntax. Example 9-5 declares a two-dimensional array
(rectangularArray
), initializes its elements using
bracketed lists of values, and then prints out the contents.
Example 9-5. Initializing a multidimensional array
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace InitializingMultiDimensionalArray { public classTester { static void Main( ) { const int rows = 4; const int columns = 3; // imply a 4x3 array int[,] rectangularArray = { {0,1,2}, {3,4,5}, {6,7,8}, {9,10,11} }; for ( int i = 0; i < rows; i++ ) { for ( int j = 0; j < columns; j++ ) { Console.WriteLine( "rectangularArray[{0},{1}] = {2}", i, j, rectangularArray[i, j] ); } } } } } Output: rectangularArrayrectangularArray[0,0] = 0 rectangularArrayrectangularArray[0,1] = 1 rectangularArrayrectangularArray[0,2] = 2 rectangularArrayrectangularArray[1,0] = 3 rectangularArrayrectangularArray[1,1] = 4 rectangularArrayrectangularArray[1,2] = 5 rectangularArrayrectangularArray[2,0] = 6 rectangularArrayrectangularArray[2,1] = 7 rectangularArrayrectangularArray[2,2] = 8 rectangularArrayrectangularArray[3,0] = 9 rectangularArrayrectangularArray[3,1] = 10 rectangularArrayrectangularArray[3,2] = 11
The preceding example is similar to Example 9-4, but this time you imply the exact dimensions of the array by how you initialize it:
int[,] rectangularArrayrectangularArray = { {0,1,2}, {3,4,5}, {6,7,8}, {9,10,11} };
Assigning values in four bracketed lists, each consisting of three elements, implies a 4 3 array. Had you written this as:
int[,] rectangularArrayrectangularArray = { {0,1,2,3}, {4,5,6,7}, {8,9,10,11} };
you would instead have implied a 3 4 array.
You can see that the C# compiler understands the implications of your clustering, since it can access the objects with the appropriate offsets, as illustrated in the output.
You might guess that since this is a 12-element array you can just as
easily access an element at rectangularArray[0,3]
(the fourth element in the first row) as at
rectangularArray[1,0]
(the first element in the
second row) This works in C++, but if you try it in C#, you will run
right into an exception:
Exception occurred: System.IndexOutOfRangeException: Index was outside the bounds of the array. at Programming_CSharp.Tester.Main() in csharpprogramming csharplisting0703.cs:line 23
C# arrays are smart, and they keep track of their bounds. When you imply a 4 3 array, you must treat it as such.
A jagged array is an array of arrays. It is called “jagged” because each row need not be the same size as all the others, and thus a graphical representation of the array would not be square.
When you create a jagged array, you declare the number of rows in your array. Each row will hold an array, which can be of any length. These arrays must each be declared. You can then fill in the values for the elements in these “inner” arrays.
In a jagged array, each dimension is a one-dimensional array. To declare a jagged array, use the following syntax, where the number of brackets indicates the number of dimensions of the array:
type
[] []...
For example, you would declare a two-dimensional jagged array of
integers named myJaggedArray
as follows:
int [] [] myJaggedArray;
Access the fifth element of the third array by writing
myJaggedArray[2][4]
.
Example 9-6 creates a jagged array named
myJaggedArray
, initializes its elements, and then
prints their content. To save space, the program takes advantage of
the fact that integer array elements are automatically initialized to
0, and it initializes the values of only some of the elements.
Example 9-6. Working with a jagged array
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace JaggedArray { public classTester { static void Main( ) { const int rows = 4; // declare the jagged array as 4 rows high int[][] jaggedArray = new int[rows][]; // the first row has 5 elements jaggedArray[0] = new int[5]; // a row with 2 elements jaggedArray[1] = new int[2]; // a row with 3 elements jaggedArray[2] = new int[3]; // the last row has 5 elements jaggedArray[3] = new int[5]; // Fill some (but not all) elements of the rows jaggedArray[0][3] = 15; jaggedArray[1][1] = 12; jaggedArray[2][1] = 9; jaggedArray[2][2] = 99; jaggedArray[3][0] = 10; jaggedArray[3][1] = 11; jaggedArray[3][2] = 12; jaggedArray[3][3] = 13; jaggedArray[3][4] = 14; for ( int i = 0; i < 5; i++ ) { Console.WriteLine( "jaggedArray[0][{0}] = {1}", i, jaggedArray[0][i] ); } for ( int i = 0; i < 2; i++ ) { Console.WriteLine( "jaggedArray[1][{0}] = {1}", i, jaggedArray[1][i] ); } for ( int i = 0; i < 3; i++ ) { Console.WriteLine( "jaggedArray[2][{0}] = {1}", i, jaggedArray[2][i] ); } for ( int i = 0; i < 5; i++ ) { Console.WriteLine( "jaggedArray[3][{0}] = {1}", i, jaggedArray[3][i] ); } } } } Output: jaggedArray[0][0] = 0 jaggedArray[0][1] = 0 jaggedArray[0][2] = 0 jaggedArray[0][3] = 15 jaggedArray[0][4] = 0 jaggedArray[1][0] = 0 jaggedArray[1][1] = 12 jaggedArray[2][0] = 0 jaggedArray[2][1] = 9 jaggedArray[2][2] = 99 jaggedArray[3][0] = 10 jaggedArray[3][1] = 11 jaggedArray[3][2] = 12 jaggedArray[3][3] = 13 jaggedArray[3][4] = 14
In this example, a jagged array is created with four rows:
int[][] jaggedArray = new int[rows][];
Notice that the second dimension is not specified. This is set by creating a new array for each row. Each array can have a different size:
// the first row has 5 elements jaggedArray[0] = new int[5]; // a row with 2 elements jaggedArray[1] = new int[2]; // a row with 3 elements jaggedArray[2] = new int[3]; // the last row has 5 elements jaggedArray[3] = new int[5];
Once an array is specified for each row, you need only populate the various members of each array and then print out their contents to ensure that all went as expected.
Notice that when you access the members of the rectangular array, you put the indexes all within one set of square brackets:
rectangularArrayrectangularArray[i,j]
while with a jagged array you need a pair of brackets:
jaggedArray[3][i]
You can keep this straight by thinking of the first as a single array of more than one dimension and of the jagged array as an array of arrays.
The Array
class can also
be created by using the overloaded
CreateInstance
method. One of the overloads allows
you to specify the lower bounds (
starting index) of each dimension
in a multidimensional array. This is a fairly obscure capability, not
often used.
Briefly, here is how you do it: you call the static method
CreateInstance
, that returns an
Array
, and that takes three parameters: an object
of type Type
(indicating the type of object to
hold in the array), an array of integers indicating the length of
each dimension in the array, and a second array of integers
indicating the lower bound for each dimension. Note that the two
arrays of integers must have the same number of elements; that is,
you must specify a lower bound for each dimension:
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace SettingArrayBounds { public classSettingArrayBounds { public static void CreateArrayWithBounds( ) { // Creates and initializes a multidimensional // Array of type String. int[] lengthsArray = new int[2] { 3, 5 }; int[] boundsArray = new int[2] { 2, 3 }; Array multiDimensionalArray = Array.CreateInstance( typeof( String ), lengthsArray, boundsArray ); // Displays the lower bounds and the // upper bounds of each dimension. Console.WriteLine( "Bounds: Lower Upper" ); for ( int i = 0; i < multiDimensionalArray.Rank; i++ ) Console.WriteLine( "{0}: {1} {2}", i, multiDimensionalArray.GetLowerBound( i ), multiDimensionalArray.GetUpperBound( i ) ); } static void Main( ) { SettingArrayBounds.CreateArrayWithBounds( ); } } }
Conversion is possible between arrays if their dimensions are equal and if a conversion is possible between the reference element types. An implicit conversion can occur if the elements can be implicitly converted; otherwise an explicit conversion is required.
It is also possible, of course, to convert an array of derived
objects to an array of base objects. Example 9-7
illustrates the conversion of an array of user-defined
Employee
types to an array of objects.
Example 9-7. Converting arrays
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace ConvertingArrays { // create an object we can // store in the array public classEmployee { // a simple class to store in the array public Employee( int empID ) { this.empID = empID; } public override string ToString( ) { return empID.ToString( ); } private int empID; } public class Tester { // This method takes an array of objects. // We'll pass in an array of Employees // and then an array of strings. // The conversion is implicit since both Employee // and string derive (ultimately) from object. public static void PrintArray( object[] theArray ) { Console.WriteLine( "Contents of the Array {0}", theArray.ToString( ) ); // walk through the array and print // the values. foreach ( object obj in theArray ) { Console.WriteLine( "Value: {0}", obj ); } } static void Main( ) { // make an array of Employee objects Employee[] myEmployeeArray = new Employee[3]; // initialize each Employee's value for ( int i = 0; i < 3; i++ ) { myEmployeeArray[i] = new Employee( i + 5 ); } // display the values PrintArray( myEmployeeArray ); // create an array of two strings string[] array = { "hello", "world" }; // print the value of the strings PrintArray( array ); } } } Output: Contents of the Array Programming_CSharp.Employee[] Value: 5 Value: 6 Value: 7 Contents of the Array System.String[] Value: hello Value: world
Example 9-7 begins by creating a simple
Employee
class, as seen earlier in the chapter.
The Tester
class now contains a new static method,
PrintArray( )
, that takes as a parameter a
one-dimensional array of Object
s:
public static void PrintArray(object[] theArray)
Object
is the implicit base class of every object
in the .NET Framework, and so is the base class of both
String
and Employee
.
The PrintArray()
method takes two actions. First,
it calls the ToString()
method on the array
itself:
Console.WriteLine("Contents of the Array {0}", theArray.ToString());
System.Array
overrides the
ToString( )
method to your advantage, printing an identifying name of the array:
Contents of the Array Programming_CSharp. Employee [] Contents of the Array System.String[]
PrintArray( )
then goes on to call
ToString()
on each element in the array it
receives as a parameter. Because ToString( )
is a
virtual method in the base class Object
, it is
guaranteed to be available in every derived class. You have
overridden this method appropriately in Employee
so that the code works properly. Calling
ToString( )
on a String
object
might not be necessary, but it is harmless and it allows you to treat
these objects polymorphically.
Two
useful
static methods of
Array
are
Sort()
and Reverse()
. These are
fully supported for arrays of the built-in C# types such as
string
. Making them work with your own classes is
a bit trickier, as you must implement the
IComparable
interface (see the section
“Implementing IComparable” later in
this chapter). Example 9-8 demonstrates the use of
these two methods to manipulate String
objects.
Example 9-8. Using Array.Sort and Array.Reverse
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace ArraySortAndReverse { public classTester { public static void PrintMyArray( object[] theArray ) { foreach ( object obj in theArray ) { Console.WriteLine( "Value: {0}", obj ); } Console.WriteLine( " " ); } static void Main( ) { String[] myArray = { "Who", "is", "John", "Galt" }; PrintMyArray( myArray ); Array.Reverse( myArray ); PrintMyArray( myArray ); String[] myOtherArray = { "We", "Hold", "These", "Truths", "To", "Be", "Self","Evident", }; PrintMyArray( myOtherArray ); Array.Sort( myOtherArray ); PrintMyArray( myOtherArray ); } } } Output: Value: Who Value: is Value: John Value: Galt Value: Galt Value: John Value: is Value: Who Value: We Value: Hold Value: These Value: Truths Value: To Value: Be Value: Self Value: Evident Value: Be Value: Evident Value: Hold Value: Self Value: These Value: To Value: Truths Value: We
The example begins by creating myArray
, an array
of strings with the words:
"Who", "is", "John", "Galt"
This array is printed, and then passed to the
Array.Reverse( )
method, where it is printed again
to see that the array itself has been reversed:
Value: Galt Value: John Value: is Value: Who
Similarly, the example creates a second array,
myOtherArray
, containing the words:
"We", "Hold", "These", "Truths", "To", "Be", "Self", "Evident",
This is passed to the Array.Sort( )
method. Then
Array.Sort()
happily sorts them alphabetically:
Value: Be Value: Evident Value: Hold Value: Self Value: These Value: To Value: Truths Value: We
There
are times when it is desirable to access a
collection within
a class as though
the class itself were an array. For example, suppose you create a
listbox control named myListBox
that contains a
list of strings stored in a one-dimensional array, a private member
variable named myStrings
. A listbox control
contains member properties and methods in addition to its array of
strings. However, it would be convenient to be able to access the
listbox array with an index, just as if the listbox were an
array.[2] For
example, such a property would permit statements such as the
following:
string theFirstString = myListBox[0]; string theLastString = myListBox[Length-1];
An
indexer
is a C# construct that allows you to access collections contained by
a class using the familiar []
syntax of arrays. An
indexer is a special kind of property and includes
get
and set
accessors to
specify its behavior.
You declare an indexer property within a class using the following syntax:
type
this [type argument
]{get; set;}
The return type determines the type of object that will be returned by the indexer, while the type argument specifies what kind of argument will be used to index into the collection that contains the target objects. Although it is common to use integers as index values, you can index a collection on other types as well, including strings. You can even provide an indexer with multiple parameters to create a multidimensional array!
The
this
keyword is a
reference to the object in which the indexer appears. As with a
normal property, you also must define get
and
set
accessors, which determine how the requested
object is retrieved from or assigned to its collection.
Example 9-9 declares a listbox control
(ListBoxTest
) that contains a simple array
(myStrings)
and a simple indexer for accessing its
contents.
C++
programmers take note: the indexer serves much the same
purpose as overloading the C++ index operator
([]
). The index operator can’t be
overloaded in C#, which provides the indexer in its place.
Example 9-9. Using a simple indexer
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace SimpleIndexer { // a simplified ListBox control public classListBoxTest { private string[] strings; private int ctr = 0; // initialize the list box with strings public ListBoxTest( params string[] initialStrings ) { // allocate space for the strings strings = new String[256]; // copy the strings passed in to the constructor foreach ( string s in initialStrings ) { strings[ctr++] = s; } } // add a single string to the end of the list box public void Add( string theString ) { if ( ctr >= strings.Length ) { // handle bad index } else strings[ctr++] = theString; } // allow array-like access public string this[int index] { get { if ( index < 0 || index >= strings.Length ) { // handle bad index } return strings[index]; } set { // add only through the add method if ( index >= ctr ) { // handle error } else strings[index] = value; } } // publish how many strings you hold public int GetNumEntries( ) { return ctr; } } public class Tester { static void Main( ) { // create a new list box and initialize ListBoxTest lbt = new ListBoxTest( "Hello", "World" ); // add a few strings lbt.Add( "Who" ); lbt.Add( "Is" ); lbt.Add( "John" ); lbt.Add( "Galt" ); // test the access string subst = "Universe"; lbt[1] = subst; // access all the strings for ( int i = 0; i < lbt.GetNumEntries( ); i++ ) { Console.WriteLine( "lbt[{0}]: {1}", i, lbt[i] ); } } } } Output: lbt[0]: Hello lbt[1]: Universe lbt[2]: Who lbt[3]: Is lbt[4]: John lbt[5]: Galt
To keep Example 9-9 simple, we strip the listbox control down to the few features we care about. The listing ignores everything having to do with being a user control and focuses only on the list of strings the listbox maintains and methods for manipulating them. In a real application, of course, these are a small fraction of the total methods of a listbox, whose principal job is to display the strings and enable user choice.
The first things to notice are the two private members:
private string[] strings; private int ctr = 0;
In this program, the listbox maintains a simple array of strings:
strings
. Again, in a real listbox you might use a
more complex and dynamic container, such as a hash table (described
later in this chapter). The member variable ctr
will keep track of how many strings have been added to this array.
Initialize the array in the constructor with the statement:
strings = new String[256];
The remainder of the constructor adds the parameters to the array. Again, for simplicity, add new strings to the array in the order received.
Because you can’t know how many strings will be
added, use the keyword
params
, as described earlier in this chapter.
The Add()
method of ListBoxTest
does nothing more than append a new string to the internal array.
The key method of ListBoxTest
, however, is the
indexer. An indexer is unnamed, so use the this
keyword:
public string this[int index]
The syntax of the
indexer
is very similar to that for properties. There is either a
get( )
method, a set()
method, or both. In the case
shown, the get( )
method endeavors to implement
rudimentary bounds-checking, and assuming the index requested is
acceptable, it returns the value requested:
get { if (index < 0 || index >= strings.Length) { // handle bad index } return strings[index]; }
The set( )
method checks to make sure that the
index you are setting already has a value in the listbox. If not, it
treats the set as an error. (New elements can only be added using
Add
with this approach.) The
set
accessor takes advantage of the implicit
parameter value
that represents whatever is
assigned using the index operator:
set { if (index >= ctr ) { // handle error } else strings[index] = value; }
Thus, if you write:
lbt[5] = "Hello World"
the compiler will call the indexer set()
method on
your object and pass in the string Hello
World
as an implicit parameter named
value
.
In Example 9-9, you can’t assign to an index that doesn’t have a value. Thus, if you write:
lbt[10] = "wow!";
you would trigger the error handler in the set()
method, which would note that the index you’ve
passed in (10
) is larger than the counter
(6
).
Of course, you can use the set()
method for
assignment; you simply have to handle the indexes you receive. To do
so, you might change the set()
method to check the
Length
of the buffer rather than the current value
of counter
. If a value was entered for an index
that did not yet have a value, you would update
ctr
:
set { // add only through the add method if (index >= strings.Length ) { // handle error } else { strings[index] = value; if (ctr < index+1) ctr = index+1; } }
This code is kept simple and thus is not robust. There are any number
of other checks you’ll want to make on the value
passed in (e.g., checking that you were not passed a negative index
and that it doesn’t exceed the size of the
underlying strings[]
array).
This allows you to create a “sparse” array in which you can assign to offset 10 without ever having assigned to offset 9. Thus, if you now write:
lbt[10] = "wow!";
the output would be:
lbt[0]: Hello lbt[1]: Universe lbt[2]: Who lbt[3]: Is lbt[4]: John lbt[5]: Galt lbt[6]: lbt[7]: lbt[8]: lbt[9]: lbt[10]: wow!
In Main( )
, you create an instance of the
ListBoxTest
class named lbt
and
pass in two strings as parameters:
ListBoxTest lbt = new ListBoxTest("Hello", "World");
Then call Add()
to add four more strings:
// add a few strings lbt.Add("Who"); lbt.Add("Is"); lbt.Add("John"); lbt.Add("Galt");
Before examining the values, modify the second value (at index
1
):
string subst = "Universe"; lbt[1] = subst;
Finally, display each value in a loop:
for (int i = 0;i<lbt.GetNumEntries();i++) { Console.WriteLine("lbt[{0}]: {1}",i,lbt[i]); }
C# doesn’t require that you always use an integer value as the index to a collection. When you create a custom collection class and create your indexer, you are free to create indexers that index on strings and other types. In fact, the index value can be overloaded so that a given collection can be indexed, for example, by an integer value or by a string value, depending on the needs of the client.
In the case of our listbox, we might want to be able to index into
the listbox based on a string. Example 9-10
illustrates a string index. The indexer calls
findString( )
, which is a helper method that
returns a record based on the value of the string provided. Notice
that the overloaded indexer and the indexer from Example 9-9 are able to coexist.
Example 9-10. Overloading an index
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace OverloadedIndexer { // a simplified ListBox control public classListBoxTest { private string[] strings; private int ctr = 0; // initialize the list box with strings public ListBoxTest( params string[] initialStrings ) { // allocate space for the strings strings = new String[256]; // copy the strings passed in to the constructor foreach ( string s in initialStrings ) { strings[ctr++] = s; } } // add a single string to the end of the list box public void Add( string theString ) { strings[ctr] = theString; ctr++; } // allow array-like access public string this[int index] { get { if ( index < 0 || index >= strings.Length ) { // handle bad index } return strings[index]; } set { strings[index] = value; } } private int findString( string searchString ) { for ( int i = 0; i < strings.Length; i++ ) { if ( strings[i].StartsWith( searchString ) ) { return i; } } return -1; } // index on string public string this[string index] { get { if ( index.Length == 0 ) { // handle bad index } return this[findString( index )]; } set { strings[findString( index )] = value; } } // publish how many strings you hold public int GetNumEntries( ) { return ctr; } } public class Tester { static void Main( ) { // create a new list box and initialize ListBoxTest lbt = new ListBoxTest( "Hello", "World" ); // add a few strings lbt.Add( "Who" ); lbt.Add( "Is" ); lbt.Add( "John" ); lbt.Add( "Galt" ); // test the access string subst = "Universe"; lbt[1] = subst; lbt["Hel"] = "GoodBye"; // lbt["xyz"] = "oops"; // access all the strings for ( int i = 0; i < lbt.GetNumEntries( ); i++ ) { Console.WriteLine( "lbt[{0}]: {1}", i, lbt[i] ); } // end for } // end main } // end tester } Output: lbt[0]: GoodBye lbt[1]: Universe lbt[2]: Who lbt[3]: Is lbt[4]: John lbt[5]: Galt
Example 9-10 is identical to Example 9-9 except for the addition of an overloaded
indexer, which can match a string, and the method
findString
, created to support that index.
The findString
method simply iterates through the
strings held in myStrings
until it finds a string
that starts with the target string we use in the index. If found, it
returns the index of that string; otherwise it returns the value
-1
.
We see in Main()
that the user passes in a string
segment to the index, just as with an integer:
lbt["Hel"] = "GoodBye";
This calls the overloaded index, which does some rudimentary
error-checking (in this case, making sure the string passed in has at
least one letter) and then passes the value (Hel
)
to findString
. It gets back an index and uses that
index to index into myStrings
:
return this[findString(index)];
The set
value works in the same way:
myStrings[findString(index)] = value;
The careful reader will note that if the string
doesn’t match, a value of -1
is
returned, which is then used as an index into
myStrings
. This action then generates an exception
(System.NullReferenceException)
, as you can see by
uncommenting the following line in Main(
)
:
lbt["xyz"] = "oops";
The .NET Framework provides two sets of standard interfaces for enumerating and comparing collections: the traditional (nontype-safe) and the new generic type-safe collections. This book focuses only on the new, type-safe collection interfaces as these are far preferable.
You can declare an ICollection
of any specific
type by substituting the
actual
type (for
example, int
or string
) for the
generic type in the interface declaration
(<T>
).
C++ programmers note: C# generics are similar in syntax and usage to C++ templates. However, because the generic types are expanded to their specific type at runtime, the JIT compiler is able to share code among different instances, dramatically reducing the code bloat that you may see when using templates in C++.
The key generic collection interfaces are listed in Table 9-2.[3]
Table 9-2. Collection interfaces
You
can support the
foreach
statement in
ListBoxTest
by implementing the
IEnumerable<T>
interface (see Example 9-11). IEnumerable
has only one
method,
GetEnumerator( )
,
whose job is to return an implementation of
IEnumerator<T>
. The C# language provides
special help in creating the enumerator, using the new keyword
yield
.
Example 9-11. Making a ListBox an enumerable class
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace Enumerable { public classListBoxTest : IEnumerable<String> { private string[] strings; private int ctr = 0; // Enumerable classes can return an enumerator public IEnumerator<string> GetEnumerator( ) { foreach ( string s in strings ) { yield return s; } } // initialize the list box with strings public ListBoxTest( params string[] initialStrings ) { // allocate space for the strings strings = new String[8]; // copy the strings passed in to the constructor foreach ( string s in initialStrings ) { strings[ctr++] = s; } } // add a single string to the end of the list box public void Add( string theString ) { strings[ctr] = theString; ctr++; } // allow array-like access public string this[int index] { get { if ( index < 0 || index >= strings.Length ) { // handle bad index } return strings[index]; } set { strings[index] = value; } } // publish how many strings you hold public int GetNumEntries( ) { return ctr; } } public class Tester { static void Main( ) { // create a new list box and initialize ListBoxTest lbt = new ListBoxTest( "Hello", "World" ); // add a few strings lbt.Add( "Who" ); lbt.Add( "Is" ); lbt.Add( "John" ); lbt.Add( "Galt" ); // test the access string subst = "Universe"; lbt[1] = subst; // access all the strings foreach ( string s in lbt ) { Console.WriteLine( "Value: {0}", s ); } } } } Output: Value: Hello Value: Universe Value: Who Value: Is Value: John Value: Galt Value: Value:
The program begins in Main( )
, creating a new
ListBoxTest
object and passing two strings to the
constructor. When the object is created, an array of
Strings
is created with enough room for eight
strings. Four more strings are added using the Add
method, and the second string is updated, just as in the previous
example.
The big change in this version of the program is that a
foreach
loop is called, retrieving each string
in the listbox. The foreach
loop automatically
uses the IEnumerable<T>
interface, invoking
GetEnumerator( )
.
The GetEnumerator
method is declared to return an
IEnumerator
of string:
publicIEnumerator<string> GetEnumerator( )
The implementation iterates through the array of strings, yielding each in turn:
foreach ( string s in strings ) { yield return s; }
All the bookkeeping for keeping track of which element is next, resetting the iterator, and so forth, is provided for you by the framework.
There are times when you must ensure
that the elements you add to a generic list meet certain constraints
(e.g., they derive from a given base class, or they implement a
specific interface). In the next example, we implement a simplified
singly linked, sortable list. The list consists of
Node
s, and each Node
must be
guaranteed that the types added to it implement
IComparer
. You do so with the following statement:
public class Node<T> :IComparable<Node<T>> where T : IComparable<T>
This defines a generic Node
that holds a type,
T
. Node
of T
implements the IComparable<T>
interface,
which means that two Nodes
of T
can be compared. The Node
class is constrained
(where
T
:IComparable<T>
) to hold only types that
implement the IComparable
interface. Thus, you may
substitute any type for T
so long as that type
implements IComparable
.
Example 9-12 illustrates the complete implementation, with analysis to follow.
Example 9-12. Using constraints
using System; using System.Collections.Generic; namespace UsingConstraints { public classEmployee : IComparable<Employee> { private string name; public Employee(string name) { this.name = name; } public override string ToString( ) { return this.name; } // implement the interface public int CompareTo(Employee rhs) { return this.name.CompareTo(rhs.name); } public bool Equals(Employee rhs) { return this.name == rhs.name; } } // node must implement IComparable of Node of T. // constrain Nodes to only take items that implement Icomparable // by using the where keyword. public class Node<T> : IComparable<Node<T>> where T : IComparable<T> { // member fields private T data; private Node<T> next = null; private Node<T> prev = null; // constructor public Node(T data) { this.data = data; } // properties public T Data { get { return this.data; } } public Node<T> Next { get { return this.next; } } public int CompareTo(Node<T> rhs) { // this works because of the constraint return data.CompareTo(rhs.data); } public bool Equals(Node<T> rhs) { return this.data.Equals(rhs.data); } // methods public Node<T> Add(Node<T> newNode) { if (this.CompareTo(newNode) > 0) // goes before me { newNode.next = this; // new node points to me // if I have a previous, set it to point to // the new node as its next if (this.prev != null) { this.prev.next = newNode; newNode.prev = this.prev; } // set prev in current node to point to new node this.prev = newNode; // return the newNode in case it is the new head return newNode; } else // goes after me { // if I have a next, pass the new node along for // comparison if (this.next != null) { this.next.Add(newNode); } // I don't have a next so set the new node // to be my next and set its prev to point to me. else { this.next = newNode; newNode.prev = this; } return this; } } public override string ToString( ) { string output = data.ToString( ); if (next != null) { output += ", " + next.ToString( ); } return output; } } // end class public class LinkedList<T> where T : IComparable<T> { // member fields private Node<T> headNode = null; // properties // indexer public T this[int index] { get { int ctr = 0; Node<T> node = headNode; while (node != null && ctr <= index) { if (ctr == index) { return node.Data; } else { node = node.Next; } ++ctr; } // end while throw new ArgumentOutOfRangeException( ); } // end get } // end indexer // constructor public LinkedList( ) { } // methods public void Add(T data) { if (headNode == null) { headNode = new Node<T>(data); } else { headNode = headNode.Add(new Node<T>(data)); } } public override string ToString( ) { if (this.headNode != null) { return this.headNode.ToString( ); } else { return string.Empty; } } } // Test engine class Test { // entry point static void Main(string[] args) { // make an instance, run the method Test t = new Test( ); t.Run( ); } public void Run( ) { LinkedList<int> myLinkedList = new LinkedList<int>( ); Random rand = new Random( ); Console.Write("Adding: "); for (int i = 0; i < 10; i++) { int nextInt = rand.Next(10); Console.Write("{0} ", nextInt); myLinkedList.Add(nextInt); } LinkedList<Employee> employees = new LinkedList<Employee>( ); employees.Add(new Employee("John")); employees.Add(new Employee("Paul")); employees.Add(new Employee("George")); employees.Add(new Employee("Ringo")); Console.WriteLine(" Retrieving collections..."); Console.WriteLine("Integers: " + myLinkedList); Console.WriteLine("Employees: " + employees); } } }
In this example, you begin by declaring a class that can be placed into the linked list:
public class Employee : IComparable<Employee>
This declaration indicates that Employee
objects
are comparable, and we see that the Employee
class
implements the required methods
(CompareTo
and Equals
). Note
that these methods are type-safe (they know that the parameter passed
to them will be of type Employee
). The
LinkedList
itself is declared to hold only types
that implement IComparable
:
public class LinkedList<T> where T : IComparable<T>
so you are guaranteed to be able to sort the list. The
LinkedList
holds an object of type
Node
. Node
also implements
IComparable
and requires that the objects it holds
as data themselves implement IComparable
:
public class Node<T> : IComparable<Node<T>> where T : IComparable<T>
These constraints make it safe and simple to implement the
CompareTo
method of Node
because the Node
knows it will be comparing other
Nodes
whose data is comparable:
public int CompareTo(Node<T> rhs) { // this works because of the constraint return data.CompareTo(rhs.data); }
Notice that we don’t have to test
rhs
to see if it implements
IComparable
; we’ve already
constrained Node
to hold only data that implements
IComparable
.
The classic problem with the
Array
type is its fixed
size. If you don’t know in
advance how many objects an array will hold, you run the risk of
declaring either too small an array (and running out of room) or too
large an array (and wasting memory).
Your program might be asking the user for input, or gathering input from a web site. As it finds objects (strings, books, values, etc.), you will add them to the array, but you have no idea how many objects you’ll collect in any given session. The classic fixed-size array is not a good choice, as you can’t predict how large an array you’ll need.
The List
class is an array whose size is
dynamically increased as required. Lists
provide a
number of useful methods and properties for their
manipulation. Some of the most important are shown in Table 9-3.
Table 9-3. List methods and properties
Method or property |
Purpose |
---|---|
Property to get or set the number of elements the
| |
Property to get the number of elements currently in the array. | |
Gets or sets the element at the specified index. This is the indexer
for the | |
Public method to add an object to the | |
Public method that adds the elements of an
| |
Overloaded public method that uses a binary search to locate a
specific element in a sorted | |
Removes all elements from the | |
Determines if an element is in the | |
Overloaded public method that copies a | |
Determines if an element is in the | |
Returns the first occurrence of the element in the
| |
Returns all the specified elements in the | |
Overloaded public method that returns an enumerator to iterate
through a | |
Copies a range of elements to a new | |
Overloaded public method that returns the index of the first occurrence of a value. | |
Inserts an element into the | |
Inserts the elements of a collection into the | |
Overloaded public method that returns the index of the last
occurrence of a value in the | |
Removes the first occurrence of a specific object. | |
Removes the element at the specified index. | |
Removes a range of elements. | |
Reverses the order of elements in the | |
Sorts the | |
Copies the elements of the | |
Sets the capacity of the actual number of elements in the
| |
[4] The idiom in
the FCL is to provide an
|
When you create a List
, you don’t
define how many objects it will contain. Add to the
List
using the Add(
)
method, and the list takes care of its own
internal bookkeeping, as illustrated in Example 9-13.
Example 9-13. Working with List
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace ListCollection { // a simple class to store in the List public classEmployee { private int empID; public Employee( int empID ) { this.empID = empID; } public override string ToString( ) { return empID.ToString( ); } public int EmpID { get { return empID; } set { empID = value; } } } public class Tester { static void Main( ) { List<Employee> empList = new List<Employee>( ); List<int> intList = new List<int>( ); // populate the List for ( int i = 0; i < 5; i++ ) { empList.Add( new Employee( i + 100 ) ); intList.Add( i * 5 ); } // print all the contents for ( int i = 0; i < intList.Count; i++ ) { Console.Write( "{0} ", intList[i].ToString( ) ); } Console.WriteLine( " " ); // print all the contents of the Employee List for ( int i = 0; i < empList.Count; i++ ) { Console.Write( "{0} ", empList[i].ToString( ) ); } Console.WriteLine( " " ); Console.WriteLine( "empList.Capacity: {0}", empList.Capacity ); } } } Output: 0 5 10 15 20 100 101 102 103 104 empArray.Capacity: 16
With an Array
class, you define how many objects
the array will hold. If you try to add more than that, the
Array
class will throw an exception. With a
List
, you don’t declare how many
objects the List
will hold. The
List
has a property,
Capacity
,
which is the number of elements the List
is
capable of storing:
public int Capacity { get; set; }
The default capacity is 16. When you add the 17th element, the
capacity is automatically doubled to 32. If you change the
for
loop to:
for (int i = 0;i<17;i++)
the output looks like this:
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 empArray.Capacity: 32
You can manually set the capacity to any number equal to or greater
than the count. If you set it to a number less than the count, the
program will throw an exception of type
ArgumentOutOfRangeException
.
Like all
collections, the
List
implements the Sort( )
method, which allows you to sort any objects that implement
IComparable
. In the next example,
you’ll modify the Employee
object
to implement
IComparable
:
public class Employee : IComparable<Employee>
To implement the IComparable<Employee>
interface, the Employee
object must provide a
CompareTo()
method:
public int CompareTo(Employee rhs) { return this.empID.CompareTo(r.empID); }
The CompareTo( )
method takes an
Employee
as a parameter. We know this is an
Employee
because this is a type-safe collection.
The current Employee
object must compare itself to
the Employee
passed in as a parameter and return
-1
if it is smaller than the parameter,
1
if it is greater than the parameter, and
0
if it is equal to the parameter. It is up to
Employee
to determine what
smaller
than
,
greater
than
, and
equal
to
mean. In this example,
you delegate the comparison to the empId
member.
The empId
member is an int
and
uses the default CompareTo( )
method for integer
types, which will do an integer comparison of the two values.
The System.Int32
class implements
IComparable<Int32>
, so you may delegate the
comparison responsibility to integers.
You are now ready to
sort
the array list of employees, empList
. To see if
the sort is working, you’ll need to add integers and
Employee
instances to their respective arrays with
random values. To create the random values, you’ll
instantiate an object of class Random
; to generate
the random values, you’ll call the
Next( )
method on the Random
object, which returns a
pseudorandom number. The
Next( )
method is overloaded; one version allows
you to pass in an integer that represents the largest random number
you want. In this case, you’ll pass in the value
10
to generate a random number between
0
and 10
:
Random r = new Random(); r.Next(10);
Example 9-14 creates an integer array and an
Employee
array, populates them both with random
numbers, and prints their values. It then sorts both arrays and
prints the new values.
Example 9-14. Sorting an integer and an employee array
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace IComparable { // a simple class to store in the array public classEmployee : IComparable<Employee> { private int empID; public Employee( int empID ) { this.empID = empID; } public override string ToString( ) { return empID.ToString( ); } public bool Equals( Employee other ) { if ( this.empID == other.empID ) { return true; } else { return false; } } // Comparer delegates back to Employee // Employee uses the integer's default // CompareTo method public int CompareTo( Employee rhs ) { return this.empID.CompareTo( rhs.empID ); } } public class Tester { static void Main( ) { List<Employee> empArray = new List<Employee>( ); List<Int32> intArray = new List<Int32>( ); // generate random numbers for // both the integers and the // employee id's Random r = new Random( ); // populate the array for ( int i = 0; i < 5; i++ ) { // add a random employee id empArray.Add( new Employee( r.Next( 10 ) + 100 ) ); // add a random integer intArray.Add( r.Next( 10 ) ); } // display all the contents of the int array for ( int i = 0; i < intArray.Count; i++ ) { Console.Write( "{0} ", intArray[i].ToString( ) ); } Console.WriteLine( " " ); // display all the contents of the Employee array for ( int i = 0; i < empArray.Count; i++ ) { Console.Write( "{0} ", empArray[i].ToString( ) ); } Console.WriteLine( " " ); // sort and display the int array intArray.Sort( ); for ( int i = 0; i < intArray.Count; i++ ) { Console.Write( "{0} ", intArray[i].ToString( ) ); } Console.WriteLine( " " ); // sort and display the employee array Employee.EmployeeComparer c = Employee.GetComparer( ); empArray.Sort(c); empArray.Sort( ); // display all the contents of the Employee array for ( int i = 0; i < empArray.Count; i++ ) { Console.Write( "{0} ", empArray[i].ToString( ) ); } Console.WriteLine( " " ); } } } Output: 4 5 6 5 7 108 100 101 103 103 4 5 5 6 7 100 101 103 103 108
The output shows that the integer array and
Employee
array were generated with random numbers.
When sorted, the display shows the values have been ordered
properly.
When
you call Sort( )
on
the List
, the default implementation of
IComparer
is called, which uses QuickSort
to call the
IComparable
implementation of
CompareTo()
on each element in the
List
.
You are free to create your own implementation of
IComparer
, which you might want to do if you need
control over how the sort ordering is defined. In the next example,
you will add a second field to Employee
,
yearsOfSvc
. You want to be able to sort the
Employee
objects in the List
on
either field, empID
or
yearsOfSvc
.
To accomplish this, create a custom implementation of
IComparer
, which you pass to the
Sort()
method of the List
. This
IComparer
class,
EmployeeComparer
, knows about
Employee
objects and knows how to sort them.
EmployeeComparer
has the
WhichComparison
property, of type
Employee. EmployeeComparer.ComparisonType
:
public Employee.EmployeeComparer.ComparisonType WhichComparison { get{return whichComparison;} set{whichComparison = value;} }
ComparisonType
is an enumeration with two values,
empID
or yearsOfSvc
(indicating
that you want to sort by employee ID or years of service,
respectively):
public enum ComparisonType { EmpID, YearsOfService };
Before invoking Sort( )
, create an instance of
EmployeeComparer
and set its
ComparisionType
property:
Employee.EmployeeComparer c = Employee.GetComparer(); c.WhichComparison=Employee.EmployeeComparer.ComparisonType.EmpID; empArray.Sort(c);
When you invoke Sort( )
, the
List
calls the Compare
method
on the EmployeeComparer
, which in turn delegates
the comparison to the Employee.CompareTo()
method,
passing in its WhichComparison
property:
public int Compare(Employee lhs, Employee rhs ) { return lhs.CompareTo( rhs, WhichComparison ); }
The Employee
object must implement a custom
version of
CompareTo( )
, which takes the comparison and
compares the objects accordingly:
public int CompareTo( Employee rhs, Employee.EmployeeComparer.ComparisonType which) { switch (which) { case Employee.EmployeeComparer.ComparisonType.EmpID: return this.empID.CompareTo(rhs.empID); case Employee.EmployeeComparer.ComparisonType.Yrs: return this.yearsOfSvc.CompareTo(rhs.yearsOfSvc); } return 0; }
The complete source for this example is shown in Example 9-15. The integer array has been removed to
simplify the example, and the output of the
employee’s ToString( )
method has
been enhanced to enable you to see the effects of the sort.
Example 9-15. Sorting an array by employees’ IDs and years of service
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace IComparer { public classEmployee : IComparable<Employee> { private int empID; private int yearsOfSvc = 1; public Employee( int empID ) { this.empID = empID; } public Employee( int empID, int yearsOfSvc ) { this.empID = empID; this.yearsOfSvc = yearsOfSvc; } public override string ToString( ) { return "ID: " + empID.ToString( ) + ". Years of Svc: " + yearsOfSvc.ToString( ); } public bool Equals( Employee other ) { if ( this.empID == other.empID ) { return true; } else { return false; } } // static method to get a Comparer object public static EmployeeComparer GetComparer( ) { return new Employee.EmployeeComparer( ); } // Comparer delegates back to Employee // Employee uses the integer's default // CompareTo method public int CompareTo( Employee rhs ) { return this.empID.CompareTo( rhs.empID ); } // Special implementation to be called by custom comparer public int CompareTo( Employee rhs, Employee.EmployeeComparer.ComparisonType which ) { switch ( which ) { case Employee.EmployeeComparer.ComparisonType.EmpID: return this.empID.CompareTo( rhs.empID ); case Employee.EmployeeComparer.ComparisonType.Yrs: return this.yearsOfSvc.CompareTo( rhs.yearsOfSvc ); } return 0; } // nested class which implements IComparer public class EmployeeComparer : IComparer<Employee> { // private state variable private Employee.EmployeeComparer.ComparisonType whichComparison; // enumeration of comparison types public enum ComparisonType { EmpID, Yrs }; public bool Equals( Employee lhs, Employee rhs ) { return this.Compare( lhs, rhs ) == 0; } public int GetHashCode(Employee e) { return e.GetHashCode( ); } // Tell the Employee objects to compare themselves public int Compare( Employee lhs, Employee rhs ) { return lhs.CompareTo( rhs, WhichComparison ); } public Employee.EmployeeComparer.ComparisonType WhichComparison { get{return whichComparison;} set{whichComparison = value;} } } } public class Tester { static void Main( ) { List<Employee> empArray = new List<Employee>( ); // generate random numbers for // both the integers and the // employee id's Random r = new Random( ); // populate the array for ( int i = 0; i < 5; i++ ) { // add a random employee id empArray.Add( new Employee( r.Next( 10 ) + 100, r.Next( 20 ) ) ); } // display all the contents of the Employee array for ( int i = 0; i < empArray.Count; i++ ) { Console.Write( " {0} ", empArray[i].ToString( ) ); } Console.WriteLine( " " ); // sort and display the employee array Employee.EmployeeComparer c = Employee.GetComparer( ); c.WhichComparison = Employee.EmployeeComparer.ComparisonType.EmpID; empArray.Sort( c ); // display all the contents of the Employee array for ( int i = 0; i < empArray.Count; i++ ) { Console.Write( " {0} ", empArray[i].ToString( ) ); } Console.WriteLine( " " ); c.WhichComparison = Employee.EmployeeComparer.ComparisonType.Yrs; empArray.Sort( c ); for ( int i = 0; i < empArray.Count; i++ ) { Console.Write( " {0} ", empArray[i].ToString( ) ); } Console.WriteLine( " " ); } } } Output: ID: 103. Years of Svc: 11 ID: 108. Years of Svc: 15 ID: 107. Years of Svc: 14 ID: 108. Years of Svc: 5 ID: 102. Years of Svc: 0 ID: 102. Years of Svc: 0 ID: 103. Years of Svc: 11 ID: 107. Years of Svc: 14 ID: 108. Years of Svc: 15 ID: 108. Years of Svc: 5 ID: 102. Years of Svc: 0 ID: 108. Years of Svc: 5 ID: 103. Years of Svc: 11 ID: 107. Years of Svc: 14 ID: 108. Years of Svc: 15
The first block of output shows the
Employee
objects as they are added to the
List
. The employee ID values and the years of
service are in random order. The second block shows the results of
sorting by the employee ID, and the third block shows the results of
sorting by years of service.
If you are
creating
your own collection, as in Example 9-11, and wish to
implement IComparer
, you may need to ensure that
all the types placed in the list implement
IComparer
(so that they may be sorted), by using
constraints as described earlier.
A queue represents a first-in, first-out (FIFO) collection. The classic analogy is to a line (or queue if you are British) at a ticket window. The first person in line ought to be the first person to come off the line to buy a ticket.
A queue is a good collection to use when you are managing a limited resource. For example, you might want to send messages to a resource that can handle only one message at a time. You would then create a message queue so that you can say to your clients: “Your message is important to us. Messages are handled in the order in which they are received.”
The
Queue
class has
a number of member methods and properties, as shown in Table 9-4.
Table 9-4. Queue methods and properties
Method or property |
Purpose |
---|---|
Public property that gets the number of elements in the
| |
Removes all objects from the | |
Determines if an element is in the | |
Copies the | |
Removes and returns the object at the beginning of the
| |
Adds an object to the end of the | |
Returns an enumerator for the | |
Returns the object at the beginning of the | |
Copies the elements to a new array. |
Add
elements to your queue with the Enqueue
command
and take them off the queue with Dequeue
or by
using an enumerator. Example 9-16 illustrates.
Example 9-16. Working with a queue
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace Queue { public classTester { static void Main( ) { Queue<Int32> intQueue = new Queue<Int32>( ); // populate the array for ( int i = 0; i < 5; i++ ) { intQueue.Enqueue( i * 5 ); } // Display the Queue. Console.Write( "intQueue values: " ); PrintValues( intQueue ); // Remove an element from the queue. Console.WriteLine( " (Dequeue) {0}", intQueuee.Dequeue( ) ); // Display the Queue. Console.Write( "intQueue values: " ); PrintValues( intQueue ); // Remove another element from the queue. Console.WriteLine( " (Dequeue) {0}", intQueuee.Dequeue( ) ); // Display the Queue. Console.Write( "intQueue values: " ); PrintValues( intQueue ); // View the first element in the // Queue but do not remove. Console.WriteLine( " (Peek) {0}", intQueuee.Peek( ) ); // Display the Queue. Console.Write( "intQueue values: " ); PrintValues( intQueue ); } public static void PrintValues(IEnumerable<Int32> myCollection) { IEnumerator<Int32> myEnumerator = myCollection.GetEnumerator( ); while ( myEnumerator.MoveNext( ) ) Console.Write( "{0} ", myEnumerator.Current ); Console.WriteLine( ); } } } Output: intQueue values: 0 5 10 15 20 (Dequeue) 0 intQueuee values: 5 10 15 20 (Dequeue) 5 intQueue values: 10 15 20 (Peek) 10 intQueue values: 10 15 20
In this example the List
is replaced by a
Queue
. I’ve dispensed with the
Employee
class to save room, but of course you can
Enqueue
user-defined objects as well.
The output shows that queuing objects adds them to the
Queue
, and calls to Dequeue
return the object and also remove them from the
Queue
. The Queue
class also
provides a Peek()
method that allows you to see,
but not remove, the first element.
Because the Queue
class is enumerable, you can
pass it to the
PrintValues
method, which is provided as an
IEnumerable
interface. The conversion is
implicit. In the PrintValues
method you call
GetEnumerator
, which you will remember is the
single method of all IEnumerable
classes. This
returns an
IEnumerator
, which you then use to enumerate all
the objects in the collection.
A stack is a last-in, first-out (LIFO) collection, like a stack of dishes at a buffet table, or a stack of coins on your desk. A dish added on top is the first dish you take off the stack.
The principal methods for adding to and removing from a stack are
Push()
and Pop()
;
Stack
also offers a Peek()
method, very much like Queue
. The significant
methods and properties for
Stack
are
shown in Table 9-5.
Table 9-5. Stack methods and properties
Method or property |
Purpose |
---|---|
Public property that gets the number of elements in the
| |
Removes all objects from the | |
Creates a shallow copy. | |
Determines if an element is in the | |
Copies the | |
Returns an enumerator for the | |
Returns the object at the top of the | |
Removes and returns the object at the top of the
| |
Inserts an object at the top of the | |
Copies the elements to a new array. |
The List
, Queue
, and
Stack
types contain overloaded
CopyTo( )
and ToArray( )
methods
for copying their elements to an array. In the case of a
Stack
, the CopyTo( )
method will
copy its elements to an existing one-dimensional array, overwriting
the contents of the array beginning at the index you specify. The
ToArray( )
method returns a new array with the
contents
of the stack’s elements. Example 9-17 illustrates.
Example 9-17. Working with a stack
#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace Stack { public classTester { static void Main( ) { Stack<Int32> intStack = new Stack<Int32>( ); // populate the array for ( int i = 0; i < 8; i++ ) { intStack.Push( i * 5 ); } // Display the Stack. Console.Write( "intStack values: " ); PrintValues( intStack ); // Remove an element from the stack. Console.WriteLine( " (Pop) {0}", intStack.Pop( ) ); // Display the Stack. Console.Write( "intStack values: " ); PrintValues( intStack ); // Remove another element from the stack. Console.WriteLine( " (Pop) {0}", intStack.Pop( ) ); // Display the Stack. Console.Write( "intStack values: " ); PrintValues( intStack ); // View the first element in the // Stack but do not remove. Console.WriteLine( " (Peek) {0}", intStack.Peek( ) ); // Display the Stack. Console.Write( "intStack values: " ); PrintValues( intStack ); // declare an array object which will // hold 12 integers int[] targetArray = new int[12]; for (int i = 0; i < targetArray.Length; i++) { targetArray[i] = i * 100 + 100; } // Display the values of the target Array instance.Console
.WriteLine( " Target array: " ); PrintValues( targetArray ); // Copy the entire source Stack to the // target Array instance, starting at index 6. intStack.CopyTo( targetArray, 6 ); // Display the values of the target Array instance.Console.
WriteLine( " Target array after copy: " ); PrintValues( targetArray ); } public static void PrintValues( IEnumerable<Int32> myCollection ) { IEnumerator<Int32> enumerator = myCollection.GetEnumerator( ); while ( enumerator.MoveNext( ) ) Console.Write( "{0} ", enumerator.Current ); Console.WriteLine( ); } } } Output: intStack values: 35 30 25 20 15 10 5 0 (Pop) 35 intStack values: 30 25 20 15 10 5 0 (Pop) 30 intStack values: 25 20 15 10 5 0 (Peek) 25 intStack values: 25 20 15 10 5 0 Target array: 100 200 300 400 500 600 700 800 900 0 0 0 Target array after copy: 100 200 300 400 500 600 25 20 15 10 5 0 The new array: 25 20 15 10 5 0
The output reflects that the items pushed onto the stack were popped in reverse order.
The effect of CopyTo()
can be
seen by examining the target array before and after calling
CopyTo( )
. The array elements are overwritten
beginning with the index specified (6
).
A dictionary is a collection that associates a key to a value. A language dictionary, such as Webster’s, associates a word (the key) with its definition (the value).
To see the value of dictionaries, start by imagining that you want to keep a list of the state capitals. One approach might be to put them in an array:
string[] stateCapitals = new string[50];
The stateCapitals
array will hold 50 state
capitals. Each capital is accessed as an offset into the array. For
example, to access the capital for Arkansas, you need to know that
Arkansas is the fourth state in alphabetical order:
string capitalOfArkansas = stateCapitals[3];
It is inconvenient, however, to access state capitals using array notation. After all, if I need the capital for Massachusetts, there is no easy way for me to determine that Massachusetts is the 21st state alphabetically.
It would be far more convenient to store the capital with the state name. A dictionary allows you to store a value (in this case, the capital) with a key (in this case, the name of the state).
A .NET Framework dictionary can associate any kind of key (string, integer, object, etc.) with any kind of value (string, integer, object, etc.). Typically, of course, the key is fairly short, the value fairly complex.
The most important attributes of a good dictionary are that it is easy to add and quick to retrieve values (see Table 9-6).
Table 9-6. Dictionary methods and properties
The key in a Dictionary
can be a primitive type,
or it can be an instance of a user-defined type (an object). Objects
used as keys for a Dictionary
must implement
GetHashCode()
as well as
Equals
. In most cases, you can simply use
the inherited implementation from Object
.
Dictionaries implement the
IDictionary<K,V>
interface (where K
is the key type and
V
is the value type).
IDictionary
provides a public property
Item
. The Item
property
retrieves a value with the specified key. In C#, the declaration for
the Item
property is:
V[Kkey
]
{get; set;}
The Item
property is implemented in C# with the
index operator ([]
). Thus, you access items in any
Dictionary
object using the offset syntax, as you
would with an array.
Example 9-18 demonstrates adding items to a
Dictionary
and then retrieving them with the
Item
property.
Example 9-18. The Item property as offset operators
namespace Dictionary { public classTester { static void Main( ) { // Create and initialize a new Dictionary. Dictionary<string,string> Dictionary = new Dictionary<string,string>( ); Dictionary.Add("000440312", "Jesse Liberty"); Dictionary.Add("000123933", "Stacey Liberty"); Dictionary.Add("000145938", "John Galt"); Dictionary.Add("000773394", "Ayn Rand"); // access a particular item Console.WriteLine("myDictionary["000145938"]: {0}", Dictionary["000145938"]); } } } Output: Dictionary["000145938"]: John Galt
Example 9-18 begins by instantiating a new
Dictionary
. The type of the key and of the value
is declared to be string
.
Add four key/value pairs. In this example, the Social Security number is tied to the person’s full name. (Note that the Social Security numbers here are intentionally bogus.)
Once the items are added, you access a specific entry in the dictionary using the Social Security number as key.
If you use a reference type as a key, and the type is mutable (strings are immutable), you must not change the value of the key object once you are using it in a dictionary.
If, for example, you use the Employee
object as a
key, changing the employee ID creates problems if that property is
used by the Equals
or
GetHashCode
methods because the dictionary
consults these methods.
[1] Of course, when you create an array with
int[]
myArray
=
new
int[5]
what you actually create in the IL code is an instance of
System.int32[]
, but since this derives from the
abstract base class System.Array
, it is fair to
say you’ve created an instance of a
System.Array
.
[2] The actual ListBox
control
provided by both Windows Forms and ASP.NET has a collection called
Items
, and it is the Items
collection that implements the indexer.
[3] For backward compatibility,
C# also provides nongeneric interfaces (e.g.,
ICollection
, IEnumerator
), but
they aren’t considered here because they are
obsolescent.
13.59.173.242