Object-Oriented Programming in C++ with Dr. Ian Reid - Course Overview

B16 Software Engineering

B16 Software Engineering

Dr Ian Reid

4 lectures, Hilary Term

http://www.robots.ox.ac.uk/~ian/Teaching/B16

Object Oriented Programming

Object-oriented programming

•

Introduction to C++

─

classes

─

methods, function and operator overloading

─

constructors, destructors

─

program organisation

•

Data hiding

─

public and private data, accessor methods, encapsulation

•

Inheritance

─

Polymorphism

•

Templates

─

Standard Template Library; Design Patterns

Learning Outcomes

Learning Outcomes

•

The course will aim to give a good understanding of basic design

methods in object-oriented programming, reinforcing principles with

examples in C++.  Specifically, by the end of the course students

should

:

–

understand concepts of and advantages of object-oriented design

including:

–

Data hiding

–

Inheritance and polymorphism

–

Templates

–

understand how specific object oriented constructs are

implemented using C++

–

Be able to understand C++ programs

–

Be able to write small C++

Texts

Texts

•

Lipmann and Lajoie, 

C++ Primer,

Addison-Wesley, 2005.

•

Goodrich et al., 

Data structures and

algorithms in C++

, Wiley, 2004

•

Stroustrup, 

The C++ Programming

Language

, Addison-Wesley, 2000

•

Meyers, 

Effective C++

, Addison-

Wesley, 1998

•

Gamma et al., 

Design Patterns:

elements of reusable object-oriented

software, 

Addison-Wesley, 1995

Top down design

Top down design

•

Revisit ideas from Structured Programming

•

Want to keep in mind the general principles

–

Abstraction

–

Modularity

•

Architectural design: identifying the building blocks

•

Abstract specification: describe the data/functions and

their constraints

•

Interfaces: define how the modules fit together

•

Component design: recursively design each block

Procedural vs Object-oriented

Procedural vs Object-oriented

•

Object-oriented programming:

–

C

o

l

l

a

b

o

r

a

t

i

n

g

o

b

j

e

c

t

s

c

o

m

p

r

i

s

i

n

g

c

o

d

e

+

d

a

t

a

–

Object

 encapsulates related data and functions

–

Object Interface 

defines how an object can be

interacted with

Object Oriented Concepts

•

Object/class

─

Class encapsulates related data with the functions that act on the

data. This is called a 

class. 

 An 

object

 is an instance (a variable

declared for use) of a class.

•

Information hiding

─

The ability to make object data available only on a “need to know”

basis

•

Interface

─

Explicit separation of the description of how an object is used,

from the implementation details

•

Inheritance

─

The ability to create class hierarchies, such that the inheriting

class (super-class) is an instance of the ancestor class

•

Polymorphism

─

The ability of objects in the same class hierarchy to respond in

tailored ways to the same events

Classes

•

C++ predefines a set of atomic types

─

bool, char, int, float, double

•

C++ provides mechanism for building compound data

structures; i.e. 

user-defined

 types

─

class (c.f. struct in C)

─

class generalises the notion of struct

─

encapsulates related data and functions on that data

•

C++ provides mechanisms so that user-defined types

can behave just like the predefined types

•

Matlab also supports classes

•

A 

class

 (struct in C) is a 

user-defined data type 

which

encapsulates related data into a single entity.  It defines

how a variable of this type will look (and behave)

class Complex {

public:

double re, im;

};

•

Don’t confuse with creating an instance (i.e. declaring)

int i;

Complex z;

C++ classes

Class definition

Create a variable (an instance) of this type

•

Represent current state as, say, a

triple of numbers and a bool,

(position, velocity, mass, landed)

•

Single variable represents all

numbers

─

Better abstraction!

class State {

  public:

  double pos, vel, mass;

  bool landed;

};

State s;

Example:  VTOL state

Accessing class members

State s;

s.pos = 1.0;

s.vel = -20.0;

s.mass = 1000.0;

s.landed = false;

s.pos = s.pos +

s.vel*deltat;

Thrust =

ComputeThrust(s);

•

In Matlab introduce

structure fields

without declaration

s.pos = 1.0;

s.vel = -20.0;

…

Thrust =

ComputeThrust(s);

Methods

•

In C++ a class encapsulates related data and functions

•

