Through the 1960s, and into the early 1970s, operating systems were written in assembler language. The C programming language was originally developed as a language to replace assembler in systems programming. It was very successful, making system code portable and easier to write and read.

C began to grow in popularity not just for systems programming, but as a general purpose programming language. Today C is one of the most used programming languages. The C programmer must realize, however, that C was designed to replace assembler language, and that in several important ways, it retains a very low level view of the machine. This language summary will discuss, among other things. some of the low level characteristics of C.

The C++ programming language was designed as a higher level version of C, providing support for object-oriented programming. Some features of C++ are discussed in this summary, and some are discussed under classes, later. C++ retains almost all of C, however, and therefore is a mixture of low level and high level features. Often, the programmer has a choice of using low level or high level approaches.

C and C++ are both case sensitive. That means that B and b are two different letters. If you write

int x;

you have declared a variable x of type int. If you write

Int x;

you probably get a compile error, since there is no type Int.

C is free-form. That is, in most contexts the end of a line is just like a space. So there is no special meaning to a line. Typically, you put one statement per line, because it looks nicer than packing several to a line, or breaking a statement into several lines. Long statements are usually placed on several lines, however.

You can write comments in either C style or C++ style (in C++ programs). A C style comment begins with /* and ends with */. A C++ style comments begins with // and ends at the end of a line. (So C++ comments are one of the few violations of free-formness.) For example,

You can name things in C/C++ with names that begin with a letter or underscore, and contain letters, underscores and digits in any combination. For example,

are all names that can be given to things. Names cannot contain spaces. You should avoid names that begin with an underscore, since they are often used to name special things in the system.

Certain words are special in the language, and you cannot use them to name things. These reserved words are shown in bold face in programs in this summary.

A computer's memory stores programs and data. The usual model of a memory is as a mapping from integer addresses to values. You give the memory an address, and it gives you the value stored at that address. Here is a view of a memory.

Address Value (for example)

0 20

1 46

2 -5

3 0

... ...

Typically, each memory address holds one byte, which can hold a number from -128 to 127. Some operations use several (typically 4) consecutive bytes called a word. In a four-byte word, we can store an integer from -2,147,483,648 to 2,147,483,647.

The operating system breaks the memory for a program up into three parts: the static part, the stack and the heap.

The static part of memory holds your program, some constants that your program contains, and global variables. The program itself (a sequence of machine-language instructions) normally does not change during its execution. Constants are also unchanged. Global variables can be changed, but they occupy the same memory locations throughout. The static portion of memory is called static because it is allocated once, when the program starts, and remains of the same size while the program runs.

The run-time stack (often called simply the stack) holds information necessary to manage function calls. The local variables of functions are stored in the stack, along with extra information to allow a function to know, for example, where it should return control when it is done.

When a function is called, it is automatically allocated as much memory as it needs in the stack. When the function leaves, all of its memory in the stack is automatically deallocated, to be reused later for another function.

The heap is an area of memory where a program can allocate and deallocate memory. The key difference between the stack and the heap is that memory is not deallocated from the heap until the program explicitly deallocates it. The heap is used to get memory that a program can continue to use even after the function that allocated the memory has returned.

An expression computes a value. For example, 3+5 has value 8. A statement is executed for an effect. For example, statement n = 1; puts value 1 into variable n.

In C/C++, an expression can both compute a value and have an effect. When an expression has an effect, that effect is called a side-effect. For example, if variable n has value 5, then expression n++ has value 5, but also has the side-effect of setting n to 6.

In C/C++, any expression can be a statement. So, for example, n++ is an expression, but you can write it as a statement:

When an expression is used as a statement, the expression is computed, but its value is ignored.

You can create one large statement, called a compound statement, from several smaller ones by enclosing the statements in {...}. For example,

is a compound statement. The statements in the compound statement are executed in the order in which they are written.

Note: Each statement generally ends on a semicolon. An exception is a compound statement, which ends on }.

Because C and C++ are low level languages, they provide several integer data types. Using these types, the programmer has very close control over how memory is used. Here are the integer data types.

char A char is an integer stored in one byte. It is typically used to store the code

for a character, but can be used to store any kind of integer. Some compilers

say that a char is signed, meaning that it is taken to be an integer from -128 to

127. Some compilers say that a char is unsigned, meaning that it is an integer

from 0 to 255.

unsigned char Same as char, but all compilers treat this as an integer from 0 to 255.

short int A short int is typically an integer stored in two bytes. It can hold values from

-32,768 to 32,767. You can abbreviate short int as just short.

long int A long int is typically an integer stored in four bytes. You can abbreviate long

int as just long.

int The type int is either the same as short int or the same as long int, at the

compiler's discretion.

unsigned int These types are used to store integers without a sign. Because there is no sign

bit, you get one extra bit for storing the integer itself, so you can store twice as

many values.

Operations on integers include

+ addition,

- subtraction,

* multiplication,

% x % y is the remainder when you divide x by y,

/ x/y is the quotient when you divide x by y (an integer)

Caution: 2/3 is 0, since the result of dividing two integers is an integer.

Integer constants can be written in decimal (23) octal (071) or hexadecimal (0x3A). Character constants such as 'a' are integers -- 'a' is 97, the ascii code for character a. Some useful special characters are '\n' (newline) and '\t' (tab). The ascii code for the backslash character is written '\\'.

An enumerated type is an integer type with named members. You create such a type using an enum declaration. For example,

creates a type called Color (in C++) or enum Color (in C or C++). The compiler defines red to be 0, orange to be 1, etc., through violet, which is defined to be 6.

float Real numbers stored in four bytes. These offer about 7 digits of precision.

double Real numbers stored in eight bytes. These offer about 15 digits of precision.

long double Real numbers stored in more than eight bytes. This is not available with all

Operations on floating point types are the same as those for integers, except that % is not available, and division produces a floating point number. 2.0/3.0 yields 0.666666666666667.

A pointer is a memory address. It typically occupies four bytes. What you can do with a pointer is look at or modify the memory at the address given by the pointer. You can also compute pointers to memory cells around a given pointer, and compare pointers to one another.

Each pointer has a type. If T is a type, the type T* is the type of a pointer that points to something of type T. For example, type int* is the type of a pointer to an int.

Operations on pointers are as follows.

* *p is the content of the memory at address p. The number of bytes that you

get depends on the type of p. For example, if p has type char*, then *p is a one-

byte quantity. If p has type long int*, then *p is a four-byte quantity.

Note that, if p has type T*, then *p always has type T, for any T.

+ Suppose that p is a pointer pointing to a type that occupies b bytes, and suppose

that k is an integer. Then p+k is memory address p + bk. For example, suppose that p is a pointer with memory address 100. If p has type char*, then p+2 is a pointer, also of type char*, with memory address 102. If p has type long int*, then p+2 is a pointer, also of type long int*, with memory address 108. Notice that, if p has type long int*, then p+1 points to the next long int in memory, just after the one pointed to by p, without overlap.

- You can subtract an integer from a pointer. The result is similar to addition. For example, if p has type int*, then p-1 points to the int that occurs just before the int pointed to by p.

[] p[i] abbreviates *(p+i). So p[0] is the same as *p. p[1] is the thing in memory just

