|
Dr. Dobb's Journal October 2000
While C++ developers enjoy full control over how their programs execute, this power comes at a price. What C++ developer hasn't spent hours tracking down a memory leak, or wasted time puzzling over the effects of a stray pointer? Visual Basic developers, on the other hand, have benefited from higher productivity due to automatic memory management, close fit with the platform, and the wide availability of ActiveX components. But what VB developer hasn't at some point wanted more low-level control, or found it difficult or impossible to call a COM interface because of a data type problem?
Given that C++ developers have power but want higher productivity, and VB developers have higher productivity but often seek more power, it is natural for both sets of developers to wish for a language that delivers the best of C++ and VB -- productivity by default and power on demand. This is the void that C# aims to fill.
C# (pronounced "C sharp") is part of Microsoft Visual Studio 7.0. (For details about C#, including release dates, see http://msdn.microsoft.com/vstudio/nextgen.) In addition to C#, Visual Studio supports Visual Basic, Visual C++, and the scripting languages VBScript and JScript. All of these languages provide access to the Microsoft .NET platform, which includes a common execution engine and class library.
The Microsoft .NET platform defines a Common Language Subset (CLS), as a sort of lingua franca that ensures seamless interoperability between CLS-compliant languages and class libraries. This means that C# developers have complete access to the same class libraries as are available with tools such as Visual Basic and Visual C++. In this article, I'll examine the C# language by implementing a Stack class, whose fundamental operations are:
This example is straightforward enough that its details won't distract you from the language description, yet complex enough that it meaningfully demonstrates important aspects of the language.
I'll start by declaring an empty Stack class (see Listing One) and writing an associated test program. Close examination of this program is illuminating:
For C and C++ developers, it is interesting to note a few things that do not appear in the "Hello, world" program.
A field is a member that represents a variable associated with an object or class. I'll use two fields to store the elements of the stack: an array that holds the elements and a size that holds the number of items in the stack. When a Stack instance is created, these variables are initialized. Example 1 shows one way of doing this. The size field is initialized to 0, since a Stack is initially empty. The values field is initialized to an array of type object[] that has 10 elements. Each element of this array is automatically initialized to null.
The use of an array of objects to store the elements of the stack raises an important issue: What sorts of items can be pushed onto the stack? To answer this question, you need to examine the two kinds of types that C# supports -- value types and reference types. Value types include simple types (char, int, and float, for example), enum types, and struct types. Reference types include class types, interface types, delegate types, and array types.
Value types differ from reference types in that variables of the value types directly contain their data, whereas variables of the reference types store references to objects. With reference types, it is possible for two variables to reference the same object, and thus possible for operations on one variable to affect the object referenced by the other variable. With value types, the variables each have their own copy of the data, and it is not possible for operations on one to affect the other. In the stack example, I use a field of a value type (int) and a field of a reference type (object[]).
The keywords int and object are examples of predefined types. Some predefined types are reference types, and some are value types. The predefined reference types are object and string. The type object is the ultimate base type of all other types, and the type string is used to represent Unicode string values. The predefined value types include signed and unsigned integral types, floating-point types, and the types bool, char, and decimal. The signed integral types are sbyte, short, int, and long; the unsigned integral types are byte, ushort, uint, and ulong; and the floating-point types are float and double.
C# provides a "unified type system." All types -- including value types -- derive from the type object. Example 2 shows that an int value can be converted to object and back again to int. These conversions are called "boxing" and "unboxing," respectively. When a variable of a value type needs to be converted to a reference type, an object box is allocated to hold the value, and the value is copied into the box. Unboxing is just the opposite. When an object box is cast back to its original value type, the value is copied out of the box and into the appropriate storage location. Type system unification provides value types with the benefits of object-ness without introducing unnecessary overhead. For programs that don't need int values to act like objects, int values are simply 32-bit values. For programs that need int values to behave like objects, this capability is available on-demand. This ability to treat value types as objects bridges the gap between value types and reference types that exists in most languages. Type system unification is important for our stack example, as it enables Stack to store elements of any type, including value types like int.
At this point, I'll add support for the fundamental stack operations -- the Push method, Pop method, and Count property. In addition, I'll add two overloaded ToString methods: one that takes no parameters and is an override of a method introduced in object, and a second that takes a string delimiter.
To push an item onto the stack, you place it in the values array and increment size. To pop an item off of the stack, you extract the value from the values array, decrement size, and return the value. Error cases -- either pushing onto a full stack or popping from an empty stack -- cause exceptions to be thrown. Listing Two implements the new Stack. The test program in Listing Three creates a stack, pushes the numbers 1 through 5 onto it, and then pops them off.
Example 3 deserves further comment, because it shows some of the string formatting behavior of Console.WriteLine, which takes a variable number of arguments. The first argument is a string, which may contain numbered placeholders like {0} and {1}. Each placeholder refers to a trailing argument. The placeholder {0} refers to the second argument, the placeholder {1} refers to the third argument, and so on. Before the output is sent to the console, each placeholder is replaced with the string representation of its corresponding argument.
The output of this test program is:
Stack s = 5,4,3,2,1
Popped 5
Popped 4
Popped 3
Popped 2
Popped 1
Stack s =
Just looking at this small example, you can examine a number of important language features, including:
A method is a member that implements a computation or action that can be performed by an object or class. Methods have a list of formal parameters (which may be empty), a return value (or void), and are either static or nonstatic. Static methods are accessed through the class. Nonstatic methods, which are also called "instance methods," are accessed through instances of the class. Instance methods are either virtual or nonvirtual, and nonvirtual is the default. In the example, the methods Push and Pop are both virtual, and so could be overridden by a derived class.
Methods can be overloaded, which means that multiple methods may have the same name as long as they have unique signatures. The signature of a method consists of the name of the method and the number, modifiers, and types of its formal parameters. The signature of a method specifically does not include the return type.
The ToString methods provided by Stack are good examples of both overloading and overriding. The ToString method that takes no arguments is an override of a method provided by object. Overriding methods must include the override keyword. This helps eliminate programming errors (for instance, mistyping the formal parameters and accidentally introducing a new member rather than overriding an existing one), but more importantly, it allows for better versioning behavior.
Versioning is the process of evolving a component over time in a compatible manner. A new version of a component is source compatible with a previous version if code that depends on the previous version can, when recompiled, work with the new version. In contrast, a new version of a component is binary compatible if a program that depends on the old version can, without recompilation, work with the new version. C# supports both forms of compatibility, and includes language features that facilitate versioning.
One common versioning problem that occurs in C++ and some other object-oriented languages is "accidental overriding," in which a derived class introduces a new method, and a subsequent version of its base class introduces a virtual method with the same signature. This causes the derived class to accidentally override the base method. This is almost always an error, but is not caught in most languages. In C#, such a situation causes a compile-time warning. This warning lets you clearly specify the intent -- whether the method should override the base method or hide it.
A property is in some ways a combination of fields and methods. A property provides access to an attribute of an object or a class. Properties are like fields in that they are named members with associated types, and the syntax for accessing fields and properties is the same. However, unlike fields, properties do not denote storage locations. Instead, properties have accessors that specify the statements to execute to read/write their values. In this way, properties are like methods.
Properties are defined with property declarations. The first part of a property declaration resembles a field declaration. The second part includes a get accessor and/or a set accessor. Stack's Count property is simple: it returns the value of the private size field.
public virtual int Count {
get { return size; }
}
There are several important benefits of using a property rather than exposing size directly. First, using a property lets you limit access -- you want client code to be able to find out the number of elements in the stack, but don't want client code to be able to change the number of elements except by pushing and popping elements. Second, using a property provides encapsulation and abstraction. You could change the implementation -- perhaps by using linked lists rather than arrays -- without disturbing client code.
Each member of a class has an associated accessibility, which controls the regions of program text that are able to access the member. There are five possible forms of accessibility: public, protected, internal, protected internal, and private.
The Stack example shows the two extremes: public and private. For members like size and values that have private accessibility, access is limited to the class in which they are declared. Members that have public accessibility are accessible to any code. The use of private accessibility for the size and values fields lets you hide the implementation details of Stack from consumers.
For protected members, access is limited to the containing class or types derived from the containing class. For internal members, access is limited to the containing program. It should be no surprise that the protected internal form of accessibility is a combination of protected and internal. Members that are protected internal can be accessed from types derived from the containing class (that's the "protected" part) and from the containing program (that's the "internal" part). Listing Four provides the complete source code for Step 3.
The stack as implemented to this point has a severe limitation -- it can hold only 10 elements. To implement variable capacity, I'll do the following:
These Stack features will let you examine some interesting language features -- constants, constructors, and read/write properties. After I've implemented these features, you'll be able to run the test program in Listing Five, which produces the output:
10
2
100
Count=15, Capacity=20, Elements=15,14,13,12,11,10,9,8,7,6,5,4,3,2,1
A constant is a class member that represents a constant value: a value that can be computed at compile time. Constants are implicitly static, and can be accessed through the class in which they are declared.
The initial stack had a default capacity of 10. For the new variable capacity stack, I'll define a constant for this default capacity. The use of a constant rather than a "magic number" makes the code easier to read and modify.
I'll call the constant DefaultCapacity. As Example 4 shows, both declaration and use of this member are straightforward.
An instance constructor is a member that implements the actions required to initialize an instance of a class. If no constructor is supplied for a class, then a public constructor with no parameters is automatically provided.
Stack, as currently implemented, does not contain a constructor declaration, and instead relies on the compiler to supply one automatically. The code in Example 5(a) omits a constructor, and is equivalent to Example 5(b), which includes an explicit constructor.
The first action taken by any constructor -- except the parameterless constructor for the class object -- is to call another constructor, whether in the same class or in the base class. Calls to constructors in the same class can be made using the this keyword, and calls to base constructors can be made using the base keyword. If neither this nor base constructor calls are included, then a base() call is automatically included.
Like methods, constructors can be overloaded. This comes in handy for the new and improved stack, as you need two constructors: one that takes no parameters, and one that takes a suggested capacity from the client; see Listing Six. Note that the parameterless constructor calls the other constructor, passing DefaultCapacity as a suggested capacity.
Next, I'll expose the capacity of the stack -- the number of elements it can hold without performing a time-consuming reallocation -- by providing a read/write property named Capacity. To create a read/write property, you write a property that includes both a get accessor and set accessor.
A set accessor for a property has an implicit parameter named value that contains the proposed new value of the property. The setter for the Capacity property checks to make sure that the capacity is valid, and then resizes the stack by creating a new array and copying the stack's elements into it; see Listing Seven.
To complete the variable capacity stack, I'll modify the behavior of the Push method. The fixed-size stack threw an exception when there was no room for the item being pushed. Now that a variable capacity has been implemented, you can automatically grow the stack rather than throw an exception. To do this, set the Capacity property, as in Example 6. Listing Eight presents the complete code for Step 4.
C# supports iteration using a convenient foreach construct. I'll add support for this form of iteration, and in the process touch on a number of language features. Once I've completed these modifications, you'll be able to run the test program in Listing Nine, which initializes a stack and then uses foreach to iterate over its elements.
To implement this support, I'll make the following changes:
These Stack features will lead you to examine more interesting language features: events, delegates, interfaces, foreach, and nested classes.
The stack, as it is implemented so far, includes constructors, constants, fields, methods, and properties. Next, I'm going to add an event. As you'll see, the event I'm adding will be useful in implementing the enumerator for the stack.
An event is a member that enables an object or class to provide notifications. A class defines an event by providing an event declaration, which resembles a field declaration, though with an added event keyword. The type of this declaration must be a delegate type.
Delegates enable scenarios that C++ and some other languages have addressed with function pointers. Unlike function pointers, delegates are object oriented, type safe, and secure. Delegates are reference types that derive from a common base class: System.Delegate. A delegate instance encapsulates a method -- a callable entity -- which is specified when the delegate is instantiated. The callable entity can either consist of an instance and a method on the instance, or a class and a static method on the class. After the delegate is created, it can be called using normal method call syntax. Listing Ten declares a delegate that takes no parameters and returns void. The Main method creates an instance of this delegate type and calls it. This example shows the three main steps in using a delegate: declaring the delegate type, creating a delegate instance, and calling the delegate.
Now I'll apply the new add delegate knowledge by adding an event named Changed, and raise this event whenever the stack changes -- when items are pushed and popped. To add this event, I'll declare two members: an event named Changed and a protected method named OnChanged which raises the event. The OnChanged method serves several purposes. First, it centralizes the steps involved in raising the event. This is important because you will need to raise the event from several different methods. Second, it enables derived classes to customize the behavior of the event.
Events can have state associated with them. The Changed event has no interesting state, so I'll use the base EventHandler/EventArgs provided by the .NET class library. The type of the Changed event is EventHandler; see Listing Eleven. Next, I'll alter Push and Pop so that they raise the Changed event by calling the OnChanged method; see Listing Twelve.
To test the Changed event, the test program in Listing Thirteen creates a Stack, connects an event handler to it, and then modifies the stack.
C#'s foreach support is implemented using two interfaces: IEnumerable and IEnumerator. The IEnumerable interface is used to obtain an "enumerator" for a collection -- an object that implements IEnumerator.
An interface defines a contract by specifying the members that must be implemented, and the semantics of these members. A class or struct that implements an interface must adhere to its contract. Listing Fourteen presents the declarations of IEnumerable and IEnumerator.
The best way to describe the semantics of foreach-style iteration is to provide two examples. Example 7(a) shows foreach-style iteration over a collection, while Example 7(b) shows the equivalent "by hand" iteration, using the IEnumerable and IEnumerator interfaces. As you can see, IEnumerable is used to obtain an enumerator -- an object that implements IEnumerator. The iteration is done by calling the MoveNext method and accessing the Current property.
A nested class is a class that is lexically nested in another class. Like other class members, a nested class has an associated accessibility. I'll use a nested class for Stack's enumerator, and give this class private accessibility. It is appropriate to use a private nested class because the only way you want any code to access the enumerator is through the GetEnumerator method on Stack.
To expose the enumerator, you need to implement the IEnumerator interface on Stack. To do this, you add a "base list" to the declaration of Stack. The base list for a class declaration is a comma-separated list that includes a base class, a list of interfaces, or both. You can now sketch out the enumerator implementation (see Listing Fifteen) and get on to do the real work -- implement Enumerator. The enumerator class maintains the following pieces of state:
Enumerator does not make a copy of the stack elements. Instead, it keeps a reference to the underlying stack and invalidates itself when this underlying stack changes. Listing Sixteen presents the complete code for Step 5.
In implementing a simple stack, I've described quite a bit of the language: namespaces, classes, a variety of class members (constants, constructors, events, fields, methods, and properties), member accessibility, delegates, overloading, overriding, versioning, exceptions, interfaces, and foreach-style iteration.
More important, though, you've gained some insight into the design philosophy that underlies the language. C# adheres close to its C++ heritage in many areas, and both simplifies and modernizes it in others. The result is a language that enhances your productivity without taking away your power and control.
DDJ
using System;
class Stack
{
}
class Test
{
public static void Main() {
Stack s = new Stack();
Console.WriteLine("Done");
}
}
using System;
class Stack
{
private int size = 0;
private object[] values = new object[10];
public virtual int Count {
get { return size; }
}
public virtual object Pop() {
if (size == 0)
throw new InvalidOperationException();
else {
object ans = values[--size];
values[size] = null;
return ans;
}
}
public virtual void Push(object o) {
if (size == values.Length)
throw new InvalidOperationException();
values[size++] = o;
}
public override string ToString() {
return ToString(",");
}
public virtual string ToString(string delimiter) {
switch (size) {
case 0:
return "";
case 1:
return values[0].ToString();
default:
string ans = "";
for (int i = size-1; i > 0; i--)
ans += values[i].ToString() + delimiter;
ans += values[0];
return ans;
}
}
}
using System;
class Test
{
static void Main() {
Stack s = new Stack();
for (int i = 1; i <= 5; i++) {
s.Push(i);
}
Console.WriteLine("Stack s = {0}", s);
while (s.Count > 0)
Console.WriteLine("Popped {0}", s.Pop());
Console.WriteLine("Stack s = {0}", s);
}
}
using System;
class Stack
{
private int size = 0;
private object[] values = new object[10];
public virtual int Count {
get { return size; }
}
public virtual object Pop() {
if (size == 0)
throw new InvalidOperationException();
else {
object ans = values[--size];
values[size] = null;
return ans;
}
}
public virtual void Push(object o) {
if (size == values.Length)
throw new InvalidOperationException();
values[size++] = o;
}
public override string ToString() {
return ToString(",");
}
public virtual string ToString(string delimiter) {
switch (size) {
case 0:
return "";
case 1:
return values[0].ToString();
default:
string ans = "";
for (int i = size-1; i > 0; i--)
ans += values[i].ToString() + delimiter;
ans += values[0];
return ans;
}
}
}
class Test
{
static void Main() {
Stack s = new Stack();
for (int i = 1; i <= 5; i++) {
s.Push(i);
}
Console.WriteLine("Stack s = {0}", s);
while (s.Count > 0)
Console.WriteLine("Popped {0}", s.Pop());
Console.WriteLine("Stack s = {0}", s);
}
}
using System;
class Test
{
static void Main() {
Stack a = new Stack();
Console.WriteLine(a.Capacity);
Stack b = new Stack(2);
Console.WriteLine(b.Capacity);
Stack c = new Stack(100);
Console.WriteLine(c.Capacity);
for (int i = 1; i <= 15; i++)
a.Push(i);
Console.WriteLine("Count={0}, Capacity={1}, Elements={2}",
a.Count,
a.Capacity,
a.ToString());
}
}
using System;
class Stack
{
private int size;
private object[] values;
public Stack(): this(DefaultCapacity) {}
public Stack(int capacity) {
if (capacity <= 0)
throw new ArgumentOutOfRangeException();
values = new object[capacity];
size = 0;
}
public const int DefaultCapacity = 10;
...
}
class Test
{
static void Main() {
Stack a = new Stack();
Stack b = new Stack(10);
Stack c = new Stack(100);
}
}
class Stack
{
...
public virtual int Capacity {
get {
return values.Length;
}
set {
if ((value <= size) || (value <= 0))
throw new ArgumentOutOfRangeException();
object[] newValues = new object[value];
Array.Copy(values, 0, newValues, 0, size);
values = newValues;
}
}
...
}
using System;
class Stack
{
private int size;
private object[] values;
public Stack(): this(DefaultCapacity) {}
public Stack(int capacity) {
if (capacity <= 0)
throw new ArgumentOutOfRangeException();
values = new object[capacity];
size = 0;
}
public virtual int Capacity {
get {
return values.Length;
}
set {
if ((value <= size) || (value <= 0))
throw new ArgumentOutOfRangeException();
object[] newValues = new object[value];
Array.Copy(values, 0, newValues, 0, size);
values = newValues;
}
}
public virtual int Count {
get { return size; }
}
public const int DefaultCapacity = 10;
public virtual object Pop() {
if (size == 0)
throw new InvalidOperationException();
else {
object ans = values[--size];
values[size] = null;
return ans;
}
}
public virtual void Push(object o) {
if (size == values.Length)
Capacity = size * 2;
values[size++] = o;
}
public override string ToString() {
return ToString(",");
}
public virtual string ToString(string delimiter) {
switch (size) {
case 0:
return "";
case 1:
return values[0].ToString();
default:
string ans = "";
for (int i = size-1; i > 0; i--)
ans += values[i].ToString() + delimiter;
ans += values[0];
return ans;
}
}
}
class Test
{
static void Main() {
Stack a = new Stack();
Console.WriteLine(a.Capacity);
Stack b = new Stack(2);
Console.WriteLine(b.Capacity);
Stack c = new Stack(100);
Console.WriteLine(c.Capacity);
for (int i = 1; i <= 15; i++)
a.Push(i);
Console.WriteLine("Count={0}, Capacity={1}, Elements={2}",
a.Count,
a.Capacity,
a.ToString());
}
}
class Test
{
static void Main() {
Stack s = new Stack();
for (int i = 1; i < 10; i++)
s.Push(i);
foreach (int i in s)
Console.WriteLine(i);
}
}
using System;
delegate void EmptyDelegate();
class Test
{
static void F() {
Console.WriteLine("F");
}
static void Main() {
EmptyDelegate d = new EmptyDelegate(F);
d();
}
}
using System;
class Stack
{
...
public event EventHandler Changed;
protected virtual void OnChanged(EventArgs e) {
if (Changed != null)
Changed(this, e);
}
...
}
public virtual object Pop() {
if (size == 0)
throw new InvalidOperationException();
else {
object ans = values[--size];
values[size] = null;
OnChanged(EventArgs.Empty);
return ans;
}
}
public virtual void Push(object o) {
if (size == values.Length)
Capacity = size * 2;
values[size++] = o;
OnChanged(EventArgs.Empty);
}
using System;
class Test
{
static void Stack_Changed(object sender, EventArgs e) {
Console.WriteLine("The stack changed: {0}", sender);
}
static void Main() {
Stack s = new Stack();
s.Changed += new EventHandler(Stack_Changed);
for (int i = 1; i <= 10; i++)
s.Push(i);
while (s.Count >= 0)
s.Pop();
}
}
namespace System.Collections
{
public interface IEnumerable
{
IEnumerator GetEnumerator();
}
public interface IEnumerator
{
object Current { get; }
bool MoveNext();
void Reset();
}
}
using System;
using System.Collections;
class Stack: IEnumerable
{
public virtual IEnumerator GetEnumerator() {
return new Enumerator(this);
}
private class Enumerator: IEnumerator
{
public Enumerator(Stack stack) {...}
public virtual object Current { get {...} }
public virtual bool MoveNext() {...}
public virtual void Reset() {...}
}
...
}
using System;
using System.Collections;
class Stack: IEnumerable
{
private int size;
private object[] values;
public Stack(): this(DefaultCapacity) {}
public Stack(int capacity) {
if (capacity <= 0)
throw new ArgumentOutOfRangeException();
values = new object[capacity];
size = 0;
}
public virtual int Capacity {
get {
return values.Length;
}
set {
if ((value <= size) || (value <= 0))
throw new ArgumentOutOfRangeException();
object[] newValues = new object[value];
Array.Copy(values, 0, newValues, 0, size);
values = newValues;
}
}
public event EventHandler Changed;
public virtual int Count {
get { return size; }
}
public const int DefaultCapacity = 10;
private class Enumerator: IEnumerator
{
private int currIndex;
private bool dirty;
private Stack stack;
private void Stack_Changed(object sender, EventArgs e) {
dirty = true;
stack = null;
}
public Enumerator(Stack stack) {
this.stack = stack;
stack.Changed += new EventHandler(Stack_Changed);
dirty = false;
Reset();
}
public virtual object Current {
get {
ThrowIfDirty();
if ((currIndex == stack.size) || (currIndex == -1))
throw new InvalidOperationException();
return stack.values[currIndex];
}
}
public virtual bool MoveNext() {
ThrowIfDirty();
if (currIndex == -1)
return false;
return --currIndex >= 0;
}
public virtual void Reset() {
ThrowIfDirty();
currIndex = stack.size;
}
private void ThrowIfDirty() {
if (dirty)
throw new InvalidOperationException();
}
}
public virtual IEnumerator GetEnumerator() {
return new Enumerator(this);
}
protected virtual void OnChanged(EventArgs e) {
if (Changed != null)
Changed(this, e);
}
public virtual object Pop() {
if (size == 0)
throw new InvalidOperationException();
else {
object ans = values[--size];
values[size] = null;
OnChanged(EventArgs.Empty);
return ans;
}
}
public virtual void Push(object o) {
if (size == values.Length)
Capacity = size * 2;
values[size++] = o;
OnChanged(EventArgs.Empty);
}
public override string ToString() {
return ToString(",");
}
public virtual string ToString(string delimiter) {
switch (size) {
case 0:
return "";
case 1:
return values[0].ToString();
default:
string ans = "";
for (int i = size-1; i > 0; i--)
ans += values[i].ToString() + delimiter;
ans += values[0];
return ans;
}
}
}
class Test
{
static void Main() {
Stack s = new Stack();
for (int i = 1; i < 10; i++)
s.Push(i);
foreach (int i in s)
Console.WriteLine(i);
}
}
| Copyright © 2003 Dr. Dobb's Journal, Privacy Policy.
Comments about the web site: webmaster@ddj.com |