A class has both data fields and functions that operate

on the data

•

A class member function is called a method in the

object-oriented programming literature

Example

class Complex {

public:

double re, im;

double Mag() { return sqrt(re*re + im*im); }

double Phase() { return atan2(im, re); }

};

Complex z;

cout << “Magnitude=“ << z.Mag() << endl;

•

Call method using dot operator

•

Notice that 

re

 and 

im

 do not need 

z.

z 

is implicitly passed to the function via the

this 

pointer

Information hiding / encapsulation

•

Principle of encapsulation is that software components

hide the internal details of their implementation

•

In procedural programming, treat a function as a black

box with a well-defined interface

─

Need to avoid side-effects

─

Use these functions as building blocks to create programs

•

In object-oriented programming, a class defines a black

box data structure, which has

─

Public interface

─

Private data

•

Other software components in the program can only

access class through well-defined interface, minimising

side-effects

Data hiding example

class Complex {

public:

double Re() { return re; }

double Im() { return im; }

double Mag() { return sqrt(re*re + im*im);}

double Phase() { return atan2(im, re);

}

private:

double re, im;

};

•

Access to private members only through public interface

Complex z;

cout << “Magnitude=“ << z.Mag() << endl;

cout << “Real part=“ << z.Re() << endl;

•

R

e

a

d

o

n

l

y

a

c

c

e

s

s

:

a

c

c

e

s

s

o

r

m

e

t

h

o

d

Data hiding example, ctd

class Complex {

public:

double Re() { return r*cos(theta); }

double Im() { return r*sin(theta); }

double Mag() { return r;}

double Phase() { return theta; }

}

private:

double r, theta;

};

Complex z;

cout << “Magnitude=“ << z.Mag() << endl;

cout << “Real part=“ << z.Re() << endl;

Unchanged!

!

Internal implentation

now in polar coords

Constructor

•

If we can no longer say

z.re = 1.0;

How can we get values into an object?

•

Whenever a variable is created (declared), memory

space is allocated for it

•

It 

might

 be initialised

─

int i;

─

int i=10;

─

int i(10);

•

In general this is the work of a 

constructor

Constructor

•

The constructor is a special function with the same

name as the class and no return type

Complex(double x, double y) {

 re = x; im = y;

}

or

Complex(double x, double y) : re(x), im(y) {}

Data hiding example

class Complex {

public:

Complex(double x, double y) { re = x; im = y; }

double Re() { return re; }

double Im() { return im; }

double Mag() { return sqrt(re*re + im*im);}

double Phase() { return atan2(im, re);

}

private:

double re, im;

};

•

Interface now includes constructor

Complex z(10.0, 8.0);

cout << “Magnitude=“ << z.Mag() << endl;

cout << “Real part=“ << z.Re() << endl;

•

Declare (instantiate) an object of type Complex, setting its value to

10 + j 8

Data hiding example, ctd

class Complex {

public:

Complex(double x, double y) {

r = sqrt(x*x + y*y);

theta = atan2(y,x);

}

double Re() { return r*cos(theta); }

double Im() { return r*sin(theta); }

double Mag() { return r;}

double Phase() { return theta; }

}

private:

double r, theta;

};

Complex z(10.0,8.0);

cout << “Magnitude=“ << z.Mag() << endl;

cout << “Real part=“ << z.Re() << endl;

Unchanged!

!

Internal implentation

now in polar coords

Copy Constructor

•

The copy constructor is a particular constructor

that takes as its single argument an instance of the

class

•

Typically it copies its data into the new instance

─

The compiler creates one by default that does exactly

this

─

Not always what we want; need to take extra care when

dealing with objects that contain dynamically allocated

components

Complex(Complex& z) {

 re = z.Re(); im = z.Im();

}

Complex(Complex& z) : re(z.Re()), im(z.Im())

{}

class Complex {

public:

Complex

(double x,

 double y)…

Complex

(Complex& z)…

double 

Re

() …

double 

Im

() …

double 

Mag

() …

double 

Phase

() …

private:

double r, theta;

};

Data hiding – summary

class Complex {

public:

Complex

(double x,

 double y)…

Complex

(Complex& z)…

double 

Re

() …

double 

Im

() …

double 

Mag

() …

double 

Phase

() …

private:

double re, im;

};

Cartesian