after the thing pointed to by p.

Note: Memory address 0 is not available to application programs. It is used as a special pointer value, called the null pointer. Normally, NULL is another name for 0. You use it when you want the null pointer.

To declare a variable x of type T, you write

T x;

You can declare several variables at once. For example, to declare

char variables c and d, and long int variables x and y, you can write

When you write variable declarations outside a function, the variables will be allocated in the static area of memory. When you write them inside a function, the variables are automatically allocated in the function's stack frame, in the run-time stack. So writing

inside a function causes four bytes to be allocate in the stack, when the function

encounters this variable declaration.

In C++, a variable can be declared anywhere. In C, a variable can only be declared outside a function or at the start of a function or compound statement.

You can declare variables inside compound statements. A variable declared in a compound statement is only accessible within the innermost compound statement that contains the declaration. For example, if you write

then you can use x within this compound statement, but not outside. This is a convenient way to declare variable that are only used for a short part of a function.

When you create a variable, you can give it an intial value. For example,

not only allocates memory for variable n, but it sets that memory to 0. Outside a function, the initial value of a variable must be a constant, such as 0. Inside a function, the initial value of a variable can be given by any expression. For example, you can write

as long as the values of a and b are known.

Sometimes you want a "variable" that you never intend to change, after giving it an initial value. you can use modifier const for such variables. For example,

declares size to be 40, and does not allow size to be changed. You can declare pointer variables to be constant, but the const modifier means something different for a pointer from what it means for a nonpointer. If you declare

const char* p;

then you are allowed to change p, but you are not allowed to use p to change the memory that p points to. So you can get p[1], but you cannot set p[1] = ‘a’.

Caution: If you do not initialize a variable, it has a "junk" value. Do not use the value of a variable before you put something in the variable.

To change the value of a variable, use an assignment statement, of the form x = e, where x is a variable and e is an expression. For example,

computes a+1 and puts the result in variable n. Statement

adds one to the value of variable n, and puts the result back into n.

In C/C++, an assignment is an expression. That is, it has a value. The value is the value just put into the variable. So, for example,

is an expression that has value 0, but also has a side-effect: it puts 0 in variable n.

Note: you only include the type of a variable when you are creating the variable. So

creates variable n and sets it to 0. But

sets a previously created variable n to 0.

When you assign a value to a pointer variable, you change the pointer variable itself. If you what to modify the memory pointed to by p, assign to *p. For example,

*p = 20;

goes to the memory whose address is in variable p and puts 20 there.

There are abbreviations for frequently done kinds of assignments. Here are a few.

Abbreviation Meaning

n += k n = n + k

n -= k n = n - k

++n n = n + 1 (where the value of expression ++n is the value of n after the assignment)

n++ n = n + 1 (but the value of expression n++ is the value of n before the

assignment)

--n n = n - 1 (where the value of expression --n is the value of n after the

assignment)

n-- n = n - 1 (but the value of expression n-- is the value of n before the

assignment)

***Special Warning. You must be careful when declaring pointer variables. Each variable is said to be a pointer or not to be a pointer independently of the others. If you write

then you declare x and y each to be pointers to integers. If you write

then you declare x to have type int*, but y to have type int. There is no * on y, so y is not a pointer. Spacing in your program does not affect this. So if you write

it might look like x and y are each pointers, but in fact only x is a pointer; y is an int. To avoid this problem, you might want to declare only one pointer variable per line. Alternatively, use a typedef, discussed in Section 1.7.

If x is a variable, then &x is the address of x (a pointer). If x has type int, for example, then &x has type int*.

What if you have a pointer variable p, and you get its address? If p has type int*, then &p has type int**. That is, it is a pointer to a pointer. &p is the address of a variable that contains a pointer value.

Be careful how you use the address of a variable. If the variable is in the stack, then it will be deallocated as soon as the function that created that variable returns. The address will no longer be valid.

C/C++ provides ways to deal with areas of memory that contain several values.

An array consists of several of the same type of thing stored in consecutive memory addresses. If A is an array, then A[i] is the i-th thing in array A. All subscripting is from 0 in C/C++. So if you have an array A of four things, then those things are A[0], A[1], A[2] and A[3].

To declare an array, you must give the size. Write

to declare an array x of 20 integers. Some versions of C++ allow the size to be any expression, but others require the size to be a constant, not something that you compute. When the size is a constant, you almost always use a named constant to select the size. That way, it is easy to modify the size later. You write, for example,

const int namesize = 40;

char name[namesize];

If you are not declaring an array, but are merely refering to one that is created elsewhere (as you do, for example, in a parameter list of a function heading) you do not need to give the size. You can write int x[] to indicate that x is an array of integers.

In C/C++, an array is really just the address where the array begins. So it is a pointer to the first thing in the array. If you declare array x as above, then x itself has type int* -- a pointer to an integer. It points to the first integer in the array. Recall that, when p is a pointer, p[i] abbreviates *(p+i). It is no different for arrays. A[i] abbreviates *(A+i).

A structure is a collection of values, possibly of different types, occupying consecutive memory locations. To get a structure, you must declare a structure type. You can do that as in the following example.

In C++, this declaration causes you to get a type called MyStruct. You would write

to declare a variable s of type Mystruct. (Variable s occupies eight bytes of memory, four for the long int and four for the char*.)

In C++, you can write the word struct explicitly when you declare a variable, as in

and this form is required in C.

The parts of a structure (size and name in the example) are called fields. To get the fields of a structure, you use "dot" notation. s.name is the name field, and s.size is the size field.

For example,

puts values into the structure. Note that no values are in the structure until you put something there.

You can copy the value of one structure into another. For example, if you declare variables

s and t as having type MyStruct, then

has the same effect as

That is, the entire contents of structure t is copied into the memory occupied by structure s.

If you declare structure

and you declare

then

has the same effect as

This is an important difference between arrays and structures. To put it succinctly, the size of a structure is part of its type, but the size of an array is not part of the array’s type. So copying a structure copies all of the memory occupied by the structure. But if p and q are pointers to arrays, then

only makes p point to the same array as q. It is the pointer that is copied, not the arrays themselves.

Note: A structure type is not the same as a structure variable. It would make no sense to write

MyStruct.name since MyStruct is a type, not a variable, and has no name field to select. To use a structure, declare a variable of the structure type.

You can arrange for the fields in a structure to be initialized whenever a structure variable is created. This is part of C++, and is not available in C. Inside the structure, put a function definition, without a return type, and with no parameters, whose name is the same as the name of the structure. This function is called a constructor. For example, suppose that you want each complex number to initially 0. You can write the complex type as follows.

Another option is to ask for the initial values when a variable is created. That can be done by creating a constructor that has parameters. For example, you might declare the complex number structure as follows.

Now

declares variable z to be initialized by the constructor without parameters (and hence to have both its real and imaginary parts initialized to 0) and x to be initialized the the constructor with parameters (and hence to have a real part initialized to 1, and an imaginary part initialized to 2).

It is quite common to have pointers to structures. Suppose that pointer variable p has been declared by

Initially, p has a junk value, so we would not want to look to see where it points. Let us presume that p has been given a value somehow, and we want to get the size field of the structure to which p points. That structure is *p. We can write (*p).size. For example,

