CSC270 November 4 Tutorial: C++
Abstract Data Types
[ King 19.3 ]
An Abstract Data Type (ADT) consists of a data type and the operations
that can be performed on it. For example:
integers in a FIFO queue
operations: enqueue(x)
x <- dequeue()
empty?()
The ADT makes _no_mention_ of the actual implementation.
A program using the ADT may make use of _only_ the things defined in
the interface. All other parts (e.g. the implementation) are hidden.
This means that the implementation can change in the future while
programs using the ADT don't have to change.
Introduction to C++
Comments
Comments in C++ appear as
/* comment */
which can span many lines. A comment at the end of a single
line appears as
// comment
Storage Allocation
int *a, *b;
a = new int; // a points to an integer
b = new int[100]; // b points to an array of 100 integers
a = 5;
b[3] = 5;
delete a; // free the memory used by a's integer
delete [] b; // free the memory used by b's array.
// (note the wierd syntax)
Classes
Classes are just like structures, except:
- they can contain functions
- they can `hide' some of their components
Here's a stack class.
class stack {
public:
void push( int x );
int pop();
int empty();
stack()
{ size = 0; }
private:
int size;
int a[100];
};
Note the semicolon at the end of the class. Don't forget it!
The `public' parts are accessible by any part of the program.
The `private' parts are accessible only by program code defined within
the class.
push(), pop(), and empty() are prototypes of functions defined within
the class. Their code appears elsewhere. They have access to private
parts of the class.
Class Functions
In the definition of the stack class is a public function of the
_same_name_ as the class:
stack()
{ size = 0; }
This is a `constructor' and is called automatically when an instance
of the class is created. It typically contains a very small bit of
code and initializes the class. This is called, for example, when a
class instance is created with "new" or when a function is entered
that has a class instance as a local variable. Global variables that
are class instances are also initialized this way _before_ main() is
called.
Program code that appears _inside_ the class definition (like stack()
above) is typically compiled "inline". That is, whereever there is a
call to a function defined inside the class definition, the code of
the function replaces the function call. This saves the cost of the
function call, at the cost of some extra space to copy the function's
code. Only define very small functions inside your class definition!
A function with a _prototype_ in the class definition still has access
to all parts of the class. The function code is defined _outside_ the
class definition. The compiler must be told that such code belongs to
the class, so "classname::" must precede the function name. This isn't
necessary if the code appears inside the class definition.
void
stack::push( int x )
{
if (size < 99)
a[ size++ ] = x;
else {
cerr << "stack:push() called with a full stack\n";
exit(1);
}
}
Using Class Functions
Here's an example of using the stack:
main()
{
stack s;
s.push(5);
s.push(7);
s.push(10);
while (! s.empty())
cout << "popping " << s.pop() << "\n";
}
The output is
popping 10
popping 7
popping 5
A class function is used just like a field within a structure. If
function `f' is defined in class `myclass' which has an instance `x',
it is called as
myclass x; // x is an instance of myclass
x.f(); // call the function f() defined in myclass
If we have a _pointer_ to a class instance, we use the other notation:
myclass *p; // p is a pointer to an instance of myclass
p = new myclass; // allocate an instance and point p to it
p->f(); // call f()
Function Calls and Instances
This is important to understanding C++. Read this section!
When a class function is called, there is an instance of the class
associated with that call. Above, x.f() had instance x associated
with the call, while p->f() had the instance pointed to by p (i.e. the
instance *p) associated with the call.
Inside the function, class variables are referred to. Above, push()
refers to array `a' and integer `size'. These are the class
variables that are stored in the instance that is associated with the
function call. That is, in the call to s.push(), the push()
function refers to the variables `s.a' and `s.size'.
As a further example, suppose we have two stacks:
stack s;
stack t;
s.push(5);
t.push(9);
In the call to s.push(), the push() function refers to `s.a' and
`s.size', while in the call to t.push(), the push function refers to
`t.a' and `t.size'.
The Special Variable `this'
The compiler doesn't really create two separate pieces of code, one
for s.push() and the other for t.push(). It uses the same code, but
instantiates a special variable called `this' that points to the
instance associated with the function call. So your code
void stack::push( int x )
{
if (size < 99)
a[ size++ ] = x;
}
is really implemented by the compiler as
void stack::push( stack *this, int x )
{
if ((this->size) < 99)
(this->a)[ (this->size)++ ] = x;
}
and your function calls
s.push(5)
t.push(7)
p->push(9)
are really implemented by the compiler as
push( &s, 5 );
push( &t, 7 );
push( p, 9 );
For example, in the elevator assignment you'll occasionally see the
variable `this' being used.
void Floor::request_elevator( Floor *dest_floor )
{
controller->request_elevator( this, dest_floor );
}
In the function above, the Floor::request_elevator() takes a request
to go to a particular destination floor. A call like
Floor *f1, *f2;
f1->request_elevator( f2 );
puts in a request for an elevator to go from floor *f1 to floor *f2.
This request is passed on to the controller, supplying `this' as an
additional argument. `this' is actually `f1', so the call to
controller->request_elevator( this, dest_floor );
supplies both the source floor (`this', which is f1) and the
destination floor (`dest_floor', which is f2).
I/O in C++
Output is done like
cout << ... << ... << ... ;
where ... is a numeric expression, a string, or a class instance that
has an output method defined for it (see next week's tutorial for output
methods). Don't forget the semicolon at the end of this statement!
Output to the standard error stream is done like
cerr << ... << ... << ... ;
Input is done like
cin >> x;
where x is a variable that has an input method defined. This is true
of ints, floats, and chars. For other types of variable, you might
have to define your own input method. Look up "operator>>" in a C++
book to see how to do this.
For example, to request an integer from the user:
cout << "Enter an integer: ";
cin >> x;