Polar

•

Interface to the program remains unchanged

Complex z(10.0,8.0);

cout << “Magnitude=“ << z.Mag() << endl;

cout << “Real part=“ << z.Re() << endl;

C++ program organisation

•

Complex.h

class Complex {

public:

Complex(double x, double y);

double Re();

double Im();

double Mag();

double Phase();

private:

double re, im;

};

C++ program organisation

•

Complex.cpp

•

Scoping operator “::” makes it explicit that we are referring to

methods of the Complex class

#include “Complex.h”

Complex::Complex(double x, double y) {

re = x; im = y;

}

double Complex::Re() { return re; }

double Complex::Im() { return im; }

double Complex::Mag() {

return sqrt(re*re+im*im);

}

double Complex::Phase() { return atan2(im,re); }

const

•

An object (variable) can be declared as 

const

 meaning the

compiler will complain if its value is ever changed

const int i(44);

i = i+1;  /// compile time error!

•

It is good practice to declare constants explicitly

•

It is good practice to declare formal parameters 

const

 if the

function does not change them

int foo(BigClass& x);

versus

int foo(const BigClass& x);

const

•

Why mention this now?

─

In C++ const plays an important part in defining the class

interface

•

Class member functions can (sometimes 

must

) be declared

as const

─

Means they do not change the value of the calling object

─

Enforced by compiler

•

Notice that as far as code in a class member function is

concerned, data fields are a bit like global variables

─

They can be changed in ways that are not reflected by the

function prototype

─

Use of const can control this somewhat

const

class Complex {

public:

Complex(double x, double y) { re = x; im = y; }

double Re() { return re; }

double Im() { return im; }

double Mag() { return sqrt(re*re + im*im);}

double Phase() { return atan2(im, re);

}

private:

double re, im;

};

const Complex z(10.0, 8.0);

cout << “Real part=“ << z.Re() << endl;

•

This code will generate an error

const

class Complex {

public:

Complex(double x, double y) { re = x; im = y; }

double Re() const { return re; }

double Im() const { return im; }

double Mag() const { return sqrt(re*re + im*im);}

double Phase() const { return atan2(im, re);

}

private:

double re, im;

};

const Complex z(10.0, 8.0);

cout << “Real part=“ << z.Re() << endl;

•

This code should now compile

Function overloading

•

C++ allows several functions to share the same

name, but accept different argument types

void foo(int x);

void foo(int &x, int &y);

void foo(double x, const Complex c);

•

The function name and types of arguments yield a

signature that tells the compiler if a given function call

in the code is valid, and which version is being

referred to

Function overloading

•

We can define 

exp

 for the 

Complex

 class

#include <cmath>

Complex exp(const Complex z)

{

double r = exp(z.Re());

Complex zout(r*cos(z.Im()),

 r*sin(z.Im()));

return zout;

}

Methods versus functions

•

When should we use a member function and when

should we use a non-member function?

•

exp(z) 

versus

 z.exp()

•

Consider carefully how it will be used

•

 Does it modify the instance?

•

Which presents the most natural interface?

•

In this case I would go for 

exp(z)

•

Arithmetic

•

Relational

•

Boolean

•

Assignment

•

I/O streaming  

<<    >>

Operators

+  -  *  /  %

==  !=

<   >   <=   >=

&&  ||   !

=

•

Suppose we want to add two Complex variables

together

•

Could create a function:

Complex Add(const Complex z1, const Complex z2) {

Complex zout(z1.Re()+z2.Re(),

 z1.Im()+z2.Im());

return zout;

}

•

But it would it be much cleaner to write:

Complex z3;

z3 = z1+z2;

•

Boolean

•

Assigment

Operator overloading

•

C++ exposes the definition of the 

infix

 notation 

a+b

as a function (

prefix

 notation)

operator+(a,b)

•

Since an operator is just a function, we can overload

it

Complex operator+(const Complex z1,

 const Complex z2) {

Complex zout(z1.Re()+z2.Re(),

 z1.Im()+z2.Im());

return zout;

}

•

Hence we can write

Complex z3;

Z3 = z1+z2;

Operator overloading

operator=

•

z3=z1+z2

•

We have assumed that the assignment operator

(operator=) exists for the Complex class.

•

Define it like this:

Complex& Complex::operator=(const Complex& z1)