The parentheses are required. Writing *p.size will not get you what you want. There is a convenient abbreviation that you can use to avoid the parentheses. p -> size abbreviates (*p).size. For example, you can write

Note: The -> notation is used only when you have a pointer to a structure. If s is a structure, not a pointer, then use dot notation such as s.name, not s->name.

Arrays of characters are used to represent strings. A standard way or representing strings is to put a 0 in the last byte, so that it is possible to tell where the string ends. For example, the string "abc" would be represented as an array as follows.

Address Content

p 'a'

p+1 'b'

p+2 'c'

p+3 0

Note that the 0 is not the character '0', but is the integer 0. It is called the null character. When a null character is at the end of a string, it is called the null terminator of the string.

When you write "abc" in a C/C++ program, the compiler allocates four bytes, and fills them as shown above, with 0 in the last byte. The type of "abc" is char* -- a pointer to the first byte of the string.

In general, strings are stored in two parts: the pointer, which serves as the handle of the string, and the memory that is pointed to, which holds the content of the string. When you deal with strings, you must be aware of these two parts. Even though you often think of a variable of type char* as holding a string, it does not actually point to any string until you set it to point to appropriate memory.

If you want to put a double quote character in a string constant, precede it with a backslash.

You can give names to types using typedefs. Declaration

declares name newT to be a new name for a previously declared type oldT. For example, you might declare a pointer type.

Now, if you write

both x and y will have type char*. You can get around some difficulties of C/C++ using typedefs. For example, there is no type for true/false data. Instead, a truth value is just an integer, with true being 1 and false being 0. You can write

to define type bool to be the same a char. Some implementations of C++ define this type bool for you. We will assume a file bool.h that defines this. Additionally, we will presume that bool.h defines TRUE to be the constant 1, and FALSE to be the constant 0.

To get memory from the heap, you can use either C or C++ style. C++ style is the most pleasant by far.

Expression

new T

allocates enough memory in the heap for something of type T, and returns the address of that memory, of type T*. For example, to get a pointer to a new MyStruct, you might write

As you can see, ms is a variable of type MyStruct*. That is, it is a pointer to a MyStruct. It is initialized to point to newly allocated memory in the heap. As another example, consider

which creates a variable c of type Complex*, and initializes it to the address of some newly allocated memory in the heap. It is very common to have pointers to structures, and to allocate those structures in the heap. If you like, however, you can allocate a variable of a simple type in the heap. For example,

You can allocate an array in the heap as well. To allocate an array of 20 chars, you might write

char* p = new char[20];

Notice that p has type char*. Here, p will be set to the address of the first byte of the array. To set the third byte of the array to 'a', you would write

(Recall that the first byte is p[0].) One nice feature about allocation in the heap is that you can compute the amount of memory to allocate. If integer variable n has a value, then you can write

to allocate n bytes in the heap.

It is recommended that you use the C++ style. However, you are likely to see the C style used occasionally. In C, memory is allocated by calling a system function called malloc. malloc(n) returns n bytes in the heap and returns a pointer to the beginning of those bytes. To allocate a string of 20 bytes, you would write

Note the "cast" (char*), which tells the compiler to consider the pointer to be a char* pointer. malloc returns a pointer of an unknown kind, and you must tell the compiler what kind it should be.

Be very careful with malloc. It allocates a given number of bytes. If you want to allocate a single MyStruct value in a C program, you would write

where sizeof(T) is the number of bytes needed by something of type T. As you can see, the C++ new operator is much nicer.

If you try to allocate memory in the heap (either via new or malloc) and there is no more memory available, you will get a null pointer as the result. It is a good idea to check that your pointer is not null after doing an allocation.

You can return memory that you have allocated using new or malloc to the system. Suppose that pointer p points to memory that you have allocated. If you allocated that memory using new,

and you did not allocate an array, then write

to return that memory to the system. If you allocated using new and you allocated an array, as in char* p = new char[30];, then delete the memory using

If you allocate that memory using malloc, use

to return the memory to the system. It is very important that you deallocate memory in a way that complements the way in which you allocated it. If you used malloc to allocate, use free to deallocate. Never deallocate a pointer that points into the run-time stack.

Be very careful about deallocating memory. Keep in mind that you can have more than one variable that holds a pointer to a given piece of memory. If you deallocate the memory, all of those pointers become stale. They continue to hold memory addresses, but the memory to which they refer does not belong to you any more. You have no idea what that memory will be used for after it has been deallocated. A pointer that points to deallocated memory is called a dangling pointer. Problems that occur from the use of dangling pointers are among the most devastating, and most difficult to eliminate, of all the problems that you can have. By avoiding them with care, you will not be subjected to the pain of finding them by laborious debugging.

If you fail to deallocate memory that you have allocated, and you let that memory become inaccessible to you, the system will not take that memory back automatically. The system will presume that your program still needs the memory. The result is a memory leak. Memory leaks are quite benign for programs that do not use much memory, but can be deadly in long runs, when your program will run out of memory.

Conditionals are used for making decisions. The most frequently used conditional is the if-statement. It has the form

if(condition) statement else statement

The first statement is done if the condition is true, and the second is done if the condition is false. The else part is optional. If it is omitted, then nothing is done when the condition is false.

Typically, the statements are compound statements. Here is an example.

The parentheses around the condition are required.

Note: The condition being tested is any integer or pointer expression. If the condition has value 0, then it is considered to be false. If the condition has any nonzero value, then it is considered to be true. This can be confusing. For example, cin.fail is a function that will tell you whether the most recent operation on cin failed. In C/C++, a function is represented by the address where the machine-language code of the function is loaded. Since an address is a pointer, a function is a pointer. If you write

you are not running function cin.fail at all, but are asking whether the pointer cin.fail is not null. Of course, it is not. The correct way to ask whether the most recent operation on cin failed is

Here are some operations for creating conditions.

== equality test

!= inequality test

> test for greater

< test for less

>= test for greater or equal

<= test for less or equal

&& 'and'. Expression A && B is evaluated by first evaluating A. A has value 0,

then A && B also has value 0, and B is not evaluated. Otherwise, A && B has

the same value as B.

| | 'or'. Expression A | | B is evaluated by first evaluating A. If A has a nonzero

value, then its value is the value of A | | B, and B is not evaluated. Otherwise, A | |

B has the same value as B.

! 'not'. Expression !A is 0 if A is nonzero, and is 1 if A is 0.

Caution: You can use the comparison operations on pointers. They compare addresses. For example, if p and q each have type char*, then testing whether p == q will test whether p and q are the same pointer. It will not test whether the strings pointed to by p and q are the same.

Caution: A frequent error is to confuse = and ==. If you write

then you will not get a test to see if x and y have the same value. Instead, you will get an assignment, putting the value of y into x, and that value will be tested. This is a serious error. You should learn to check your program carefully for this. One way to avoid this problem is, when doing a comparison that involves a constant, to write the constant first. That way, if you accidentally write = instead of ==, you will get a compile error.

For example, write

You can make a test in an expression in C/C++. Expression

condition ? val1 : val2

is val1 if condition is nonzero, and is val2 if condition is 0. For example, expression

evaluates to the larger of x and y.

