Recapitulation
C. Papachristos
Robotic Workers Lab
University of Nevada, Reno
CS-202
Course , Projects , Labs:
Your Final is on Thursday 5/7 @ 4:50pm.
Monday | Tuesday | Wednesday | Thursday | Friday | | Sunday |
|
|
| FINAL |
| | |
| RECAP CLASS | PASS Session |
| | | |
PASS Session | | | | | |
Course Week
CS-202 C. Papachristos
Today’s Topics
CS-202 C. Papachristos
Recapitulation:
Prerequisites (not covered in Recap):
void func( DataType obj );
void func( DataType& obj ); / void func( const DataType& obj );
void func( DataType* obj ); / void func( const DataType* obj );
DataType func( );
DataType& func( ); / const DataType& func( );
DataType* func( ); / const DataType* func( );
Classes
CS-202 C. Papachristos
Class Declaration & Implementation
const size_t ID_LEN = 5+1;
const char DEFAULT_ID[ID_LEN] = "00000"; const char * DEFAULT_PLATES = "Default-Plate";
class Car {
public:
Car();
Car(const char * plates, const char id[ID_LEN]=DEFAULT_ID,
const Engine & engine=Engine(), Driver * driver=nullptr, size_t serial=count);
Car(const Car & other);
~Car();
Car & operator=(const Car & other);
Engine & getEngine(); const Engine & getEngine() const;
Driver * getDriver(); const Driver * getDriver() const;
friend std::ostream & operator<<(std::ostream & os, const Car & car);
friend std::istream & operator>>(std::istream & is, Car & car);
private:
Engine m_engine; // composition
Driver * m_driver; // aggregation
char m_id[ID_LEN];
char * m_plates; // raw pointer
const size_t m_serial; // const
static size_t count; // static
};
Classes
CS-202 C. Papachristos
Class Declaration & Implementation
size_t Car::count = 0;
Car::Car() : m_serial( count++ ){
m_plates = nullptr;
m_driver = nullptr;
//count already incremented
}
Car::Car(const char * plates, const char id[ID_LEN],
const Engine & engine, Driver * driver, size_t serial)
: m_serial(count = serial>count ? serial : count){ //get the bigger number
m_plates = new char [ strlen(plates)+1 ]; //have to allocate first
strcpy(m_plates, plates);
m_engine = engine;
m_driver = driver;
strcpy(m_id, id);
++count; //increment at the end, constructor done & no exceptions occurred
}
class Car {
public:
…
private:
Engine m_engine;
Driver * m_driver;
char m_id[ID_LEN];
char * m_plates;
const size_t m_serial;
static size_t count;
};
Classes
CS-202 C. Papachristos
Class Declaration & Implementation
Car::Car(const Car & other) : m_serial( count ){
m_plates = new char [ strlen(other.m_plates)+1 ]; //allocate new
strcpy(m_plates, other.m_plates);
m_engine = other.m_engine;
m_driver = other.m_driver; //same (pointer to outside object) driver
strcpy(m_id, other.m_id);
++count; //increment at the end (constructor done)
}
Car::~Car(){
//engine is class member object (aggregation) – will be automatically destroyed
//driver is pointer to external object (composition) – no deleting
delete [] m_plates; //m_plates uses dynamic memory - delete
//destroying object, m_plates=NULL unnecessary
//no decrementing of count (--count;), acts like a unique it generator
}
class Car {
public:
…
private:
Engine m_engine;
Driver * m_driver;
char m_id[ID_LEN];
char * m_plates;
const size_t m_serial;
static size_t count;
};
Classes
CS-202 C. Papachristos
Class Declaration & Implementation
Car& Car::operator=(const Car & other){
if (this != &other){ //protect from self-assignment
char * tmp = new char [ strlen(other.m_plates)+1 ]; //allocate new
strcpy(tmp, other.m_plates);
delete [] m_plates; //have to delete dynamic memory first
m_plates = tmp;
m_engine = other.m_engine;
m_driver = other.m_driver; //same (pointer to outside object) driver
strcpy(m_id, other.m_id);
}
return *this;
}
class Car {
public:
…
private:
Engine m_engine;
Driver * m_driver;
char m_id[ID_LEN];
char * m_plates;
const size_t m_serial;
static size_t count;
};
Classes
CS-202 C. Papachristos
Class Declaration & Implementation
std::ostream & operator<<(std::ostream & os, const Car & car){
os << car.m_serial<<": "<<car.m_id <<", "
<< car.m_plates<<"-"<<car.m_engine;
//driver is a pointer, have to check it, and have to dereference it
if (m_driver){ os << " driver: “ << *m_driver; }
return os;
}
std::istream & operator>>(std::istream & is, Car & car){
cout << "Expecting engine details (cc)" << endl;
is >> car.m_engine;
cout << "Expecting id[" << ID_LEN <<"]" << endl;
is >> car.m_id;
if (car.m_plates){
cout << "Expecting license plates" << endl;
is >> car.m_plates;
}
return is;
}
class Car {
public:
…
private:
Engine m_engine;
Driver * m_driver;
char m_id[ID_LEN];
char * m_plates;
const size_t m_serial;
static size_t count;
};
Classes
CS-202 C. Papachristos
Class Declaration & Implementation
const Engine & Car::getEngine() const{ //read-out engine (const-access)
return m_engine;
}
Engine & Car::getEngine(){ //can also read-in engine (non-const-access)
return m_engine;
}
const Driver * Car::getDriver() const{ //read-out driver (const-access)
return m_driver;
}
Driver * Car::getDriver(){ //can also read-in driver (non-const-access)
return m_driver;
}
/* also have to have */
// const char * Car::getID() const{ … }
// const char * Car::getPlates() const{ … }
// size_t Car::getSerial() const{ … }
class Car {
public:
…
private:
Engine m_engine;
Driver * m_driver;
char m_id[ID_LEN];
char * m_plates;
const size_t m_serial;
static size_t count;
};
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
class Vehicle {
public:
Vehicle();
Vehicle(const char * plates, const Engine & engine=Engine());
Vehicle(const Vehicle & other);
~Vehicle();
Vehicle & operator=(const Vehicle & other);
const Engine & getEngine() const;
void setEngine(const Engine& engine);
const char * getPlates() const;
void setPlates(const char * plates);
void move();
protected:
char * m_plates;
float m_miles;
private:
Engine m_engine;
};
void Vehicle::move(){
cout << "class Vehicle does not know how to move…" << endl;
}
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
const size_t SEDAN_DEFAULT_GEARS = 5;
const double SEDAN_DEFAULT_ENGINE = 2.0;
class Sedan : public Vehicle {
public:
Sedan();
Sedan(const char * plates,
bool manual=false, size_t gears=SEDAN_DEFAULT_GEARS,
const Engine & engine=Engine(SEDAN_DEFAULT_ENGINE));
Sedan(const Sedan & other);
~Sedan();
Sedan & operator=(const Sedan & other);
bool getManual() const{ return m_manual; }
void setManual(bool manual){ m_manual = manual; }
size_t getGears() const{ return m_gears; }
void setGears(size_t gears){ m_gears = gears; }
float move();
float driveInCity();
private:
bool m_manual;
size_t m_gears;
};
class Vehicle {
public:
Vehicle();
Vehicle(const char* plates,
const Engine & engine=Engine());
Vehicle(const Vehicle & other);
~Vehicle();
void move();
protected:
float m_miles;
char * m_plates;
private:
Engine m_engine;
};
…
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
/* base class ctor called first, then derived class ctor */
Sedan::Sedan() {
}
Sedan::Sedan(const char * plates, bool manual,
size_t gears, const Engine& engine)
: Vehicle(plates, engine){
m_manual = manual;
m_gears = gears;
}
Sedan::Sedan(const Sedan & other)
: Vehicle(other.m_plates, other.getEngine()){
m_manual = other.m_manual;
m_gears = other.m_gears;
}
/* derived dtor should be called first, then base dtor */
Sedan::~Sedan() {
}
class Sedan : public Vehicle {
public:
float driveInCity();
private:
bool m_manual;
size_t m_gears;
};
…
class Vehicle {
public:
Vehicle();
Vehicle(const char * plates,
const Engine & engine=Engine());
Vehicle(const Vehicle & other);
~Vehicle();
void move();
protected:
float m_miles;
char * m_plates;
private:
Engine m_engine;
};
…
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
Sedan & Sedan::operator=(const Sedan & other){
if (this != &other){ //protect from self-assignment
//handle base class members appropriately!
Vehicle::operator=( other );
//handle derived class members separately!
m_manual = other.m_manual;
m_gears = other.m_gears;
}
return *this;
}
class Sedan : public Vehicle {
public:
float driveInCity();
private:
bool m_manual;
size_t m_gears;
};
…
class Vehicle {
public:
Vehicle();
Vehicle(const char * plates,
const Engine & engine=Engine());
Vehicle(const Vehicle & other);
~Vehicle();
void move();
protected:
float m_miles;
char * m_plates;
private:
Engine m_engine;
};
…
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
float Sedan::driveInCity(){
float milesThisTrip = 0;
if (m_manual){
/* required actions involving m_gears, etc… */
cout<<"Sedan "<<m_plates<<" manual"<< endl;
}
else{
/* required actions in this case, etc… */
cout<<"Sedan "<<m_plates<<" automatic"<< endl;
}
return milesThisTrip;
}
float Sedan::move(){
return (m_miles += driveInCity());
}
class Sedan : public Vehicle {
public:
float driveInCity();
private:
bool m_manual;
size_t m_gears;
};
…
class Vehicle {
public:
Vehicle();
Vehicle(const char * plates,
const Engine& engine=Engine());
Vehicle(const Vehicle & other);
~Vehicle();
void move();
protected:
float m_miles;
char * m_plates;
private:
Engine m_engine;
};
…
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
const double SUV_DEFAULT_ENGINE = 3.5;
class Suv : public Vehicle {
public:
Suv();
Suv(const char * plates,
bool awd=false, Emergencykit * emergencykit=NULL,
const Engine & engine=Engine(SUV_DEFAULT_ENGINE));
Suv(const Suv & other);
~Suv();
Suv & operator=(const Suv & other);
bool getAwd() const{ return m_awd; }
void setAwd(bool awd){ m_awd = awd; }
const Emergencykit * getEmergencykit() const;
void setEmergencykit(const Emergencykit & emergencykit);
float move();
float driveInCityOffRoad(bool offroad);
private:
bool m_awd;
Emergencykit * m_emergencykit;
};
class Vehicle {
public:
Vehicle();
Vehicle(const char * plates,
const Engine& engine=Engine());
Vehicle(const Vehicle & other);
~Vehicle();
void move();
protected:
float m_miles;
char * m_plates;
private:
Engine m_engine;
};
…
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
/* base class ctor called first, then derived class ctor */
Suv::Suv() {
m_emergencykit = nullptr;
}
Suv::Suv(const char * plates, bool awd,
Emergencykit * emergencykit, const Engine & engine)
: Vehicle(plates, engine){
m_awd = awd; m_emergencykit = emergencykit;
if (!m_emergencykit && m_awd)
m_emergencykit = new Emergencykit;
}
Suv::Suv(const Suv & other)
: Vehicle(other.m_plates, other.getEngine()){
m_awd = other.m_awd;
m_emergencykit = new Emergencykit( *other.m_emergencykit );
}
/* derived class dtor called first, then base class dtor */
Suv::~Suv() {
delete m_emergencykit;
}
…
class Suv : public Vehicle {
public:
float driveInCityOffRoad(bool);
private:
bool m_awd;
Emergencykit * m_emergencykit;
};
class Vehicle {
public:
Vehicle();
Vehicle(const char * plates,
const Engine& engine=Engine());
Vehicle(const Vehicle & other);
~Vehicle();
void move();
protected:
float m_miles;
char * m_plates;
private:
Engine m_engine;
};
…
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
Suv & Suv::operator=(const Suv & other){
if (this != &other){ //protect from self-assignment
//handle base class members appropriately!
Vehicle::operator=( other );
//handle derived class members separately!
Emergencykit * tmp =
new Emergencykit(*other.m_emergencykit);
delete m_emergencykit; //delete dynamic object
m_emergencykit = tmp;
m_awd = other.m_awd;
}
return *this;
}
…
class Suv : public Vehicle {
public:
float driveInCityOffRoad(bool);
private:
bool m_awd;
Emergencykit * m_emergencykit;
};
class Vehicle {
public:
Vehicle();
Vehicle(const char * plates,
const Engine & engine=Engine());
Vehicle(const Vehicle & other);
~Vehicle();
void move();
protected:
float m_miles;
char * m_plates;
private:
Engine m_engine;
};
…
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
float Suv::driveInCityOffRoad(bool offroad){
float milesThisTrip = 0;
if (offroad && m_awd){
/* required actions to drive offroad, etc… */
cout<<"Suv "<<m_plates<<" offroad"<< endl;
}
else if (m_awd){
/* required actions to drive in city with awd, etc… */
cout<<"Suv "<<m_plates<<" awd in city"<< endl;
}
else{
/* required actions to drive in city without awd, etc… */
cout<<"Suv "<<m_plates<<" normal city drive"<< endl;
}
return milesThisTrip;
}
float Suv::move(){
return (m_miles += driveInCityOffRoad( false ));
}
…
class Suv : public Vehicle {
public:
float driveInCityOffRoad(bool);
private:
bool m_awd;
Emergencykit * m_emergencykit;
};
class Vehicle {
public:
Vehicle();
Vehicle(const char * plates,
const Engine& engine=Engine());
Vehicle(const Vehicle & other);
~Vehicle();
void move();
protected:
float m_miles;
char * m_plates;
private:
Engine m_engine;
};
…
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
int main() {
Vehicle vehicle0;
Sedan sedan1("SEDAN1");
Sedan sedan2("SEDAN2", true, 6, Engine(4.0));
Suv suv1("SUV1");
Suv suv2("SUV2", true, new Emergencykit, Engine(5.0));
Vehicle * vehicle_Pt;
vehicle_Pt = &vehicle0; vehicle_Pt->move();
Sedan * sedan_Pt;
sedan_Pt = &sedan1; sedan_Pt->move();
sedan_Pt = &sedan2; sedan_Pt->move();
Suv * suv_Pt;
suv_Pt = &suv1; suv_Pt->move();
suv_Pt = &suv2; suv_Pt->move();
}
class Suv : public Vehicle {
public: …
float driveInCityOffRoad(bool);
private:
bool m_awd;
Emergencykit * m_emergencykit;
};
class Sedan : public Vehicle {
public: …
float driveInCity();
private:
bool m_manual;
size_t m_gears;
};
class Vehicle does not know how to move…
Sedan SEDAN1 automatic
Sedan SEDAN2 manual
Suv SUV1 normal city drive
Suv SUV2 awd in city
class Vehicle {
public: …
void move();
protected:
float m_miles;
char * m_plates;
private:
Engine m_engine;
};
Inheritance
CS-202 C. Papachristos
Working with Hierarchies
int main() {
Vehicle vehicle0;
Sedan sedan1("SEDAN1");
Sedan sedan2("SEDAN2", true, 6, Engine(4.0));
Suv suv1("SUV1");
Suv suv2("SUV2", true, new Emergencykit, Engine(5.0));
Vehicle * vehicles_index_array[5];
vehicles_index_array[0] = &vehicle0;
vehicles_index_array[1] = &sedan1;
vehicles_index_array[2] = &sedan2;
vehicles_index_array[3] = &suv1;
vehicles_index_array[4] = &suv2;
for (size_t i=0; i<5; ++i){
vehicles_index_array[i]->move();
}
}
class Suv : public Vehicle {
public: …
float driveInCityOffRoad(bool);
private:
bool m_awd;
Emergencykit * m_emergencykit;
};
class Vehicle {
public: …
void move();
protected:
float m_miles;
char * m_plates;
private:
Engine m_engine;
};
class Sedan : public Vehicle {
public: …
float driveInCity();
private:
bool m_manual;
size_t m_gears;
};
class Vehicle does not know how to move…
class Vehicle does not know how to move…
class Vehicle does not know how to move…
class Vehicle does not know how to move…
class Vehicle does not know how to move…
Polymorphism
CS-202 C. Papachristos
Achieving Polymorphic behavior
class Vehicle {
public: …
void move();
protected:
float m_miles;
…
};
class Sedan : public Vehicle {
public: …
float move();
float driveInCity();
…
};
class Suv : public Vehicle {
public: …
float move();
float driveInCityOffRoad(bool);
…
};
class Vehicle {
public: …
virtual float move();
protected:
float m_miles;
…
};
class Sedan : public Vehicle {
public: …
virtual float move();
float driveInCity();
…
};
class Suv : public Vehicle {
public: …
virtual float move();
float driveInCityOffRoad(bool);
…
};
float Vehicle::move(){
cout << "…" << endl;
return m_miles;
}
CS-202 C. Papachristos
Working with Hierarchies
int main() {
Vehicle vehicle0;
Sedan sedan1("SEDAN1");
Sedan sedan2("SEDAN2", true, 6, Engine(4.0));
Suv suv1("SUV1");
Suv suv2("SUV2", true, new Emergencykit, Engine(5.0));
Vehicle * vehicles_index_array[5];
vehicles_index_array[0] = &vehicle0;
vehicles_index_array[1] = &sedan1;
vehicles_index_array[2] = &sedan2;
vehicles_index_array[3] = &suv1;
vehicles_index_array[4] = &suv2;
for (size_t i=0; i<5; ++i){
vehicles_index_array[i]->move();
}
}
Polymorphism
class Suv : public Vehicle {
public: …
virtual float move();
float driveInCityOffRoad(bool);
…
};
class Sedan : public Vehicle {
public: …
virtual float move();
float driveInCity();
…
};
class Vehicle does not know how to move…
Sedan SEDAN1 automatic
Sedan SEDAN2 manual
Suv SUV1 normal city drive
Suv SUV2 awd in city
class Vehicle {
public: …
virtual float move();
protected:
float m_miles;
…
};
Polymorphism
CS-202 C. Papachristos
Achieving Polymorphic behavior
class Vehicle {
public: …
void move();
protected:
float m_miles;
…
};
class Sedan : public Vehicle {
public: …
float move();
float driveInCity();
…
};
class Suv : public Vehicle {
public: …
float move();
float driveInCityOffRoad(bool);
…
};
class Vehicle {
public: …
virtual float move() = 0;
protected:
float m_miles;
…
};
class Sedan : public Vehicle {
public: …
virtual float move();
float driveInCity();
…
};
class Suv : public Vehicle {
public: …
virtual float move();
float driveInCityOffRoad(bool);
…
};
float Vehicle::move(){
cout << "…" << endl;
return m_miles;
}
CS-202 C. Papachristos
Working with Hierarchies
int main() {
Vehicle vehicle0;
Sedan sedan1("SEDAN1");
Sedan sedan2("SEDAN2", true, 6, Engine(4.0));
Suv suv1("SUV1");
Suv suv2("SUV2", true, new Emergencykit, Engine(5.0));
Vehicle * vehicles_index_array[4];
vehicles_index_array[0] = &sedan1;
vehicles_index_array[1] = &sedan2;
vehicles_index_array[2] = &suv1;
vehicles_index_array[3] = &suv2;
for (size_t i=0; i<4; ++i){
vehicles_index_array[i]->move();
}
}
Polymorphism
class Suv : public Vehicle {
public: …
virtual float move();
float driveInCityOffRoad(bool);
…
};
class Sedan : public Vehicle {
public: …
virtual float move();
float driveInCity();
…
};
Sedan SEDAN1 automatic
Sedan SEDAN2 manual
Suv SUV1 normal city drive
Suv SUV2 awd in city
class Vehicle {
public: …
virtual float move() = 0;
protected:
float m_miles;
…
};
CS-202 C. Papachristos
Working with Hierarchies
int main() {
Vehicle * vehicles_index_array[3];
vehicles_index_array[0] = new Vehicle;
vehicles_index_array[1] = new Sedan("SEDAN2", true, 6, Engine(4.0));
vehicles_index_array[2] = new Suv("SUV2", true, new Emergencykit,
Engine(5.0));
for (size_t i=0; i<3; ++i){
vehicles_index_array[i]->move();
}
// cleanup ...
for (size_t i=0; i<3; ++i){
delete vehicles_index_array[i];
}
}
Polymorphism
class Suv : public Vehicle {
public: …
~Suv();
private:
bool m_awd;
Emergencykit * m_emergencykit;
};
class Sedan : public Vehicle {
public: …
~Sedan();
private:
bool m_manual; size_t m_gears;
};
~Vehicle dtor…
~Vehicle dtor…
~Vehicle dtor…
class Vehicle {
public: …
~Sedan();
virtual float move();
protected:
float m_miles;
…
};
CS-202 C. Papachristos
Working with Hierarchies
int main() {
Vehicle * vehicles_index_array[3];
vehicles_index_array[0] = new Vehicle;
vehicles_index_array[1] = new Sedan("SEDAN2", true, 6, Engine(4.0));
vehicles_index_array[2] = new Suv("SUV2", true, new Emergencykit,
Engine(5.0));
for (size_t i=0; i<3; ++i){
vehicles_index_array[i]->move();
}
// cleanup ...
for (size_t i=0; i<3; ++i){
delete vehicles_index_array[i];
}
}
Polymorphism
class Suv : public Vehicle {
public: …
~Suv();
private:
bool m_awd;
Emergencykit * m_emergencykit;
};
class Sedan : public Vehicle {
public: …
~Sedan();
private:
bool m_manual; size_t m_gears;
};
~Vehicle dtor…
~Sedan dtor…
~Vehicle dtor…
~Suv dtor…
~Vehicle dtor…
class Vehicle {
public: …
virtual ~Vehicle();
virtual float move();
protected:
float m_miles;
…
};
Dynamic Memory
CS-202 C. Papachristos
Managing Dynamic Memory
int * grades_array = nullptr;
size_t size_grades_array;
cin >> size_grades_array;
try{
grades_array = new int[size_grades_array];
}
catch(const std::bad_alloc & ex){
cerr<<"Bad allocation of "<<size_grades_array<<"integer array…"<<endl;
size_grades_array = 0; //defensive
}
if (grades_array) {
for (size_t i=0; i<size_grades_array; ++i){ cin>>grades_array[i]; }
for (size_t i=0; i<size_grades_array; ++i){ cout<<grades_array[i]; }
}
delete [] grades_array;
grades_array = nullptr;
size_grades_array = 0; //defensive
...
...
Dynamic Memory
CS-202 C. Papachristos
Managing Dynamic Memory
int * * int_matrix = nullptr;
size_t rows, cols; cin >> rows>>cols;
try{
int_matrix = new int * [rows];
for (size_t i=0; i<rows; ++i)
int_matrix[i] = nullptr;
for (size_t i=0; i<rows; ++i){
try{
int_matrix[i] = new int [cols];
}
catch(const std::bad_alloc & ex){
for (size_t i_del=0; i_del<i; ++i_del)
delete [] m_data[i_del];
throw;
}
}
}
catch(const std::bad_alloc & ex)
{ delete [] int_matrix; }
if (int_matrix){
for (int i=0; i<rows; ++i){
delete [] int_matrix[i];
}
delete [] int_matrix;
}
Forward List (Singly-Linked Node-based)
CS-202 C. Papachristos
Linked-List(s)
m_data |
… |
… |
… |
m_next
0x…
Node 1
m_data |
… |
… |
… |
m_next
0x…
Node 0
m_head
m_data |
… |
… |
… |
m_next
0x…
Node n
m_data |
… |
… |
… |
m_next
0x…
Node …
NULL
class Node{
//declaration of friend classes – Queue,Stack,List,etc.
friend class List;
public:
Node() : m_next(nullptr){ }
Node(const DataClass & data, Node * next = nullptr)
: m_data(data), m_next(next){ }
const DataClass & data() const{ return m_data; }
DataClass & data(){ return m_data; }
private:
Node * m_next;
DataClass m_data;
};
m_data |
… |
… |
… |
m_next
0x…
Node k
Forward List (Singly-Linked Node-based)
CS-202 C. Papachristos
“First” Node creation
Declares a pointer variable m_head.
Empty Forward-List, so set to “Null Pointer”.
m_head = nullptr;
Dynamically allocate new Node.
The First in the LL, so assigned to head.
m_head = new Node(DataType("Alice",95), nullptr);
Set head Node data.
Next set to nullptr since it’s the only node.
"Alice" |
95 |
m_next
0x…
Node 0
m_head
NULL
CS-202 C. Papachristos
Forward-List Insertion
Inter-connect inserted Node into the FL.
m_head
curr
m_data |
… |
… |
m_next
0x…
Node …
m_data |
… |
… |
m_next
0x…
Node 0
m_data |
… |
… |
m_next
0x…
NULL
m_data |
… |
… |
m_next
0x…
Node n
Node k
for (Node * curr = m_head; curr!=nullptr; curr = curr->m_next) //traversal
if ( curr->m_data == … ){
Node * newNode_pt = new Node(data, curr->m_next);
curr->m_next = newNode_pt;
}
}
m_data |
… |
… |
m_next
0x…
newNode
newNode_pt
Forward List (Singly-Linked Node-based)
CS-202 C. Papachristos
Forward-List Node Erasing
Deallocate dynamic memory of target Node.
for (Node * curr = m_head; curr!=NULL; curr = curr->m_next) //traversal
Node * delNode_pt = curr->m_next;
if ( delNode_pt!=nullptr && delNode_pt->m_data == … ){
curr->m_next = delNode_pt->m_next;
delete delNode_pt;
}
m_head
m_data |
… |
… |
m_next
0x…
Node …
m_data |
… |
… |
m_next
0x…
m_data |
… |
… |
m_next
0x…
NULL
m_data |
… |
… |
m_next
0x…
Node n
Node k
Node 0
curr
delNode_pt
Forward List (Singly-Linked Node-based)
Dynamic Data Structures
CS-202 C. Papachristos
Stack push()
Elements are exclusively pushed to the top of the Stack.
m_data |
… |
… |
m_next
0x…
Node n-1
m_data |
… |
… |
m_next
0x…
Node n
m_top
m_data |
… |
… |
m_next
0x…
Node 0
m_data |
… |
… |
m_next
0x…
Node …
1) Node * newNode_Pt(Data(…), m_top);
2) m_top = newNode_Pt;
m_data |
… |
… |
m_next
0x…
Node k
2)
NULL
1)
newNode_pt
Dynamic Data Structures
CS-202 C. Papachristos
Stack pop()
Elements are exclusively popped from the top of the Stack.
1) Node * delNode_Pt = m_top;
2) m_top = m_top->m_next;
3) delete delNode_Pt;
m_data |
… |
… |
m_next
0x…
Node n-1
m_data |
… |
… |
m_next
0x…
Node n
m_top
DataType |
… |
… |
m_next
0x…
Node 0
DataType |
… |
… |
m_next
0x…
Node …
NULL
delNode_pt
2)
3)
1)
Dynamic Data Structures
CS-202 C. Papachristos
Queue push()
Elements are exclusively pushed to the back of the Queue.
m_data |
… |
… |
m_next
0x…
Node 1
m_data |
… |
… |
m_next
0x…
Node 0
m_front
m_data |
… |
… |
m_next
0x…
Node n-1
m_data |
… |
… |
m_next
0x…
Node …
NULL
m_back
DataType |
… |
… |
m_next
0x…
Node k
2)
3)
1)
1) Node * newNode_Pt(Data(…), nullptr);
2) m_back->m_next = newNode_Pt;
3) m_back = newNode_Pt;
newNode_pt
Dynamic Data Structures
CS-202 C. Papachristos
Queue pop()
Elements are exclusively popped from the back of the Queue.
m_data |
… |
… |
m_next
0x…
Node 1
m_data |
… |
… |
m_next
0x…
Node 0
m_front
DataType |
… |
… |
m_next
0x…
Node n
DataType |
… |
… |
m_next
0x…
Node …
NULL
m_back
delNode_Pt
1) Node * delNode_Pt = m_front;
2) m_front = m_front->m_next;
3) delete delNode_Pt;
2)
3)
1)
Dynamic Data Structures
CS-202 C. Papachristos
Array-based Queue(s)
push()-ing: Advance m_back to next circular array position.
if ( !full() ) {
m_back = (m_back + 1) % m_maxsize;
++m_size; //keep track of the size
}
char |
… |
m_arr […]
char |
A |
m_arr [97]
char |
… |
m_arr [96]
char |
B |
m_arr [98]
char |
C |
m_arr [99]
char |
D |
char |
… |
m_arr [0]
m_arr [1]
char |
… |
m_arr […]
char |
A |
m_arr [97]
char |
… |
m_arr [96]
char |
B |
m_arr [98]
char |
C |
m_arr [99]
char |
… |
char |
… |
m_arr [0]
m_arr [1]
charQueue.push(‘D’);
m_size := 4 m_front := 97
m_maxsize := 99 m_back := 0
m_size := 3 m_front := 97
m_maxsize := 99 m_back := 99
[99]
[0]
[98]
[1]
[97]
[2]
[…]
[…]
Dynamic Data Structures
CS-202 C. Papachristos
Array-based Queue(s)
pop()-ping: Advance m_front to next circular array position.
if ( !empty() ) {
m_front = (m_front + 1) % m_maxsize;
--m_size; //remember the size
}
char |
D |
m_arr [2]
char |
… |
m_arr [97]
char |
… |
m_arr […]
char |
… |
m_arr [98]
char |
A |
m_arr [99]
char |
B |
char |
C |
m_arr [0]
m_arr [1]
m_size := 3 m_front := 0
m_maxsize := 99 m_back := 2
m_size := 4 m_front := 99
m_maxsize := 99 m_back := 2
[99]
[0]
[98]
[1]
[97]
[2]
[…]
[…]
char |
D |
m_arr [2]
char |
… |
m_arr [97]
char |
… |
m_arr […]
char |
… |
m_arr [98]
char |
… |
m_arr [99]
char |
B |
char |
C |
m_arr [0]
m_arr [1]
charQueue.pop();
Templates
CS-202 C. Papachristos
Function Templates(s)
// forward declaration
template < typename T >
void Swap(T & v1, T & v2);
// templated implementation
template < typename T >
void Swap(T & v1, T & v2){ T temp = v1; v1 = v2; v2 = temp; };
Call with implicit / explicit template parameter statement:
int i1=0, i2=1; Swap(i1, i2);
float f1=0.1, f2 = 99.9; Swap< float >(f1, f2);
Car c1("GRAY"), c2("WHITE"); Swap(c1, c2);
Date d1(4,20), d2(4,21); Swap< Date >(1, d2);
Inferred / Declared Type
T : int
T : float
T : Car
T : Date
Templates
CS-202 C. Papachristos
Class Templates
// forward declarations -in order- (successful compilation requires these)
template <typename T, size_t N_CART> class Train;
template <typename T, size_t N_CART> std::ostream & operator<<(std::ostream & os, � const Train<T,N_CART> & car);
template <typename T, size_t N_CART = 1>
class Train {
public:
Train();
Train(size_t capacity, const T & item_value = T());
Train(const Train<T,N_CART> & other);
~Train();
Train<T,N_CART> & operator=(const Train<T,N_CART> & other);
const T * getCart(size_t i) const;
T * getCart(size_t i);
// friend function declared as specialization of templated operator
friend std::ostream & operator<< <> (std::ostream & os, const Train<T,N_CART> & car);
private:
T * m_carts[N_CART]; // an array of N_CART subarrays containing T objects
size_t m_capacities[N_CART]; // an array of number of elements per cart
};
Templates
CS-202 C. Papachristos
Class Templates
template <typename T, size_t N_CART>
Train<T,N_CART>::Train(){
for (size_t i = 0; i < N_CART; ++i){
m_carts[i] = nullptr; // initialize pointers
m_capacities[i] = 0; // defensive
}
}
template <typename T, size_t N_CART>
Train<T,N_CART>::Train(size_t n_per_cart, const T & item_value){
for (size_t i = 0; i < N_CART; ++i){ // iterative new needs exception handling
// for each pointer allocate a new subarray
m_carts[i] = new T [ n_per_cart ];
m_capacities[i] = n_per_cart;
for (size_t j = 0; j < n_per_cart; ++j){
m_carts[i][j] = item_value;
}
}
}
Templates
CS-202 C. Papachristos
Class Templates
template <typename T, size_t N_CART>
Train<T,N_CART>::Train(const Train<T,N_CART> & other){
for (size_t i = 0; i < N_CART; ++i){ // iterative new needs exception handling
m_capacities[i] = other.m_capacities[i];
if (!m_capacities[i])
continue;
m_carts[i] = new T [ other.m_capacities[i] ]; // allocate subarray
for (size_t j = 0; j < m_capacities[i]; ++j){
m_carts[i][j] = other.m_carts[i][j];
}
}
}
template <typename T, size_t N_CART>
Train<T,N_CART>::~Train(){
for (size_t i = 0; i < N_CART; ++i){
//deleting a pointer to an allocated array, needs delete [] variant
delete [] m_carts[i];
}
}
Templates
CS-202 C. Papachristos
Class Templates
template <typename T, size_t N_CART>
Train<T,N_CART> & Train<T,N_CART>::operator=(const Train<T,N_CART> & other){
if (this != &other){ // check for self-assignment
for (size_t i = 0; i < N_CART; ++i){ // iterative new needs exception handling
delete m_carts[i]; // deallocate previous memory (if necessary)
m_carts[i] = nullptr; // set pointers to NULL, exception might be thrown later
m_capacities[i] = other.m_capacities[i];
if (!m_capacities[i])
continue;
// for each pointer allocate a new subarray, sizes are stores in m_capacities
m_carts[i] = new T [ other.m_capacities[i] ];
for (size_t j = 0; j < m_capacities[i]; ++j){
m_carts[i][j] = other.m_carts[i][j];
}
}
}
// return calling object
return *this;
}
Templates
CS-202 C. Papachristos
Class Templates
template <typename T, size_t N_CART>
const T * Train<T,N_CART>::getCart(size_t i) const{ return m_carts[i]; }
template <typename T, size_t N_CART>
T * Train<T,N_CART>::getCart(size_t i){ return m_carts[i]; }
// implementation of templated friend (non-member) function
template <typename T, size_t N_CART>
std::ostream& operator<<(std::ostream & os, const Train<T,N_CART> & train){
for (size_t i = 0; i < N_CART; ++i){
if (train.m_carts[i]){
for (size_t j = 0; j < train.m_capacities[i]; ++j){
os << train.m_carts[i][j] <<" ";
}
os << endl;
}
}
return os;
}
Templates
CS-202 C. Papachristos
Dynamic Data Structures Class Templates
// forward declaration of (any) class or function that will be a friend of Node
// and is necessary for any other component to compile
template <typename T> class Queue;
// forward declaration of (any) class or function that will be a friend of DDS (Queue)
template <typename T> std::ostream & operator<<(std::ostream & os, const Queue<T> & queue);
// templated Node
template <typename T>
class Node{
friend class Queue<T>; //declaration of templated friend class
public:
Node() : m_next( nullptr ){ }
Node(const T & data, Node<T> * next = nullptr) : m_data( data ), m_next( next ){ }
const T & data() const{ return m_data; }
T & data(){ return m_data; }
private:
Node<T> * m_next;
T m_data;
};
Templates
CS-202 C. Papachristos
Dynamic Data Structures Class Templates
template <typename T> // DDS (Queue) class template
class Queue{
friend std::ostream & operator<< <> (std::ostream & os, const Queue<T> & queue);
public:
Queue();
Queue(size_t size, const T & value = T());
Queue(const Queue<T> & other);
~Queue();
Queue<T> & operator=(const Queue<T> & rhs);
T & front(); const T& front() const;
T & back(); const T& back() const;
void push(const T & value);
void pop();
size_t size() const; bool empty() const; bool full() const;
void clear();
void serialize(std::ostream & os) const;
private:
Node<T> * m_front;
Node<T> * m_back;
};
Templates
CS-202 C. Papachristos
Dynamic Data Structure Class Templates
template <typename T>
Queue<T>::Queue()
: m_front( nullptr )
, m_back ( nullptr )
{
}
template <typename T>
Queue<T> & Queue<T>::Queue(size_t size, const T & value)
: m_front( nullptr )
, m_back ( nullptr )
{
if (count){
Node<T> * currNode = m_front = new Node<T>(value);
while (--count){
currNode = currNode->m_next = new Node<T>(value);
}
//currNode->m_next = nullptr; //unnecessary, NULL-initialized by Node ctor
}
}
Templates
CS-202 C. Papachristos
Dynamic Data Structure Class Templates
template <typename T>
Queue<T>::Queue(const Queue<T> & other)
: m_front( nullptr )
, m_back ( nullptr )
{
Node<T> * otherNode = other.m_front;
if (otherNode){
Node<T> * myNode = m_front = new Node<T>(otherNode->m_data);
while (otherNode->m_next){
otherNode = otherNode->m_next;
myNode = myNode->m_next = new Node<T>(otherNode->m_data);
}
m_back = myNode;
}
}
Templates
CS-202 C. Papachristos
Dynamic Data Structure Class Templates
template <typename T>
Queue<T>::~Queue(){
//traverse to deallocate
while (m_front){
Node<T> * del_Pt = m_front;
m_front = m_front->m_next;
delete del_Pt;
}
}
template <typename T>
void Queue<T>::clear(){
//traverse to deallocate
while (m_front){
Node<T> * del_Pt = m_front;
m_front = m_front->m_next;
delete del_Pt;
}
m_front = nullptr; //reset pointers to NULL
m_back = nullptr; //reset pointers to NULL
}
Templates
CS-202 C. Papachristos
Dynamic Data Structure Class Templates
template <typename T>
Queue<T> & Queue<T>::operator=(const Queue<T> & rhs){
//check for self-assignment
if (this != &rhs){
clear(); //clear previous content first
Node<T> * otherNode = rhs.m_front;
if (otherNode){
Node<T> * myNode = m_front = new Node<T>(otherNode->m_data);
while (otherNode->m_next){
otherNode = otherNode->m_next;
myNode = myNode->m_next = new Node<T>(otherNode->m_data);
}
m_back = myNode;
}
}
//return calling object by-reference
return *this;
}
Templates
CS-202 C. Papachristos
Dynamic Data Structure Class Templates
template <typename T>
const T & Queue<T>::front() const{ return m_front->m_data; }
template <typename T>
T & Queue<T>::front(){ return m_front->m_data; }
template <typename T>
const T & Queue<T>::back() const{ return m_back->m_data; }
template <typename T>
T & Queue<T>::back(){ return m_back->m_data; }
template <typename T>
size_t Queue<T>::size() const{
size_t size = 0;
Node<T> * trav_Pt = m_front;
while (trav_Pt){
++size;
trav_Pt = trav_Pt->m_next;
}
return size;
}
Templates
CS-202 C. Papachristos
Dynamic Data Structure Class Templates
template <typename T>
void Queue<T>::push(const T & value){
if (!m_back){ //empty back and front initialized
m_back = m_front = new Node<T>(value);
}
else{ //append to back then update back
m_back = m_back->m_next = new Node<T>(value);
}
}
template <typename T>
void Queue<T>::pop(){
if (m_front){
Node<T> * del_Pt = m_front;
m_front = m_front->m_next;
delete del_Pt;
if (!m_front){ //no more elements after popping last one
m_back = nullptr;
}
}
}
Templates
CS-202 C. Papachristos
Dynamic Data Structure Class Templates
template <typename T>
void Queue<T>::serialize(std::ostream & os) const { // front-to-back
Node<T> * out_Pt = m_front;
//traverse to output
while (out_Pt){
os << out_Pt->data() << " ";
out_Pt = out_Pt->m_next;
}
}
template <typename T>
std::ostream & operator<<(std::ostream & os, const Queue<T> & queue){
queue.serialize(os);
//return std::ostream object
return os;
}
Exceptions
CS-202 C. Papachristos
The try – throw – catch Flow
Car::Car(const char * lPlates){
setLicensePlates( lPlates );
}
void Car::setLicensePlates(const char* lPlates){
std::string lPlates_str( lPlates );
if (lPlates_str.find_first_not_of("ABCDEF … 0123456789")
throw (lPlates_str) ;
m_licensePlates = lPlates_str;
}
Car * myCar_pt = nullptr;
try{
myCar_pt = new Car("ABC-123");
}
catch(const std::string & ex_lp){
cerr << "Plates " << ex_lp << " contain invalid characters...";
}
1)
2)
3)
4)
…
…
Exceptions
CS-202 C. Papachristos
The try – throw – catch Flow
Car::Car(const char * lPlates){
setLicensePlates( lPlates );
}
void Car::setLicensePlates(const char* lPlates){
std::string lPlates_str( lPlates );
if (lPlates_str.find_first_not_of("ABCDEF … 0123456789")
throw (lPlates_str) ;
m_licensePlates = lPlates_str;
}
Car * myCar_pt = nullptr;
try{
myCar_pt = new Car("@#!~+^");
}
catch(const std::string & ex_lp){
cerr << "Plates " << ex_lp << " contain invalid characters...";
}
3)
…
…
1)
2)
Exceptions
CS-202 C. Papachristos
The try – throw – catch Flow
Car::Car(const char * lPlates){
setLicensePlates( lPlates );
}
void Car::setLicensePlates(const char* lPlates){
std::string lPlates_str( lPlates );
if (lPlates_str.find_first_not_of("ABCDEF … 0123456789")
throw (lPlates_str) ;
m_licensePlates = lPlates_str;
}
Car * myCar_pt = nullptr;
try{
myCar_pt = new Car("@#!~+^");
}
catch(const std::string & ex_lp){
cerr << "Plates " << ex_lp << " contain invalid characters...";
}
…
…
…
4)
6)
3)
5-a)
5-b)
7)
8)
Exceptions
CS-202 C. Papachristos
Semantics of throw and catch
/*a block scope somewhere*/
{
throw _expression_ ;
}
/*a block scope somewhere*/
{
throw ;
}
Evaluate the value of _expression_ and use it to copy-initialize an Exception Object of the same type (Copy-ctor of the type must be available).
Abandon current catch Block and re-throw the currently handled Exception object�(the exact same – not a copy).
try{
/* something */
catch (const ExceptionClass & ex){
/*handling & manipulating
ExceptionClass type ex Exceptions*/
}
catch (const int &){
/*handling int type Exceptions*/
}
catch (...)
{
/*handling any type of Exception*/
}
Catch possible Exception type(s) in order�(and potentially manipulate the Exception Object)
Finals Sample – Program 1
CS-202 C. Papachristos
#include <iostream>
#include <cstring> // allowed to use built-in c-string functions
using namespace std;
/////////////////////////HELPERS/////////////////////////// (should be considered as pre-implemented & working)
class Cover{
public:
Cover() : m_hard(false){}
Cover(bool hard) : m_hard(hard){}
friend std::ostream & operator<<(std::ostream & os, const Cover & cover){ os << (cover.m_hard?"hardcover":"paperback");
return os; }
friend std::istream & operator>>(std::istream & is, Cover & cover){ is >> cover.m_hard; return is; }
bool getValue() const{ return m_hard; }
private:
bool m_hard;
};
class Client{
public:
Client(){ m_name = nullptr; }
Client(const char * name){ m_name = new char[ strlen(name)+1 ]; strcpy(m_name,name); }
Client(const Client & other){ m_name = new char[ strlen(other.m_name)+1 ]; strcpy(m_name,other.m_name); }
~Client(){ delete [] m_name; }
Client & operator=(const Client & other){ delete [] m_name; m_name = new char[ strlen(other.m_name)+1 ];
strcpy(m_name,other.m_name); }
const char * getName() const{ return m_name; }
friend std::istream & operator>>(std::istream & is, Client & client){ if (client.m_name){ is >> client.m_name; } return is; }
friend std::ostream & operator<<(std::ostream & os, const Client & client){ os << client.m_name; return os; }
private:
char * m_name;
};
Finals Sample – Program 1
CS-202 C. Papachristos
////////////////////////////BOOK//////////////////////////////
class Book {
friend std::ostream & operator<<(std::ostream & os, const Book & book);
public:
Book();
Book(const char * title, const Cover & cover=Cover(),
const Client * client=nullptr, size_t serial=count);
Book(const Book & other);
virtual ~Book();
Book & operator=(const Book & other);
const Cover & getCover() const;
void setCover(const Cover & cover);
const Client * getClient() const;
void setClient(const Client * client);
void serialize(std::ostream & os) const;
private:
char * m_title; // raw pointer
Cover m_cover; // composition
const Client * m_client; // aggregation
const size_t m_serial; // const
static size_t count; //static
};
Finals Sample – Program 1
CS-202 C. Papachristos
size_t Book::count = 0; // instantiation of static variables
Book::Book() : m_serial( count++ ){
m_title = nullptr; // initialization of pointers
m_client = nullptr;
}
Book::Book(const char * title, const Cover & cover, const Client * client, size_t serial)
: // set static to the greater value, and initialize const member at the same time
m_serial( count = serial>count?serial:count ),
m_cover(cover),
m_client(client) {
m_title = new char [ strlen(title)+1 ];
strcpy(m_title, title);
++count; // increment at the end, constructor done & no exceptions occurred
}
Finals Sample – Program 1
CS-202 C. Papachristos
Book::Book(const Book & other)
: m_serial( count ),
m_cover(other.m_cover),
m_client(other.m_client) {
m_title = new char [ strlen(other.m_title)+1 ];
strcpy(m_title, other.m_title);
++count; // increment at the end, constructor done & no exceptions occurred
}
Book & Book::operator=(const Book & other){
if (this != &other){ // check for self-assignment
char * tmp = new char [ strlen(other.m_title)+1 ]; // allocate new first
strcpy(tmp, other.m_title);
delete [] m_title; // then deallocateirst deallocate previous
m_title = tmp; // finally re-assign pointer
m_client = other.m_client;
}
//return calling object by-reference
return *this;
}
Finals Sample – Program 1
CS-202 C. Papachristos
Book::~Book(){
// cover is class member object (composition) – will be automatically destroyed
// m_client is pointer to external object (aggregation) – no deleting here
delete [] m_title; // m_title is object-bound dynamic memory - delete
//--count; // no decrement, count specified to generate unique increasing serial(s)
}
void Book::serialize(std::ostream & os) const{
os << m_serial<<":"<<m_title<<"("<<m_cover<<")";
if (m_client)
os <<" client:"<< *m_client; // m_client is a pointer! cout has to dereference it
return os;
}
std::ostream & operator<<(std::ostream & os, const Book & book){
book.serialize(os);
return os;
}
const Cover & Book::getCover() const{ return m_cover; }
void Book::setCover(const Cover & cover){ m_cover = cover; }
const Client * Book::getClient() const{ return m_client; }
void Book::setClient(const Client * client){ m_client = client; }
Finals Sample – Program 1
CS-202 C. Papachristos
//////////////////BOOK-INHERITANCE-POLYMORPHISM//////////////////
class Book {
public:
virtual ~Book();
…
virtual void serialize(std::ostream& os) const; // making this virtual causes� // dynamic binding to work
protected:
char * m_title; //moved to protected access
Cover m_cover; //moved to protected access
const size_t m_serial; //moved to protected access
static size_t count; //moved to protected access
private:
const Client * m_client;
};
// the virtual method implementation remains as is
void Book::serialize(std::ostream & os){
os << m_serial<< ":" <<m_title<< "(" << m_cover << ")";
if (m_client)
os << " client:" << *m_client; // m_client is a pointer! cout has to dereference it
return os;
}
Finals Sample – Program 1
CS-202 C. Papachristos
//////////////////////////CHILDRENBOOK////////////////////////////
class ChildrenBook : public Book{ //inheritance
public:
ChildrenBook();
ChildrenBook(const char * title, bool graphic, const Cover & cover=Cover(),
const Client * client=nullptr, size_t serial=count);
ChildrenBook(const ChildrenBook & other);
~ChildrenBook(); // Base constructor is virtual
ChildrenBook & operator=(const ChildrenBook & other);
bool getGraphic() const;
void setGraphic(const bool& graphic);
virtual void serialize(std::ostream& os) const; // overridden method is virtual in Base� // class therefore dynamic binding enabled
/* Unnecessary if serialize is virtual, dynamic binding on Base class object will work ! */
/* friend std::ostream & operator<<(std::ostream & os, const ChildrenBook & childrenbook); */
private:
bool m_graphic;
};
Finals Sample – Program 1
CS-202 C. Papachristos
ChildrenBook::ChildrenBook()
: Book(){ //call default base ctor at instantiation
// count increases when base class constructor gets called
}
ChildrenBook::ChildrenBook(const char * title, bool graphic, const Cover & cover,
const Client * client, size_t serial)
: //use base class parametrized constructor with arguments (passing them along)
Book(title, cover, client, serial),
m_graphic(graphic){
// count increases when base class constructor gets called
}
ChildrenBook::ChildrenBook(const ChildrenBook & other)
: //have to use GetClient() because m_client is private, not protected
Book(other.m_title, other.m_cover, other.getClient(), other.m_serial),
m_graphic(other.m_graphic){
// count increases when base class constructor gets called
}
ChildrenBook::~ChildrenBook(){
// derived class has no dynamic memory to manage� // base class destructor will get automatically called right after
}
Finals Sample – Program 1
CS-202 C. Papachristos
ChildrenBook & ChildrenBook::operator=(const ChildrenBook & other){
if (this != &other){ // check for self-assignment
// handle base class members
Book::operator=( other );
// handle derived class members
m_graphic = other.m_graphic;
}
//return calling object by-reference
return *this;
}
Finals Sample – Program 1
CS-202 C. Papachristos
// overriding function of the base class serialize(), virtual as well to enable Dynamic Binding
void ChildrenBook::serialize(std::ostream & os){
os << m_serial<<":"<<m_title<<"("<<m_cover<<","<<(m_graphic?"graphic":"novel")<<")";
if (getClient()){
//m_client is a pointer, and it is also private (not protected)
os << " client:" << *getClient();
}
}
/* Unnecessary if serialize is virtual, dynamic binding on Base class object will work! */
std::ostream & operator<<(std::ostream & os, const ChildrenBook & childrenbook){
childrenbook.serialize(os);
return os;
}
Finals Sample – Program 1
CS-202 C. Papachristos
////////////////////////////MAIN//////////////////////////////
int main()
{
Client jDoe("John Doe");
Book myBook("LOTR ROTC", Cover(true), &jDoe, 999);
Client jDoeJr("John Doe Jr");
ChildrenBook myChildBook("LOTR comic", true, Cover(false), &jDoeJr);
Book * book_Pt;
book_Pt = &myBook;
cout << *book_Pt << endl;
book_Pt = &myChildBook;
cout << *book_Pt << endl; /* this uses the friend operator<< function which is not a� member function (and hence cannot be a virtual one) */
/*however if the Base class method is virtual (dynamic binding) then the Derived� class method override will be called */
return 0;
}
Finals Sample – Program 2
CS-202 C. Papachristos
class DynamicMatrix {
public:
// 1) instatiates a [0]x[0] NULL matrix
DynamicMatrix();
// 2) instatiates a [rows]x[cols] matrix with all elements set to [value]
DynamicMatrix(size_t rows, size_t cols, int value=0);
// 3) instantiates via matrix copy
DynamicMatrix(const DynamicMatrix & otherDynamicMatrix);
// 4) destroys matrix and deallocates dynamic memory
~DynamicMatrix();
// 5) assignment operator
DynamicMatrix & operator=(const DynamicMatrix & other);
// 6) parenthesis operator, to be used for [row],[col] indexing
int & operator()(size_t row_pos, size_t col_pos);
// 7) checks if two matrices are by-size-and-by-value equal
bool operator==(const DynamicMatrix & other);
private:
size_t m_rows;
size_t m_cols;
int * * m_matrix;
};
Finals Sample – Program 2
CS-202 C. Papachristos
DynamicMatrix::DynamicMatrix(){
m_matrix = nullptr; //initialize pointer(s) to NULL
m_rows = 0; //defensive strategy sometimes desired
m_cols = 0; //defensive strategy sometimes desired
}
DynamicMatrix::~DynamicMatrix(){
// check that top-level pointer is not NULL
// (otherwise cannot index by it m_matrix[i] to call delete on row(s) subarrays)
if (m_matrix){
for (int i=0; i<m_rows; ++i){
delete [] m_matrix[i]; // delete subarrays via pointers of top-level array
}
delete [] m_matrix; // delete top level array of pointers
}
}
Finals Sample – Program 2
CS-202 C. Papachristos
DynamicMatrix::DynamicMatrix(size_t rows, size_t cols, int value){
//get new m_rows, m_cols values
m_rows = rows;
m_cols = cols;
//allocate memory
try{
m_matrix = new int * [m_rows]; //allocate memory for rows (array of pointers to row subarrays)
for (size_t i=0; i<m_rows; ++i) //initialize all these pointers to NULL
m_matrix[i] = nullptr;
for (size_t i=0; i<m_rows; ++i){
try{
m_matrix[i] = new int [m_cols]; //allocate memory for row i (subarray of int(s))
}
catch(const std::bad_alloc & ex){ //delete all row(s) i that were allocated before
for (size_t i_del=0; i_del<i; ++i_del)
delete [] m_matrix[i_del];
throw ; //re-throw the original exception
}
}
for (int i=0; i<m_rows; ++i) //reached this far, now initialize matrix with values
for (int j=0; j<m_cols; ++j)
m_matrix[i][j] = value;
}
catch(const std::bad_alloc & ex)
{
delete [] m_matrix;
}
}
Finals Sample – Program 2
CS-202 C. Papachristos
DynamicMatrix::DynamicMatrix(const DynamicMatrix & otherDynamicMatrix){
//free current memory first
if (m_matrix){ //check that top-level pointer is not NULL
for (size_t i=0; i<m_rows; ++i){ delete [] m_matrix[i]; }
delete [] m_matrix;
}
m_rows = otherDynamicMatrix.m_rows; // get new m_rows, m_cols values
m_cols = otherDynamicMatrix.m_cols; // get new m_rows, m_cols values
try{
m_matrix = new int * [m_rows];
for (size_t i=0; i<m_rows; ++i)
m_matrix[i] = nullptr;
for (size_t i=0; i<m_rows; ++i){
try{
m_matrix[i] = new int [m_cols];
}
catch(const std::bad_alloc & ex){
for (size_t i_del=0; i_del<i; ++i_del)
delete [] m_matrix[i_del];
throw ;
}
}
for (size_t i=0; i<m_rows; ++i) //reached this far, initialize matrix with otherDynamicMatrix
for (size_t j=0; j<m_cols; ++j)
m_matrix[i][j] = otherDynamicMatrix.m_matrix[i][j];
}
catch(const std::bad_alloc & ex)
{
delete [] m_matrix;
}
}
Finals Sample – Program 2
CS-202 C. Papachristos
DynamicMatrix & DynamicMatrix::operator=(const DynamicMatrix & otherDynamicMatrix){
if (this != &otherDynamicMatrix){ //check for self-assignment first
//free current memory first
if (m_matrix){ //check that top-level pointer is not NULL
for (size_t i=0; i<m_rows; ++i){ delete [] m_matrix[i]; }
delete [] m_matrix;
}
// get new m_rows, m_cols values
m_rows = otherDynamicMatrix.m_rows;
m_cols = otherDynamicMatrix.m_cols; // get new m_rows, m_cols values
try{
…
… // 2d array allocation handling here
…
}
catch(const std::bad_alloc & ex)
{
delete [] m_matrix;
}
}
//return calling object
return *this;
}
Finals Sample – Program 2
CS-202 C. Papachristos
bool DynamicMatrix::operator==(const DynamicMatrix & otherDynamicMatrix){
//checking for equality pre-requires equal rows, cols
if (m_matrix==nullptr || otherDynamicMatrix.m_matrix==nullptr ||
m_rows!=otherDynamicMatrix.m_rows || m_cols!=otherDynamicMatrix.m_cols){
return false;
}
for (size_t i=0; i<m_rows; ++i){
for (size_t j=0; i<m_cols; ++i){
if (m_matrix[i][j] != otherDynamicMatrix.m_matrix[i][j]){
return false;
}
}
}
return true;
}
int & DynamicMatrix::operator()(size_t row_pos, size_t col_pos){
return m_matrix[row_pos][col_pos];
}
Finals Sample – Program 3
CS-202 C. Papachristos
Dynamic Data Structure Class Templates
template <typename T> // DDS (Queue) class template
class Queue{
friend std::ostream & operator<< <> (std::ostream & os, const Queue<T> & queue);
public:
Queue();
Queue(size_t size, const T & value = T());
Queue(const Queue<T> & other);
~Queue();
Queue<T> & operator=(const Queue<T> & rhs);
T & front(); const T & front() const;
T & back(); const T & back() const;
void push(const T & value);
void pop();
size_t size() const;
void clear();
void serialize(std::ostream & os) const;
private:
Node<T> * m_front;
Node<T> * m_back;
};
Finals Sample – Program 4 - A
CS-202 C. Papachristos
#include <iostream>
#include <cstring>
using namespace std;
int my_series (int n) {
if (n > 1)
return my_series (n-1) - my_series (n-2);
else if (n == 1)
return 1;
else if (n == 0)
return -1;
else
exit(1);
}
int main()
{
for (size_t i=0; i<10; ++i)
cout << my_series(i) << endl;
return 0;
}
Output:
-1 1 2 1 -1 -2 -1 1 2 1
Finals Sample – Program 4 - B
CS-202 C. Papachristos
#include <iostream>
#include <cstring>
using namespace std;
void rec (int n){
if (n < 0){ // base case here is never reached, modulo is positive or zero
cout << n << endl;
}
else {
rec( n / 10 );
cout << ( n % 10 ) << endl;
}
}
int main()
{
rec(123);
return 0;
}
Finals Sample – Question 1
CS-202 C. Papachristos
#include <iostream>
#include <string.h>
using namespace std;
class MyException{
public:
// instantiates and initializes info string
MyException(const char * s) : m_info(s){ }
// sets info string to desired value
void setInfo(const char * s){ m_info = s; }
// handles output of exception object data (info string)
friend std::ostream& operator<<(std::ostream & os,
const MyException & e){
os << e.m_info;
return os;
}
private:
std::string m_info;
};
class A{
public:
A(){ cout << "A" << endl; }
~A(){ cout << "~A" << endl; }
};
Finals Sample – Question 1
CS-202 C. Papachristos
int main(){
try{
A anA;
try{
A anotherA;
//error detected
throw MyException("Something awful happened here...");
}
catch(MyException & e){
cerr << e << endl;
e.setInfo( "It's been taken care of!" );
throw;
}
}
catch(const MyException & e){
cerr << e << endl;
}
return 0;
}
Output:
A
A
~A
Something awful happened here...
~A
It's been taken care of!
class A{
public:
A(){ cout << "A" << endl; }
~A(){ cout << "~A" << endl; }
};
class MyException{
public:
MyException(const char * s) : m_info(s){ }
void setInfo(const char * s){ m_info = s; }
friend std::ostream& operator<<(std::ostream & os,
const MyException & e){
os << e.m_info;
return os;
}
private:
std::string m_info;
};
Time for Questions !
CS-202
CS-202 C. Papachristos