{

re = z1.Re();

im = z1.Im();

return *this;

}

operator=

•

Defn of operator= is one of the few common uses for

the “this” pointer.

•

z2=z1 

is shorthand for

z2.operator=(z1)

•

operator=

 must be a member function

•

The left hand side (here 

z2

) is implicitly passed in to

the function

•

Function returns a reference to a 

Complex.  

This

is so we can write 

z3=z2=z1;

z3.operator=(z2.operator=(z1));

•

C++ does no

array bounds

checking (seg

fault)

•

Create our own

safe array class

by overloading the

array index

operator 

[]

Operator overloading

class SafeFloatArray {

public:

…

float& operator[](int i)

{

if ( i<0 || i>=10 ) {

cerr <<

“Oops!” << endl;

exit(1);

}

return a[i];

}

private:

float a[10];

};

•

Putting it all together: program to calculate frequency

response of transfer function H(jw) = 1/(1+jw)

•

Three files, two modules

─

Complex.h and Complex.cpp

─

Filter.cpp

•

The first two files define the Complex interface (.h)

and the method implementations

% g++ -c Complex.cpp

% g++ -c Filter.cpp

% g++ -o Filter Complex.o Filter.o -lm

Complete example

Compile source to

object files

Link object files together with maths library (-lm) to

create executable

// Complex.h

// Define Complex class and function prototypes

//

class Complex {

 public:

  Complex(const double x=0.0, const double y=0.0);

  double Re() const;

  double Im() const;

  double Mag() const;

  double Phase() const;

  Complex &operator=(const Complex z);

 private:

  double _re, _im;

};

// Complex maths

Complex operator+(const Complex z1, const Complex z2);

Complex operator-(const Complex z1, const Complex z2);

Complex operator*(const Complex z1, const double r);

Complex operator*(const double r, const Complex z1);

Complex operator*(const Complex z1, const Complex z2);

Complex operator/(const Complex z1, const Complex z2);

#include <cmath>

#include <iostream>

#include "Complex.h"

// First implement the member functions

// Constructors

Complex::Complex(const double x, const double y) : _re(x), _im(y) {}

Complex::Complex(const Complex& z) : _re(z.Re()), _im(z.Im()) {}

double Complex::Re() const { return _re; }

double Complex::Im() const { return _im; }

double Complex::Mag() const { return sqrt(_re*_re + _im*_im); }

double Complex::Phase() const { return atan2(_im, _re); }

// Assignment

Complex& Complex::operator=(const Complex z)

{

  _re = z.Re();

  _im = z.Im();

  return *this;

}

// Now implement the non-member arithmetic functions

// Complex addition

Complex operator+(const Complex z1, const Complex z2)

{

  Complex zout(z1.Re()+z2.Re(), z1.Im()+z2.Im());

  return zout;

}

// Complex subtraction

Complex operator-(const Complex z1, const Complex z2)

{

  Complex zout(z1.Re()-z2.Re(),

               z1.Im()-z2.Im());

  return zout;

}

// scalar multiplication of Complex

Complex operator*(const Complex z1, const double r)

{

  Complex zout(r*z1.Re(), r*z1.Im());

  return zout;

}

Complex operator*(const double r, const Complex z1)

{

  Complex zout(r*z1.Re(), r*z1.Im());

  return zout;

}

// Complex multiplication

Complex operator*(const Complex z1, const Complex z2)

{

  Complex zout(z1.Re()*z2.Re() - z1.Im()*z2.Im(),

               z1.Re()*z2.Im() + z1.Im()*z2.Re());

  return zout;

}

// Complex division

Complex operator/(const Complex z1, const Complex z2)

{

  double denom(z2.Mag()*z2.Mag());

  Complex zout((z1.Re()*z2.Re() + z1.Im()*z2.Im())/denom,

               (z1.Re()*z2.Im() - z1.Im()*z2.Re())/denom);

  return zout;

}

// end of file Complex.cpp

#include <iostream>

#include "Complex.h"

using namespace std;

Complex H(double w)

{

  const Complex numerator(1.0);

  const Complex denominator(1.0, 0.1*w);

  Complex z(numerator/denominator);

  return z;

}

int main(int argc, char *argv[])