Sometimes you want to make several tests of a single value. C/C++ provides a switch statement for that purpose. Here is an example.

Note: You must include break; after each case. If you do not, then the program will keep going into the next case. For example, if you run the following with day = 5

the program prints

Note: If there is no default case, then nothing is done if none of the cases match.

Note: You can have two or more cases do the same thing. Just put them in a row, as in

text for these cases

Note: You can only use a switch when the type of the value being tested is an integer type.

C/C++ provides three kinds of loop.

The while-loop is used to do a statement zero or more times. Statement

while (condition) statement

does the statement (called the loop body) repeatedly until the condition is tested and found to be true (nonzero). For example, suppose that s is a pointer to a null-terminated string. The following sets n to the length of string s.

The condition is tested before the loop is entered for the first time. If the condition is false immediately, then the loop body is not performed at all.

A do-loop is used to do a statement one or more times. Statement

do statement while (condition);

does the statement repeatedly until the condition is true (nonzero), but tests the condition for the first time only after it has already done the statement once.

A for-loop is typically used to count through a fixed sequence of values. In general, statement

for (A; B; C) statement

abbreviates

A;

while (B) {

statement

C;

}

For example, here is a statement that prints the numbers from 0 to 9.

This for-loop abbreviates

Note: A for-loop has just three parts, separated by semicolons, within its parentheses. You can omit any part, but must not omit the semicolons. If you omit the test (the middle part), you get an infinite loop.

Note: In C++, if you declare any variables within the parentheses after for, those variables are only available within the for-loop. In C, those variables can be used after the for loop as well.

A function takes zero or more parameters, computes, and then returns a value. A function definition looks like this.

return-type function-name(parameters)

{

statements

}

Within the statements, you can use a return statement to cause the function to stop computing and to return a value. Here is an example, a function that returns three times its parameter.

To use function triple in an expression, just provide a value for the parameter. For example, statement

sets n = 15.

Note: In the definition of function triple, parameter x is called a formal parameter. It is just a place holder. In the expression triple(5), the number 5 is called the actual parameter. It is the value that is used in place of the formal parameter.

You can use functions in arbitrarily complicated expressions. For example, statement

sets m = n + 3(k+2). Another example is a function that computes the length of a null-terminated string. We use the loop from the loop section.

To use the length function, just give it a pointer to a null-terminated string. For example,

would set r = 4.

Here is a function that takes two parameters, and returns the larger one. Note that the parameters are separated by a comma, and each must have a type.

For example,

would set r = 8. We can use function max to create another function max3, which computes the largest of three values.

Sometimes, you need to tell the compiler what types of parameters a function takes, and what type it returns, without writing the function. You can use a prototype, which is just the function heading, followed by a semicolon. A prototype for function max3 is

In a prototype, you may include names of parameters, as is done above, or you can omit them, as in

In C/C++, each function must have a return type indicated. However, that return type can be the reserved word void, indicating that no value is returned. For example, the system function exit takes an integer parameter, and stops the program. Its prototype is

You do not need to have a return statement in a function that returns void. If you like, you can include one, but it should just say

Three ways to pass information to a function are call-by-value, call-by-pointer and call-by reference.

Call-by-value. Call-by-value is the default calling mode. When you pass a parameter, the value of that parameter is sent to the function. The formal parameter acts as a variable local to the function that is initialized with the value of the actual parameter. If a structure is passed by value, the contents of the structure is copied into the formal parameter.

Call-by-pointer. Call-by-pointer is a special case of call-by-value in which the value that is passed is a pointer. When you have a pointer, you can do whatever you like with the memory that the pointer points to. For example, consider function increment.

Function increment adds one to the variable that points to. For example, in

the value of x would be 1 just after the call to increment. Notice that we must pass a pointer to function increment, so we use &x to get a pointer to variable x. If you already had a pointer, you would just pass that pointer value. For example,

Here, after the increment call, variable *p holds 1. (Variable p holds a pointer to variable *p.)

What would happen if we did this?

The line int* p = 0 sets pointer variable p to 0. So p contains a null pointer. When function increment does *p, it will cause the program to abort. (You will get a memory protection error, since memory address 0 is not accessible to you.)

Call-by-pointer is the default mode for arrays, since an array is the same as a pointer to its first member. Sometimes, you want to pass an array as a parameter, but do not want to allow the array to be changed. To do that, use a constant pointer. For example, the prototype for the function length written previously should really have been

since the length function does not change the array that is passed to it.

Call by Reference. When you pass a variable as a parameter, it can be awkward to deal explicitly with pointers. C++ (but not C) has a way to pass variables in a more convenient way. Use & instead of * in the type of the parameter. Then the parameter is a reference parameter, and it is thought of as a variable that is being passed. For example, function increment can be written using call-by-reference.

Notice that variable x is now just an integer variable, not a pointer variable. To use this new increment function, you do something like this.

You do not pass &n now. You just pass n as the actual parameter. The compiler passes the variable n to function increment. Within function increment, formal parameter x just names variable n. So after the call to increment, n has value 1.

When the compiler implements call-by-reference, it really just does call-by-pointer, but it inserts the & and * operations where needed automatically.

Return-by-value. Typically, a function returns a value. For example, the max function takes two integers and returns an integer (that is, a value).

Return-by-pointer. You can have a function return a pointer. Then, the caller gets access to the memory that the pointer points to. A pointer returned by a function should usually point into either static memory or into the heap. Returning a pointer into the stack is asking for trouble, except when carefully controlled. Here is a function that allocates an integer variable in the heap, sets it to 0, and returns a pointer to the new integer variable. It also checks that the system did not run out of memory.

Return-by-reference. In some circumstances, you would like a function to return a variable, so that a function call expression can be used just like a variable. In such circumstances, you use return-by-reference. Often, the reference that is returned is the same as one of the reference parameters. Here is a function that increments a variable, and returns the variable.

Now you can write increment(increment(x)) to add two to x, if you were so inclined.

You can perform output to a terminal or a file in either the C or C++ styles. (C style can be used in either C or C++ programs. C++ style can only be used in C++ programs.)

To use C++-style output, include header file iostream.h.

Variable cout refers to the standard output (usually the terminal). Binary operator << is used to write. You can write many different kinds of things, such as integers, characters and strings, and you can perform several writes in one statement. For example,

writes 2 and a, with no space between them. You can include null-terminated strings as well, as in

The endl constant is just "\n". Some other operations using cout are as follows.

cout.write(buf,n) Write n characters from character array buf.

cout.flush() When you print on cout, what you print goes into a buffer until the

buffer becomes full. Then the contents of the buffer is actually

printed. This delayed printing can be a problem sometimes.

Function flush prints what is in the buffer.

cout.close() Write an end-of-file marker to the file being written by cout. This

terminates the file. After doing this, you can no longer write to

Variable cout is just one variable of type ofstream, used to print to a file. You can create other ofstream variables, and tie them to files. To do this, include header file fstream.h. For example,

declares variable myout of type ofstream. It also uses a constructor that ties this variable to the system file called "myfile". The file will be emptied, if it already exists. Anything that you write will be written into that file. When you are done writing to the file, close it, using the close function.

To use C style output, you must include header file stdio.h.

