COMP2004
Programming Practice
2002 Summer School


Kevin Pulo
School of Information Technologies
University of Sydney


(page 1)


Classes





(page 2)


Grouping Data


struct Student {
std::string sid;
std::vector courses;
}; // The semicolon is needed
Student s;
s.sid = "9222194";
s.courses.push_back("comp2004");


(page 3)


Pointers to structs


Student *sp = &s;
(*sp).sid = "9222194";
(*sp).courses.push_back("comp2004");



Student *sp = &s;
sp->sid = "9222194";
sp->courses.push_back("comp2004");


(page 4)


The List Class


struct Node {
int number;
Node *next;
};

class List {
private:
Node *head;
public:
// we'll fill this in as we go
}; // The semicolon is needed


(page 5)


Constructors




(page 6)


Default Constructor


class List {
private:
Node *head;
public:
List();
}


(page 7)


Method code


class List {
private:
Node *head;
public:
List() {
head = NULL;
}
}


(page 8)


Method code


class List {
private:
Node *head;
public:
List();
}

List::List() {
head = NULL;
}


(page 9)


Constructor initialisers


List::List() : head(NULL) {
}


(page 10)


Other Constructors




(page 11)


Copy Constructor


List::List(const List &o) {
if (o.head == NULL) head = NULL;
else {
head = new Node;
head->number = o.head->number;
for (Node *c1=head,*c2=o.head;
c2;c1=c1->next,c2=c2->next) {
c1->next = new Node;
c1->next->number = c2->number;
}
c1->next = NULL; } }


(page 12)


Destructor




(page 13)


List Destructor


List::~List() {
Node *c = head;
while (c) {
Node *remove = c;
c = c->next;
delete remove;
}
}


(page 14)


Assignment




(page 15)


Assignment Operator


List& List::operator=(const List &o) {
if (this == &o) return *this;
Node *c = head;
while (c) {
Node *r = c;
c = c->next; delete r;
}
if (o.head == NULL) head = NULL;
else {
// insert rest of copy code
} return *this; }


(page 16)


A Problem




(page 17)


Structs and Classes




(page 18)


Node Constructor


Node::Node(int val) : number(val),
next(NULL) {
}
head = new Node;
head->number = o.head->number;
head = new Node(o.head->number);


(page 19)


Another Node Constructor


Node::Node(int val, Node *next)
: number(val), next(next) {
}
head = new Node(o.head->number,
o.head->next);


(page 20)


Merging the Constructors


Node::Node(int val, Node *next = NULL)
: number(val), next(next) { }
head = new Node(o.head->number,
o.head->next);
head = new Node(o.head->number,
NULL);
head = new Node(o.head->number);


(page 21)


More default parameters


Node::Node(int val = 0, Node *next
= NULL) : number(val), next(next) { }
head = new Node(o.head->number,
o.head->next);
head = new Node(o.head->number,
NULL);
head = new Node(o.head->number);
head = new Node();


(page 22)


Node Copying


Node* Node::deep_copy() {
Node *r = new Node(number);
for (Node *c1 = r, *c2 = next; c2;
c1 = c1->next, c2 = c2->next) {
c1->next = new Node(c2->number);
}
return r;
}


(page 23)


New Copy Constructor


List::List(const List &o) {
head = o.head->deep_copy();
}


(page 24)


New Copy Constructor


List::List(const List &o) {
if (o.head)
head = o.head->deep_copy();
else
head = NULL;
}


(page 25)


Node Copying


Node* Node::deep_copy(Node *n) {
if (n == NULL) return NULL;
Node *r = new Node(n->number);
for (Node *c1 = r, *c2 = n->next; c2;
c1 = c1->next, c2 = c2->next) {
c1->next = new Node(c2->number);
}
return r;
}


(page 26)


New Copy Constructor


List::List(const List &o) {
head = Node::deep_copy(o.head);
}


(page 27)


Node Deletion



void Node::delete_chain(Node *n) {
while (n != NULL) {
Node *remove = n;
n = n->next;
delete remove;
}
}


(page 28)


New Destructor


List::~List() {
Node::delete_chain(head);
}


(page 29)


Node Struct


class Node {
public:
int number;
Node *next;
Node(int val = 0, Node *next = NULL)
: number(val), next(next) { }
static Node* deep_copy(Node *n);
static void delete_chain(Node *n);
};


(page 30)


New Assignment Operator


List& List::operator=(const List &o) {
if (this == &o) return *this;
Node::delete_chain(head);
head = Node::deep_copy(o.head);
return *this;
}


(page 31)


Copying Aside




(page 32)


Inserting An Element


void List::insert_at_front(int val) {
Node *node = new Node(val);
node->next = head;
head = node;
}
void List::insert_at_front(int val) {
head = new Node(val, head);
}


(page 33)


Iterators




(page 34)


Simple Iterator


class Iterator {
friend List;
private:
Node *node;
public:
Iterator() : node(NULL) { };
Iterator(Node *n) : node(n) { };

int& operator*() {
return node->number;
}

(page 35)


Simple Iterator


Iterator& operator++() {
node = node->next;
return *this;
}

Iterator operator++(int) {
Iterator result = *this;
++(*this);
return result;
}

(page 36)


Simple Iterator


bool operator==(const Iterator &o)
const {
return node == o.node;
}

bool operator!=(const Iterator &o)
const {
return node != o.node;
}
};


(page 37)


Const correctness





(page 38)


Accessing Iterators


Iterator List::begin() {
return Iterator(head);
}
Iterator List::end() {
return Iterator();
}













































(page 39)


Test Code


int main() {
List list;
for (int i = 0; i < 10; ++i)
list.insert_at_front(i);

for (Iterator i=list.begin(); i!=list.end(); ++i)
*i *= 5;

for (Iterator i=list.begin(); i!=list.end(); ++i)
std::cout << *i << std::endl;
}


(page 40)


File layout



g++ -Wall -g -c list.cc

g++ -Wall -g -o listprog list.o main.o


(page 41)


Include guards


#ifndef LIST_HH_INCLUDED
#define LIST_HH_INCLUDED
// rest of file goes here
#endif




























































































(page 42)