{

  double w=0.0;

  const double stepsize=0.01;

  Complex z;

  for (double w=0.0; w<100.0; w+=stepsize) {

    z = H(w);

    cout << w << " " << z.Mag() << " " << z.Phase() << endl;

  }

}

Object-oriented programming

•

An object in a programming context is an instance of a

class

•

Object-oriented programming concerns itself primarily

with the design of classes and the interfaces between

these classes

•

The design stage breaks the problem down into classes

and their interfaces

•

OOP also includes two important ideas concerned with

hierarchies of objects

─

Inheritance

─

polymorphism

Inheritance

•

Hierarchical relationships often arise between classes

•

Object-oriented design supports this through

 inheritance

•

An derived class is one that has the functionality of its

“parent” class but with some extra data or methods

•

In C++

class A : public B {

…

};

•

Inheritance encodes an “is a” relationship

Example

Inheritance

•

Inheritance is an “is a” relationship

─

Every instance of a derived class is also an instance of the

parent class

─

Example:

class Vehicle;

class Car : public Vehicle { … };

─

Every instance of a 

Car

 is also an instance of a 

Vehicle

─

A 

Car

 object has all the properties of a 

Vehicle

•

Don’t confuse this with a “contains” or “composition”

relationship.

class Vehicle {

Wheels w[];

};

Polymorphism

•

Polymorphism

, Greek for “many forms”

•

One of the most powerful object-oriented concepts

•

Ability to hide alternative implementations behind a

common interface

•

Ability of objects of different types to respond in different

ways to a similar event

•

Example

─

TextWindow and GraphicsWindow, redraw()

Implementation

•

In C++ run-time polymorphism invoked by the

programmer via 

virtual functions

class Window {

…

virtual void redraw();

};

Example

class A

class B

class C

•

Consider simple hierarchy

as shown

•

A is base class

•

B and C both derive from A

•

Every instance of a B

object is also an A object

•

Every instance of a C

object is also an A object

Example

#include <iostream>

using namespace std;

class A {

  public:

void func() {

cout << “A\n”;

}

};

class B : public A {

  public:

void func() {cout<<"B\n"; }

};

class C: public A {

  public:

void func() {cout << "C\n"; }

};

void callfunc(A param)

{

param.func();

}

int main(int argc, 

char

*

argv[])

{

A x;

B y;

C z;

x.func();

y.func();

z.func();

callfunc(x);

callfunc(y);

callfunc(z);

return 0;

}

Memory

CODE

DATA

machine code

global variables

STACK

local variable m

local variable 1

return location

return value n

return value 1

parameter x

parameter 1

…

…

…

Activation

record

Passing derived class objects into functions

Passing derived class objects into functions

Passing derived class objects into functions

class A

class B

class C

B y;

callfunc(y)

local variable m

local variable 1

return location

parameter (y|A)

…

c

allfunc activation

record

void callfunc(A param)

{

param.func();

}

•

Callfunc takes a value parameter of class A

•

It expects an object of the right size to be on

the stack

•

The call above is legitimate but only the bit of y

that is an A will be copied onto the stack

•

Once “inside” the function the parameter can

only behave as an A

RTTI and Polymorphism

#include <iostream>

using namespace std;

class A {

  public:

virtual void func() 

{

cout << “A\n”;

}

};

class B : public A {

  public:

void func() {cout<<"B\n"; }

};

class C: public A {

  public:

void func() {cout << "C\n"; }

};

void callfunc(A& param)

{

param.func();

}

int main(int argc, 

char

*

argv[])

{

A x;

B y;

C z;

x.func();

y.func();

z.func();

callfunc(x);

callfunc(y);

callfunc(z);

return 0;

}

Passing derived class objects into functions

class A

class B

class C

B y;

callfunc(y)

local variable m

local variable 1

return location

param (&y)

…

c

allfunc activation

record

void callfunc(A& param)

{

param.func();

}

•

Callfunc takes a reference to an object of class A

•

A reference is just a memory address

•

The call above is legit because objects of type B

are also of type A

•

Dereferencing param leads to y

•

Y can identify itself as being of class B, and so

can behave like a B if we want it to

•

Declaring func() to be virtual invokse this

beahviour

y

Summary

•

A virtual function called from an object that is either a

─

Reference to a derived class

─

Pointer to a derived class

•

Performs run-time type identification on the object that