To write in C style, you can use library functions printf and fprintf. Include header file stdio.h to use these. The first parameter to printf is a format, a string that tells what the output should look like. Within the format are sequences that start with %, and that indicate that the value of the next parameter should be put here. For example,

would print

Here are some of the formats that are available.

%c Print a character.

%d Print an integer. %3d prints the integer in three spaces, padded on the left with

blanks. If the integer is too large for three spaces, more will be used. %-3d is

similar, but pads on the right with blanks.

%ld Print a long integer. %5ld print the long integer in five spaces.

%f Print a floating point number. %6.2f prints it in six spaces, with two digits to the

right of the decimal point.

%s Print a string. The parameter must point to a null-terminated string. %12s prints

the string in 12 characters, padded on the left with blanks.

%% Print a % character.

To print on a file, you must open the file. Use the following.

to open a file for writing. Now use

to print on the file. Finally, to close the file, use

For example, here is a function that writes file "test.out", putting string

in the file.

See documentation for fopen for more on opening files.

You can perform input from a terminal or a file in either the C or C++ styles. (C style can be used in either C or C++ programs. C++ style can only be used in C++ programs.) Use the same header files as for output.

Variable cin refers to the standard input (usually the terminal). Binary operator >> is used to read. You can read many different kinds of things, such as integers, characters and strings, and you can perform several reads in one statement. For example,

reads an integer, and puts it into variable n, and then reads a character, and puts it into variable c. If you read a string (char*) using >>, characters will be read up to a space or newline, and put into the string. Be sure that there is enough room in the arrray. If you read a character, you will get one character, except that white-space characters (blank, tab, newline) are skipped.

Some other operations using cin are as follows.

cin.eof() True if cin is at the end of file.

cin.fail() True if the most recent operation done failed. This can also be used to test

cin.get() Returns the next character, or the special value EOF (-1) if there is no

does not skip over white-space characters.

cin.peek() Returns the next character, without removing it from the stream. Like

cin.putback(c) Puts character c back at the front of the stream.

cin.read(buf,n) Reads n characters and puts them into buffer buf. buf must be a pointer to

a buffer that you have already allocated.

cin.getline(buf,n) Reads a line and puts it into buf. It replaces the end of line character

by a null character. n is the size of buf. No more than that many

characters will be read.

cin.close() Closes stream cin. (You cannot read from cin after closing it.)

You can read from a file. To do so, include header file fstream.h.

To read from a file, just create a stream attached to that file. Declaration

creates variable f, a stream bound to file name. You can use the same operations on f as on cin. For example,

creates a stream called ins and reads an integer from it. When you are done with a stream, close it, as is done above. But don't close it until you are done reading from it. The example only wants to read one integer, and no more.

To read in C style, you can use library functions scanf and fscanf. Include header file stdio.h to use these. The first parameter to scanf is a format, telling what kind of data to read. Usually, the format just has indications of types that are similar to the indications in output formats. For example, to read two integers m and n, you would write

Notice the need to use &. The parameters after the format are call-by-pointer. If you use format %s, then a string will be read up to a space or newline.

To read from a file, you must open the file for reading, and use fscanf. For example,

reads a single integer from file infile.txt. A handy function is gets. gets(f,s) reads a line from file f, and puts it into array s. The newline character in s is replaced by a null character, so that s becomes a null-terminated string.

When a C or C++ program is compiled, it is first passed through a preprocessor, which makes some modifications to the program. One thing that the preprocessor does is to expand includes. When you write

the preprocessor inserts the contents of file stdio.h in place of the include line. Include lines can have the file name enclosed in <...> or in "...". If you use <...>, the preprocessor looks for the file in the directory that has standard header files. If you use "...", the preprocessor looks for the file in the current directory.

The preprocessor provides a macro facility. If you write

for example, each occurrence of NULL will be replaced by 0 by the preprocessor. Common substitutions are

We assume that header file bool.h define TRUE, FALSE and NULL. Note that there is no semicolon. If you write

then each occurrence of "TRUE" gets replaced by "1;", which is probably not what you want. #define lines are one line long. The preprocessor is not free-form.

Note: TRUE will only be recognized by the preprocessor when it is not part of a longer word. If you write TRUE_LIES, for example, the preprocessor will not make a change.

Macros can have parameters. You can write

to create a macro for computing the maximum of two values. max(n,0) would be replaced by (n) > (0) ? (n) : (0). You should always put parentheses around arguments in macros, as has been done here, or you can get very strange effects from the textual substitution done by the preprocessor.

Note: Preprocessor directives start with a # in column 1. Don't indent the #.

The preprocessor can also be used to make decisions at compile time. A common kind of decision is to ask whether a symbol is defined. A definition of NULL might look like this.

This says to compile what is between #ifndef NULL and #endif only if NULL is not a defined preprocessor macro. This kind of thing is commonly used in header files (described in the next section) to prevent them from being read more than once by the compiler. A file called

myhead.h typically has the form

The first time the file is read, and MYHEAD_H is defined. Subsequent times, the entire file is skipped.

When you build a program from several files, you typically break each file into two parts: a code file (with extension .cpp or .cc for a C++ program, or .c for a C program) and a header file (with extension .h). The code file contains the function and variable declarations. The header file just tells what is in the code file, so that other files can know about them. If there is a function in the code file that other files should be able to use, then there should be a prototype of that function in the header file. If there is a variable in the code file that other files should know about, then there is an extern declaration in the header file. Here is an example of a pair of files. They must be in two different files. These should not be taken as a recommendation on how to write functions: realistically, char_to_count should be a parameter to function count_chars.

When you compile your files, you produce object files, with extension .o or .obj. You then run a linker to link the object files together into a single executable file.

Note: If you declare an array in a module, as in

then the extern declaration should have the same form, but need not include the size. For example, you might write

An array is a pointer constant. Do not put

since that tells the compiler that A is a pointer variable, and causes confusion.

When the linker builds an executable file, it looks for a function of a specific name, and creates the executable file so that it starts with that function. In most systems, the function to start with is called main. The main function has three parameters, although you often use only the first two. When you use two, your main program heading looks like this.

where array argv holds the parts of the command line that was used to invoke this program, and argc is the number of members of argv. argv[0] is the name of the command. If you type command

then argc is 3 and argv is as follows.

argv[0] = "myprog"

argv[1] = "-d"

argv[2] = "test.txt"

The return result of main is the exit status of the program. Normally, it is 0. A nonzero value indicates that an error occurred during the program's execution.

Note: If you do not use the parameters argc and argv, you can omit them, and write

There are quite a few libraries available -- more for C++ than for C. We cannot discuss all of the libraries here. Instead, we cover a few useful functions for manipulating null-terminated strings that are available if you include string.h.

strlen(s) Returns the length (number of characters, not counting the terminating

null) of string s.

strcat(s,t) Concatenates string t onto the end of string s. The memory that is used

is what occurs just after string s in memory, so you must be sure that

buffer s has enough extra memory available at its end. The return value is

pointer s.

strcpy(s,t) Copy string t into the buffer pointed to by pointer s. The return value is

pointer s.

strcmp(s,t) Compare the contents of buffers s and t. Return

0 if the strings are the same,

-1 if s is alphabetically before t,

1 if s is alphabetically after t.

