C++ and OO
C++ classes and OO
More Examples
HW2
C++ for C Programmers by Ira Pohl
Objects
C++ for C Programmers by Ira Pohl
C++ and OO
What happens with a declaration
l
l
l
int i , j = 3;
Declares; allocates ; initializes
For a simple native type this happens
automatically via a stack
Constructor the OO function to do this
C++ for C Programmers by Ira Pohl
Quiz- what is printed
l
l
l
l
l
l
l
int main()
{ int i = 9, j = 3;
cout << i is << i << j is << j <<endl;
{ int i = j + 2;
cout << i is << i << j is << j <<endl;
cout << i is << i << j is << j <<endl;
}
C++ for C Programmers by Ira Pohl
Answer
l
i is 9 j is 3
i is 5 j is 3
i is 9 j is 3
C++ for C Programmers by Ira Pohl
Point and its constructor
class point{
public:
point(x=0.0, y = 0.0):x(x),y(y){} //constructor
double getx(){return x;}
void setx(double val){x = v;}
..
private:
double x, y;
};
//note class_name():initializer list syntax
C++ for C Programmers by Ira Pohl
This pointer --self-referential
l
Every class object has the implicit pointer
l
Keyword this associate with it.
We will use it in the next slide
C++ for C Programmers by Ira Pohl
A special method -constructor
l
point(){ x = y = 0.0;}
or
l point(){ this -> x = 0.0; this ->y = 0.0}
l Or best
l point():x(0.0),y(0.0){}
l
Default constructor the constructor whose
signature is void.
C++ for C Programmers by Ira Pohl
Use
l
point p, q, r; // all call constructor of void signature
C++ for C Programmers by Ira Pohl
Constructor overloading
l
It is useful to have multiple ways to initialize
an object like point.
point(double x, double y)
l {this -> x = x; this ->y = y;}
l
this used to disambiguate
C++ for C Programmers by Ira Pohl
Argument and member confusion
point(double x, double y)
l {this -> x = x; this ->y = y;}
l
This lets ambiguity be resolved x=x; would not work
l Better use initialization syntax
l point(double x, double y):x(x),y(y){}
l
C++ for C Programmers by Ira Pohl
More Constructors
Constructors: Initialize
Constructors: Convert
Constructors: Allocate
Also: constructors can check for correctness
C++ for C Programmers by Ira Pohl
Memory management
new - allocator -think malloc()
l delete deallocator think free()
l
Both work with a heap heap is dynamically
allocated memory unlike Java not
automatically garbage collected
C++ for C Programmers by Ira Pohl
Simple use of new
char* s = new char[size];//get off heap
l int *p = new int(9); // single int initialized
l delete [] s; //delete an array
l delete p; //delete single element
l
These will get used with dynamic data structures
in constructors and destructors
C++ for C Programmers by Ira Pohl
~ destructor
l
Deallocator when item goes out of scope
Syntax within class ~classname(){ }
Typical use is for calling delete to deallocate
to the heap what if you forget
l Answer: Bad manners -memory leak
l
C++ for C Programmers by Ira Pohl
Linked List p 168 section5.7
l
struct slistelem{ char data; slistelem* next;}
class slist{ //singly linked list
public:
slist():h(0){} //empty list
~slist() {release();} destructor
..more methods
private:
slistelem* h; //list head
}
l
l
l
l
l
l
l
C++ for C Programmers by Ira Pohl
Prepend to slist
l
l
l
l
l
l
l
l
void slist::prepend (char* c)
{
slistelem* temp = new slistelem;
assert (temp != 0);
temp -> next = h; //single link
temp -> data = c;
h = temp; //update h
}
C++ for C Programmers by Ira Pohl
~ destructor
slist::~slist()
l {
l
cout << destructor called << endl;
l
//just for demonstration debug
l
release(); //march thru list with
l
//deletes
l }
l
C++ for C Programmers by Ira Pohl
HW2 some ideas
l
HW2 : implement Dijkstra algorithm and use
a randomly generated graph to test it.
A simpler problem is to compute if a graph is
one connected component
Draw Unconnected graph
C++ for C Programmers by Ira Pohl
Unconnected graph
O
C++ for C Programmers by Ira Pohl
O
O
Connected graph
O
C++ for C Programmers by Ira Pohl
O
O
First draw a randomly generated
Graph
bool** graph;
l
srand(time(0));//seed rand()
l
graph = new bool*[size];
l
for(int i = 0; i <size; ++i)
l
graph[i] = new bool[size];
l //heap created 2 D array of Bool
l
C++ for C Programmers by Ira Pohl
Density is 0.19
l
l
l
l
for (int i = 0; i < size; ++i)
for(int j = i; j < size; ++j)
if (i == j) graph[i][j]= false; //no loops
else graph[i][j] = graph[j][i] = (prob() < 0.19);
C++ for C Programmers by Ira Pohl
Quiz:
l
If the density is 0 the graph has no ____
If the density is 1 the graph is c..
If the density is fixed say 0.1 then as the size
of the graph gets larger it is ____likely to be
connected.
C++ for C Programmers by Ira Pohl
Answer:
l
If the density is 0 the graph has no edges
If the density is 1 the graph is complete
If the density is fixed say 0.1 then as the size
of the graph gets larger it is more likely to be
connected.
C++ for C Programmers by Ira Pohl
The is_connected algorithm
l
//This algorithm is a form of breadth first search - first
implemented by the author in 1968 at SLAC.
//It was in PL1 and was a package of routines for
computational graph theory.
//See also the Wikipedia on Breadth First Search.
//The algorithm is_connected uses a Boolean matrix
representation of an undirected graph to determine if a
graph is connected.
C++ for C Programmers by Ira Pohl
Details
l
l
l
l
It starts with node 0 and determines which nodes can be reached
from this node
placing them in an open set and placing node 0 as the first node
of a connected component.
Each iteration adds one node to the closed set.
This stops with either no furter nodes reachable and
is_connected is false or all nodes being included in the closed
set.
The algorithm was published as a SLAC report and later a
generalizion was published by Hopcroft and Tarjan in 1973.
C++ for C Programmers by Ira Pohl
Is_connected
l
l
bool is_connected(bool *graph[], int size)
{
l
l
l
l
l
l
l
int old_size =0, c_size = 0;
bool* close = new bool[size];
bool* open = new bool[size];
for(int i = 0; i < size; ++i)
open[i] = close[i] = false;
open[0] = true;
C++ for C Programmers by Ira Pohl
At this point
Open set has node 0 on it
l Question would this work if other node is
selected
l
Nothing in closed set.
Each iteration will add one node to closed set
C++ for C Programmers by Ira Pohl
Add to close
l
l
l
l
l
while(c_size < size){
for (int i = 0; i < size; ++i){
old_size = c_size;
if (open[i] && (close[i] == false)){
close[i] = true; c_size++;
C++ for C Programmers by Ira Pohl
Add to open
for(int j = 0; j < size; ++j)
l
open[j] = open[j] || graph[i][j];
l
}
l
}
l
C++ for C Programmers by Ira Pohl
Are we done?
l
l
We are done if have all nodes in close set
Or if no nodes available in open set
if (c_size == size) return true;
if (old_size == c_size) return false;
}
}
C++ for C Programmers by Ira Pohl
L6 Lists
List and code
C++ for C Programmers by Ira Pohl
List Element
l
struct list_element{
list_element(int n = 0, list_element* ptr = 0):
d(n), next(ptr){}
int d;
list_element* next;
};
Or equivalently
l
l
class list_element{
public:
list_element(int n = 0, list_element* ptr = 0):
d(n), next(ptr){}
int d;
list_element* next;
};
C++ for C Programmers by Ira Pohl
Quiz
l
In the previous list_element constructor, what
is 0 used for?
C++ for C Programmers by Ira Pohl
Ans: Null Pointer
l
The zero value is the null pointer value.
Recall it is important in lists to test for null;
they are used as sentinel values.
C++11 - list_element* ptr =nullptr ;
l new keyword - type safe
l
C++ for C Programmers by Ira Pohl
List
l
class list{
public:
list():head(0), cursor(0){}
void prepend(int n); //insert at front value n
int get_element(){return cursor->d;}
void advance(){ cursor= cursor-> next;}
void print();
private:
list_element* head;
list_element* cursor;
};
C++ for C Programmers by Ira Pohl
prepend
l
void list::prepend(int n)
{ if (head == 0)//empty list case
cursor = head = new list_element(n,
head);
else//add to front -chain
head = new list_element(n, head);
}
C++ for C Programmers by Ira Pohl
Quiz : prepend(5)
l
Draw how prepend (5) would work.
Assume a two element list
C++ for C Programmers by Ira Pohl
-> 7 -> 3 ##
Answer
l
5 is on the front of the new list
Draw here----
C++ for C Programmers by Ira Pohl
Print() chaining
l
Void list:: print(){
list_element* h = head;
while(h != 0){//idiom for chaining
cout << h->d << ", ";
h = h -> next;
}
cout << "###" << endl;
}
Should know how to use recursion
Should know how to overload << for list
C++ for C Programmers by Ira Pohl
Use of list
l
int main()
{
list a, b;
a.prepend(9); a.prepend(8);
cout << " list a " << endl;
a.print();
for (int i = 0; i < 40; ++i)
b.prepend(i*i);
cout << " list b " << endl;
b.print();
}
What gets printed?
C++ for C Programmers by Ira Pohl
Q: What gets printed
l
Follow previous code
C++ for C Programmers by Ira Pohl
Ans:
l
Simulate here:(run)
C++ for C Programmers by Ira Pohl
More elaborate
class list{
public:
list():head(0), cursor(0){}
list(const int* arr, int n);
list(const list& lst);//copy constructor
...
~list(); //delete
private:
list_element* head;
list_element* cursor;
};
Deep copy v. referential copy
C++ for C Programmers by Ira Pohl
Deep: Pi is transcendental
C++ for C Programmers by Ira Pohl
Shallow: Moms pie is tasty
C++ for C Programmers by Ira Pohl
Deep v. Shallow
l
First we will examine the copy constructor. We
want to build an equivalent list that is a "deep"
copy.
A "shallow copy would be a referential copy where
the new list head would be the same value as the
old list head.
Shallow copy is a highly efficient form of copying
(why?) but has a more limited utility than a deep
copy(why?).
C++ for C Programmers by Ira Pohl
Copy constructor
l
list::list(const list& lst){
if (lst.head == 0)
{
head =0; cursor =0;
}
else
set up
for( cursor = lst.head; cursor != 0; )
{
chain and create
}
cursor = head;
}
}
C++ for C Programmers by Ira Pohl
More code
l
else
{
cursor = lst.head;
list_element* h = new list_element();
list_element* previous;
head = h;
h->d = lst.head->d;
previous = h;
C++ for C Programmers by Ira Pohl
Chain and create
l
for( cursor = lst.head; cursor != 0; )
{
h = new list_element();
h->d = cursor->d;
previous->next = h;
cursor = cursor->next;
previous = h;
}
cursor = head;
}
C++ for C Programmers by Ira Pohl
~ destructor
l
list::~list()
{
for( cursor = head; cursor != 0; )
{
cursor = head->next;
delete head;
head = cursor;
}
}
Here the destructor chains through the list
returning each list_element created by a
corresponding new.
C++ for C Programmers by Ira Pohl
Use this list
l
int main()
{
list a, b;
int data[10] = {3,4, 6, 7, -3, 5};
list d(data, 6);
list e(data, 10);
a.prepend(9); a.prepend(8);
cout << " list a " << endl;
a.print();
C++ for C Programmers by Ira Pohl
for (int i = 0; i < 40; ++i)
b.prepend(i*i);
cout << " list b " << endl;
b.print();
list c(b);
c.print();
d.print();
e.print();
}
Make sure you know where each constructor and
destructor is invoked. Also what is printed?
C++ for C Programmers by Ira Pohl
Dynamic data Structures in
STL
The standard template library has the
following data structures available and you
are free to use them in your problem:
l #include <vector>
l
can then use vector<type> name(size);
l
vector is the most used it is nearly
efficient as araw array and is safer and
expandable.
l
C++ for C Programmers by Ira Pohl
List is also available
#include <list>
l gets you doubly linked lists
l
C++ for C Programmers by Ira Pohl
C++ More
HW2 Questions?
l
l
l
How to average in disconnected graphs
ignore them for averaging
Density is for entire set of edges does not mean node degree is
uniform; also for small graphs a low density leads to graph being
disconnected.
Review end of chapter short questions
C++ for C Programmers by Ira Pohl