invoked the call, and will call the appropriate version

class A

class B

class C

If the object is of type A then call A’s func()

If the object is of type B then call B’s func()

If the object is of type C then call C’s func()

Abstract Base Class

•

If class 

A

 defines func() as

virtual void func() = 0;

then 

A

 has no implementation of 

func()

•

class 

A

 is then an 

abstract base class

─

It is not possible to create an instance of class 

A

, only

instances derived classes, 

B

 and 

C

─

class 

A

 defines an

 interface 

to which all derived

classes must conform

•

Use this idea in designing program components

─

Specify interface, then have a guarantee of

compatibility of all derived objects

Abstract Base Class

#include <iostream>

using namespace std;

class A {

  public:

virtual void func()= 0;

};

class B : public A {

  public:

void func() {cout<<"B\n"; }

};

class C: public A {

  public:

void func() { cout << "C\n";

}

};

void callfunc(A param)

{

param.func();

}

int main(int argc, 

char

*

argv[])

{

A x;

B y;

C z;

x.func();

y.func();

z.func();

callfunc(x);

callfunc(y);

callfunc(z);

return 0;

}

Another example

•

Consider a vector graphics drawing package

•

Consider base class “Drawable”

─

A graphics object that knows how to draw itself on the screen

─

Class hierarchy may comprise lines, curves, points, images, etc

class Drawable {

…

virtual void Draw() = 0;

};

class Line : public Drawable { … };

•

Program keeps a list of objects that have been created and on

redraw, displays them one by one

•

This is implemented easily by a loop

for (int i=0; i<N; i++) {

obj[i]->Draw();

}

Must implement

Draw();

Abstract base class: example

•

An abstract base class cannot be instantiated itself

•

It is used to define the interface

•

Consider spreadsheet

class Cell {

virtual double Evaluate() = 0;

};

class Spreadsheet {

private:

Cell& c[100][100];

};

•

By specifying the interface to Cell, we can implement

Spreadsheet independently of the various types of Cell.

Abstract base class

•

Recall Euler’s method in “Structured Programming”

•

Can achieve similar abstraction in a clean way using an

abstract base class and polymorphism

class Euler {

  public:

Euler(Func &f);

void Simulate(double x, double step, double time);

  private:

Func fn;

};

Abstract base class

Euler::Euler(Func &f) : fn(f) {};

void Euler::Simulate(double x, double step, double time)

{

for (int t=0; t<time; t+=step) {

   x = x + step*fn(x,t);

   cout << x << endl;

   }

return;

}

…

XdotPlusX y;

Euler e(y);

e.Simulate();

Abstract base class

class Func {

  public:

virtual double dx_by_dt(double x, double t) = 0;

};

class XdotPlusX : public Func {

  public:

double dx_by_dt(double x, double t) {

  return –x;

   }

};

class XdotPlusX2 : public Func {

  public:

double dx_by_dt(double x, double t) {

  return –x*x;

    }

};

Templates

•

Templating is a mechanism in C++ to create classes in which one or

more types are 

parameterised

•

Example of 

compile-time

 polymorphism

class BoundedArray {

public:

float& operator[](int i) {

if (i<0 || i>=10) {

cerr << “Access out of bounds\n”;

return 0.0;

} else {

return a[i];

}

}

private:

float a[10];

};

Templates

template <class Type>

class BoundedArray {

public:

Type& operator[](int i) {

if (i<0 || i>=10) {

cerr << “Access out of bounds\n”;

return Type(0);

} else {

return a[i];

}

}

private:

Type a[10];

};

BoundedArray<int> x;

BoundedArray<Complex> z;

Templates

template <class Type, int Size>

class BoundedArray {

public:

Type& operator[](int i) {

if (i<0 || i>=Size) {

cerr << “Access out of bounds\n”;

return Type(0);

} else {

return a[i];

}

}

private:

Type a[Size];

};

BoundedArray<int,10> x;

BoundedArray<Complex,40> z;

Design patterns

•

Programs regularly employ similar design solutions

•

Idea is to standardise the way these are implemented

─

Code re-use

─

Increased reliability

─

Fewer errors, shorter development time

•

An array is special case of a 

container type

─

Way of storing a collection of possibly ordered elements.

─

List, stack, queue, double-ended list, etc

•