strchr(s,c) Find the first character in string s that is equal to c, and return a pointer to

the byte that contains that character. If there is no such character in string

s, then return NULL.

strstr(s,t) Find the first occurrence of string t as a substring of string s, and return a

pointer to the start of that occurrence in s. If string t does not occur in

string s, return NULL.

strdup(s) Allocate memory in the heap (using malloc), and copy string s into that

memory. Return a pointer to the copy of s.

C/C++ compilers tend to be quite unfriendly when they encounter incorrect programs. When you get a compile error, do your best to understand what the compiler is saying, but if you cannot make sense of what it says, just look at the line where the error is reported, and possibly at the line (or a few lines) before that line. Try to find what is wrong.

If you omit a semicolon from a C/C++ program, the compiler can become very confused, and can produce hundreds of error messages. Don't let them bother you. Generally, fix the first error, and then compile again. Some of the other errors might go away.

Programs typically include several separate modules. When you make a change, you must recompile the modules that you have changed, and then link the modules together. That can be very tedious, if you do it by hand. Tools are available to make the job easy. One tool, available under Unix, is make. To use make, create a file called Makefile in the directory where your program files are. Put, in Makefile, a line for each of your modules telling how to compile it. Here is a sample makefile, for a program with two modules called tables.c and main.c. It puts the executable program into a file called go.

Line CFLAGS = -g –c indicates that $(CFLAGS) should be replaced by –g –c. Each pair of lines after that consists of a first line giving a target, a colon, and some files on which the target depends. For example, file main.o depends on file main.c. The next line must begin with a tab. It contains the command that builds the target. In general, you can put several lines of code, each preceded by a tab.

Now to build go, just type

This builds the first target in the file. Before building go, main.o and tables.o are build, since go depends on them. However, a target is only built if it is out of date. If you modify tables.c but not main.c, then make will not recompile main.c.

If you only want to rebuild a selected target, put that target on the make command line. For example,

only builds target tables.o.

Since computer programs are easy to change and to run, it is tempting to throw something together and begin testing and debugging right away. If you do that, you will spend far too long debugging. Try to be cautious about how you program. After you have written a function definition, for example, reread the definition, and convince yourself anew that the function is written correctly. Look for errors, such as memory allocation errors. Shoot for having the function work the first time, without going to extremes of hand checking that take too long.

In spite of your best planning, you will make mistakes, and you should plan for them. To fix your program, you will need to use debugging strategy and tactics.

Debugging strategy tells you the large steps involved in debugging. The steps are as follows.

1. Determine that something is wrong. Simplify if possible to a small input that the program gets wrong.
2. Isolate the error as closely as possible within the program. For example, you might determine which function is at fault.
3. Determine exactly what is wrong.
4. Determine what can be done to fix the program.

Debugging tactics are particular ways to accomplish the goals of a strategy. Usually, isolating the error is the hardest thing to do. Here are some tactics for isolating errors. They also help in step 3, determining exactly what is wrong.

Add prints to your program to show what is happening. Direct the prints to a file, not to the standard output. You might let the main program open a file, and make that file available to all modules using an extern declaration.

Be sure that you do not print raw data. Each added print should show who did the print, where it is, and what is being printed. For example, if you insert a print at the top of a loop body in function copy, and you are printing the value of an integer variable n, you might write

If you are printing an array A of n integers at the beginning of function insert, you might write

Hint: If you define a preprocessor symbol such as

then you can use tprint in place of fprintf in your trace prints. The advantage is that you can then search for tprint using a text editor or search utility, and quickly find all of the trace prints.

Hint: You can leave trace prints in your program if you surround them by preprocessor conditions. For example, you might write

Now if you have said

then this print will be compiled in. If not, then it will not be compiled.

A debugger can be a powerful tool if used correctly. There are many different debuggers, each with its own characteristics. Typical things that a debugger will do for you are

1. Show where a program is when an error occurs.
2. Show the values of variables.
3. Allow you to stop the program at selected places.
4. Allow you to step through a program.

Debuggers rely on extra information being put into executable files, telling the names of functions and variables. When you compile a file, you should be sure to tell the compiler to include debugging information. In Unix, for example, you use option –g on the compile command line. For example, you might say

to compile C++ program program.cc, and put the executable code into file program.

An example of a debugger is the Gnu debugger (gdb). To debug a program using gdb, you type

where program is the name of the executable file. The debugger has its own language. Use the following with gdb.

1. Command run runs the program.
2. Command bt shows the run-time stack, most recent frame first, when the program encounters an error.
3. Command print x prints the value of variable x.
4. Command break name causes the program to paus, and return control to the debugger, when the program enters function name.
5. Command cont continues the program after a pause.
6. Command help provides information about more commands.

Successive refinement is a method of developing a program gradually. After each stage, you have a working program that does part of the job, or that at least incorporates some of the parts that the full program will hold.

To develop a program by successive refinement, start with a refinement plan. Think about the parts, and how they can be tested. Write each part, and test each before moving on. A big advantage of this is that isolation of errors is usually easy. The error is usually in the (small) part that you have just written.

One way to find an error is to read your program carefully to see if it looks correct. Try hand executeions. For some errors, this approach will show you the error faster than any other method. But be sure not to give up if code inspection does not reveal to you what is wrong. You can fall back on tracing or running a debugger.

You will need to develop, though experience, a feel for which is more useful in each situation, a debugger, tracing or code inspection. If you get a memory protection fault, a debugger will tell you where the fault is very quickly. If you have a subtle algorithm flaw, you will often find that a trace is more effective. If you have just written a piece of code and things seem very bad, sometimes a code inspection of that piece will reveal the error quickly.

Never assume that your program works. Always test it. When you design a program or a part of a program, you often have one or two example inputs in mind, to help you think about the problem. Since you understand those example inputs, you test your program on them. It is very tempting to think that your program works once it has successfully handled those examples. But

one or two examples.

Try several examples, including some that you think might be difficult, or might expose a bug.

Check the results, and see whether they are right. Try extreme examples. Keep in mind that whoever uses your program will probably use it on examples that are unlike your original one or two test cases.

Keep your tests around, even after all have been passed. You might modify the program later, and need to retest it to see that your modifications have not made it fail on cases where it previously worked.

A function performs a specific task. It encapsulates the knowledge of how that task is performed, freeing the rest of the program from the need to know such details. Sometimes, a function encapsulates knowledge of an algorithm that is complicated. Sometimes, the function encapsulates a very simple algorithm, but it encapsulates information that might change later, when the program is modified. When that information changes, you only need to change one function.

Functions are important program design tools because they allow you to break a large program up into manageable pieces, and to deal with each piece separately.

Functions in C/C++ are typically of three kinds.

Pure functions. A pure function does not change anything. It only computes a value. For example, strlen is a pure function. You pass it a string, and it gives you the length of the string.

You think of a pure function the way you do a mathematical function such as sqrt.

Procedures. A procedure is a function that makes changes to things, and that returns a void value. You think of it as performing a command. Sometimes, a procedure only changes the values of reference parameters. Sometimes, it changes other things, such as things pointed to by parameters.

Mixed functions. A mixed function returns a value, and also has side effects. For example, scanf is a mixed function. It puts values in its parameters, but it also returns a value. (The value returned by scanf is the number of items that it successfully read.) Mixed functions are useful, but should be used with care. If you do more than one in a single expression, the different mixed functions might interfere with one another.

The functions of a particular application can usually be broken into two groups. First are functions that are particular to the application, and would make little sense if found in another application. Such functions might, for example, print messages that would almost certainly not be appropriate to other applications. I will call these functions application specific. The second kind of functions are those that might easily be picked up and put into another application, without change. I will call these functions application independent.

The interface of a function tells the function user everything that he or she needs to know, and no more. There are two parts of the interface.

Prototype. The prototype tells the types of the parameters and the return type. It tells the compiler how the function can be used in a program.

Meaning. The meaning of a function tells what the function does. It is usually a comment, and is called a contract for the function. The contract should tell about all of the parameters, about the return value, and about any changes that the function makes. It should not tell details that are supposed to be encapsulated inside the function, such as how the function does its job.

You can tell whether a function is application specific or application independent by examining its contract. If the description of the function makes reference to where this function fits into the current application (for example, by saying that this function is called by function jam, which handles part three of the application) then the function is application specific. If the description only tells what the function does, without reference to who calls it or exactly how it is used in the application, then the function is often application independent.

Novice programmers tend to make all of their functions application specific. Expert programmers make as many functions as possible application independent.

The implementation of a function tells how the function works. It is written in C/C++, and gives all of the detail. See the examples below.

This is a pure function. We provide the interface, consisting of the contract above the function and the heading of the function, and the implementation, consisting of the body of the function.

Notice that the comment describing the algorithm is in the body, since it describes the implementation, not the interface.

This is an application independent function. Its description tells what it does, not for what purpose some other part of a program uses it.

Again, we provide an interface (two parts: contract and prototype) and an implementation. This function is application independent.

This example is similar to the previous example, but the function is pure. The method of allocation is relevant to the interface since the user might need to free the allocated memory, and needs to know how it was allocated in order to free it.

This function is similar to the preceding two, but instead of allocating memory or making changes in an existing string, this function asks the caller to provide the memory into which the new string will be placed.

A large program must be broken into small functions to make it manageable. How do you decide what those functions should do? Here are some guidelines.

1. Choose functions so that their interfaces are simple and natural. A function that has ten parameters and does so many different things that its description is pages long is almost useless. A function with a few parameters and a short, simple description is generally much more useful. Do not use this as an excuse, however, to write inadequate contracts. Say everything that needs to be said.

2. When writing a function F, ask yourself what natural subtasks the function breaks into. Ask yourself what library functions you wish that you had, functions that would make writing F easy. Then write interfaces for those functions. Now write function F, using the functions that you wish you had. Now write the functions that you wish you had. This is called top-down design, and is a very useful design method.

3. Wherever possible, choose application independent functions. You will find that they are more useful to you, even in the current application. If you choose your functions wisely, then you will find that a function that you thought would only be useful in one place turns out to be useful elsewhere as well.

Abstraction is a suppression of detail. You can think of a function as abstracting a task or algorithm. The interface provides only the abstract view, telling what the function accomplishes. The implementation provides the concrete view, showing the details.

Functions abstract computation. But what about the data on which computation is performed? If you have only functions as an abstraction tool, then your data is always concrete. There are good reasons for wanting to abstract away details of the data as well as to abstract details of computation.

1. What you care about in data is what is stored, not how the data is stored. A programmer does not want to be burdened with unnecessary details.

2. Often, you find it desirable to change the representation of data. For example, a new, very clever implementation of some of the operations that you need might come along, but it might require that data be stored in a particular way. (Efficient algorithms usually have strict requirements on how data is stored.) You might want to remove a more naive implementation of those operations, and plug in a more efficient one, without disrupting the rest of your program.

You can only do that if your program is insensitive to the representation of the data.

You cannot hide the details of the representation from all functions. Some, of course, must deal with the data at a very concrete level. So how can the details be hidden? The answer is that those functions that need to see the details are part of the abstract data type.

When you change the implementation of an abstract data type, you only need to change those functions that are part of the abstract data type.

There are two major kinds of ADT: destructive and nondestructive. Nondestructive ADTs are also called persistent ADTs. Destructive ADTs are characterized by functions that change the data that is stored. The functions in a destructive ADT are typically procedures or mixed functions, although some of the functions are usually pure. The functions in a nondestructive ADT must all be pure. They cannot change anything.

An interface to an ADT tells a user of the ADT everything that he or she needs to know, and no more. The interface consists of two parts: the signature and the semantics.

Signature. The signature consists of the name of the type and prototypes for the functions that are part of the ADT. For example, here is the signature for an ADT that is a stack of integers. (Is this a destructive or nondestructive ADT?)

Type: IntStack

Functions:

Semantics. The semantics of an ADT gives meanings to the functions. It consists of a description of the data that is represented, and contracts for the functions. Here is the semantics of our integer stack ADT.

An IntStack holds a sequence of integers. The sequence is thought of as being written

vertically, and having a bottom and a top. When you create a stack, it is has nothing in it. That is, it is empty.

Empty(s) removes all integers from s, making s empty.

isEmpty(s) returns TRUE if s is empty, and FALSE if s is not empty.

Push(x,s) adds x to the top of stack s.

Pop(s) removes the top number from stack s, and returns it. If s is empty,

then pop(s) returns 0, and does not modify s.

The implementation of an ADT provides a representation of the type, and implementations of the functions. It is written in the programming language that you are using, such as C/C++.

One way to create an abstract data type is to put the type in the header file, along with prototypes for the functions. Doing things this way has a serious defect: it makes the representation of the type available to all functions, and so does not hide it, since that representation is in the header file. Ways to improve this are discussed later.

Here is a full implementation of the stack ADT outlined above. In the header file, we put the signature and the type. In the implementation file, we put the implementation, along with documentation of the implementation. This implementation assumes that a function called abort is available to exit the computation at an error.

// File: intstack.h

// File: intstack.cpp

To use the IntStack ADT, you would include its header file, and use the type and functions.

Suppose that function main had attempted to use st.top directly. Doing so would have been a logical error, since data value st.top is part of the representation of stacks, and should not be visible outside the ADT implementation. Unfortunately, the compiler will allow us to make that error. Using classes, covered later, it is possible to make such an error impossible to make.

Here is another example of an abstract data type. This is a nondestructive stack ADT. Although it provides stacks, it is quite different from the previous ADT. This ADT does not attempt to recover memory, since doing so for this kind of data type is beyond the scope of these notes.

// File: istack.h

To use this ADT, you would include its header file, and use its type and functions. You must be sure to use them according to the signature.

Think of a type as a factory for producing things. For example, type IntStack is a factory for producing stacks. Each thing that is produced has the same capabilities, and initially looks the same. For example, each can do a push, and each can do a pop.

An object is similar to the things produced by a type. It can be the value of a variable. It has certain capabilities, such as the ability to do certain functions. The difference is that an object carries its operations with it. For example, you might have several different objects that have the capability to do a print operations. Some of those objects will do one thing when asked to do a print, others will do something else.