Templates in C++ offer a way of providing libraries to

implement these standard containers

Standard Template Library

•

C++ provides a set of container classes

─

Standard way of representing and manipulating container types

─

eg, methods insert(),  append(), size(), etc

•

STL supports

─

Stack (FILO structure)

─

List (efficient insertion and deletion, ordered but not indexed)

─

Vector (extendible array)

─

others

STL example: vector

•

std::vector<Type> 

is an extendible array

•

It can increase its size as the program needs it to

•

It can be accessed like an ordinary array (eg 

v[2]

)

•

It can report its current size

─

v.size()

•

You can add an item to the end without needing to know

how big it is

─

v.push_back(x)

#include<vector>

int main() {

    std::vector<int> v;

    for (int i=0; i<20; i++) v.push_back(i);

    for (int i=0; i<v.size(); i++)

      std::cout << v[i] << std::endl;

}

STL vector

•

To create a new STL vector of a size specified at 

run-

time

int size;

std::vector<Complex> z;

std::cin >> size;

z.resize(size);

z[5] = Complex(2.0,3.0);

STL vector, continued

•

To create a two dimensional array at 

run-time

int width, height;

std::vector< std::vector<int> > x;

x.resize(height);

for (int i=0; i<height; i++)

x[i].resize(width);

x[2][3] = 10;

…

STL vector, continued

•

The vector class implements a number of methods for accessing and

operating on the elements

─

vector::front 

- Returns reference to first element of vector.

─

vector::back 

- Returns reference to last element of vector.

─

vector::size 

- Returns number of elements in the vector.

─

vector::empty 

- Returns true if vector has no elements.

─

vector::capacity 

- Returns current capacity (allocated memory) of vector.

─

vector::insert 

- Inserts elements into a vector (single & range), shifts later

elements up. O(n) time.

─

vector::push_back 

- Appends (inserts) an element to the end of a vector,

allocating memory for it if necessary. O(1) time.

─

vector::erase 

- Deletes elements from a vector (single & range), shifts later

elements down. O(n) time.

─

vector::pop_back 

- Erases the last element of the vector, O(1) time. Does

not usually reduce the memory overhead of the vector. O(1) time.

─

vector::clear 

- Erases all of the elements. (This does not reduce capacity).

─

vector::resize 

- Changes the vector size. O(n) time

.

Iterators

•

A standard thing to want to do with a collection of data

elements is to iterate over each

─

for (int i=0; i<v.size(); i++)

•

Not all container types support indexing

─

A linked list has order, but only 

relative order

•

An

 iterator

 is a class that supports the standard

programming pattern of iterating over a container type

std::vector<int> v;

std::vector<int>::iterator i;

for (it=v.begin(); it!=v.end(); it++) …

•

An iterator encapsulates the internal structure of how the

iteration occurs

Concept summary

•

Classes

─

Encapsulate related data and functions together

•

Interface

─

Clearly define mechanisms for how program can interact with an

object of a given class

─

Minimise side-effects

─

Hide private data, const constant data and functions

•

Inheritance

─

Class hierarchies

─

Use of abstract base class to create a generic interface

•

Polymorphism

─

Ability of objects in the same class hierarchy to respond in

tailored ways to the same event

•

Templates

─

The ability to create generic code that is type agnostic until

instantiated at compile time

Complete example

•

Design a program to compute a maze

─

User-specified size

─

Print it out at the end

•

Algorithm

─

Mark all cells unvisited

─

Choose a start cell

─

While current cell has unvisited neighbours

•

Choose one at random

•

Break wall between it and current cell

•

Recursively enter the chosen cell

Design data structures

•

Maze class

─

Compute method

─

Print method

─

Two dimensional array of Cells

•

Cell class

─

Accessor methods

─

Break wall methods

─

Wall flags

─

Visited flag

Cell class interface

class Cell {

 public:

  Cell();

  bool Visited();

  void MarkVisited();

  bool BottomWall();

  bool RightWall();

  void BreakBottom();

  void BreakRight();

private:

  bool bottomwall;

  bool rightwall;

  bool visited;

};

Maze class interface

class Maze {

public:

Maze(int width, int height);

void Compute(int x, int y);

void Print();

private:

int Rand(int n);

int H, W;

std::vector< std::vector<Cell> > cells;

};