When you write a function that uses an object, you typically ask that object to do a few specific things. For example, you might ask it to print and to make a copy of itself. What you exploit when you use an object is its signature. You require that it has the ability to do the operations that you ask it to do. You can imagine that your function will do something meaningful on any object that has the correct signature. Your function takes on new generality when used with objects. Instead of working on just one type of thing, it becomes polymorphic.

Like a member of an ADT, an object holds data. It keeps that data in a way that is invisible to other parts of the program. So an object becomes a convenient place to store a package of information. An object typically holds data and also carries functions that manipulate that data. Since the data and functions are packaged together, the rest of the program does not need to deal with the data at all. If the rest of the program wants something done with that data, it asks the object to do the job on its own data.

Objects are supported by C++, not by C. C++ has special syntax for dealing with objects. If x is an object, and you want to ask x to perform operation op with parameters a, b and c, you write

If p is a pointer to an object, rather than being an object itself, then you can ask the object that p points to to perform the same operation as follows.

Like an ADT, an object has a signature and a semantics. The signature tells the operations that the object is capable of doing, and the semantics tells what it will actually do.

In order to create an object, you must build a factory that builds objects. Such a factory is called a class, and is covered next. The interface to an object is given with the interface to its class.

The implementation of an object is given by the implementation of its class. This approach to objects has some advantages over creating objects one at a time. It always gives you the capability of creating more of the same kind of thing. Also, it yield quite efficient implementations of objects. You think of an object as carrying with it implementations of its operations. What actually happens is that the object simply carries with it the name (or number) of its class. Each time an operation is required, the class is consulted. This is far more efficient that having objects actually carry the operations with them.

Objects typically implement destructive operations that modify the data stored in the object. Because of this, you rarely want to make a copy of an object. Instead, you refer, via pointers, to a single object.

To prevent copying, objects are usually passed by reference or by pointer to functions. If a function returns an object, it usually returns it by reference or by pointer.

A class is a factory for producing objects. It also provides the implementations of the operations, usually called methods, that are done by the objects in the class.

A class is similar to an abstract data type, and we will use classes to implement abstract data types in a secure manner, hiding what needs to be hidden.

Classes also provide a way for the compiler to manage polymorphism. The fact that an object is a member of a certain class indicates that it has at least a certain signature. There is a mechanism for indicating that one class has the signature of another, plus additional operations. If class B has all of class A's operations, and possibly more, then class B is said to be a subclass of class A.

We do not deal with subclasses in these notes, but they form an important part of object-oriented programming.

In object-oriented programming, the word member is used in more than one way. An object that is created by a class is a member of that class, in the same way that the number 2 is a member of type int. But objects themselves have parts, and those parts are called members of the object. For example, if object x carries with it a function called grove, then grove is a member function of the object. Now comes the difficulty: objects are described by describing their classes. Hence, a member function of an object is said to be a member function of its class. You must understand that the word member in this context really refers to membership in the objects that the class constructs.

Ideally, the class interface would tell only the class name and the operations that its objects support. Unfortunately, for reasons similar to those that required structures to be put in header files, you must provide information about the data representation in the header file. A feature of classes that partially counteracts this is that you can indicate that the data is private. Private data can only be used by the member functions of the class. This gives you a much more secure implementation of an ADT than would be obtained by making the data visible to everybody.

A class is similar in form to a structure. In the class, you list the data fields and give prototypes of the member functions. Each member function, however, comes with an implicit parameter: the object that performs the function. So you typically have one less explicit parameter than you would using a structure-based implementation.

Here is an interface, given in file cintstack.h, of a stack of integers ADT. This is a class-based ADT similar to the structure-based ADT IntStack of part 4 of these notes. Notice that the function prototypes are inside the class definition, and that they have one less parameter (the stack) that in the IntStack ADT.

// File: cintstack.h

The missing parameter, the stack that is performing the operation, is implicitly of type CIntStack&. In the case of function isEmpty, the missing parameter is indicated to have the const attribute by placing const after the prototype.

To use this class, we use object notation. Here is an example. Compare it to the example for the structure-based implementation IntStack. Line

creates a CIntStack object called st. This is where the class CIntStack is used like a factory.

If function main had attempted to use st.top, the compiler would have flagged the use as an error, since the top field is private to the class, and so cannot be used by functions that are not members of the class.

To implement a class, you must implement each of its member functions. You must indicate, in each function definition, that your are creating a member function of this class. You do that by adding the class name, followed by ::, to the function name. For example, to define function Empty in class CIntStack, you define CIntStack::Empty.

Inside the definition of a member function, you can refer to the object that is performing the method by pointer value this. For class CIntStack, this has type CIntStack*. You can refer to the fields of this, and ask this to perform member functions, without explicitly writing this. For example, top abbreviates this->top and Push(2) abbreviates this->Push(2).

Here is an implementation of class CIntStack. Compare it to file instack.cpp.

// File: cintstack.cpp

This example implements queues using stacks to help. So it both implements an ADT and uses another ADT. This example also uses a private function, Normalize.

// File: queue.h

When you declare a variable or function in a class, you normally intend to describe a feature of the objects that the class produces. The objects of a class are sometimes called instances of the class, so these variables and functions are called instance variables and instance functions, or instance methods.

It is possible to create variables and functions that are associated with the class itself, not with the objects. A class variable is shared by all objects, as is a class function. To declare a class variable or function, precede it by the modifier static. For example,

creates a class MyClass that has a class variable called count. Use class variables and methods whenever you want to think of the class itself as a special object, and to give it attributes, or when you need a variable that is shared by the instances of a class.

Constructors are used for initialization of objects, and always have the same name as the class. When you define a constructor, you do not give a return type.

Constructors are often written inside the class itself. But you may write them in the .cpp file if you like. A constructor for class Queue is called Queue::Queue in the .cpp file.

There are a few technical problems associated with constructors that are dealt with here.

If you do not call a constructor on the instance variables in an object, they are, by default, initialized using the constructor for their own class that has no parameters. For example, the Queue class above uses this fact to ensure that the two stacks are initialized to empty stacks.

Sometimes, you want to use other constructors for instance variables. There is a special syntax in C++ for doing that. Here is an example that uses this syntax. Suppose that class LimitedStack provides stacks of fixed size, and provides a constructor that gives the desired size.

The variables to be initialized follow the colon, with their parameters but not their types. They are separated by commas.

When a copy of an object is made, a default copying method is normally used. The default copier

simply copies all of the variables in the object. That is often not what is desired. Imagine, for example, that you are implementing a linked list. To copy the list, you really need to copy all of the cells of the list. The default copier does not do that.

C++ allows you to write your own copy constructor. The copy constructor for a class called Raven has prototype

If you define such a constructor, then it will be used instead of the default constructor to do copying. It is used to initialize the copy, with its parameter being a reference to the object that is being copied. All copying is done using this constructor, whether it is a copy at an assignment, or due to passing an object as a value parameter to a function, or any other reason.

For example, if you use the default copier for class CIntStack, you find that the copy and the copied stack both contain pointers to the same content array. This is not a good idea, since a push to one of the stacks will modify what is in the other. Class CIntStack should really be provided with a copy constructor, so that each stack has its own array. The copy constructor for class CIntStack might be written as follows.

In file cintstack.h:

In file cintstack.cpp: