cs 247 - software engineering principles

[   about   /   course notes   /   blog   /   contact   ]

light    dark

---

2019-05-02
term: 2B

Software Engineering Principles, taken in Spring 2019.

meta

Software Engineering: collection of principles and practices, techniques, processes, tools… that aim to improve software quality, dev productivity, scalability to larger systems, evolvability, more hot words here…

website: student.cs.uwaterloo.ca/~cs247

personel

marks

Course Overview


---


software engineering principles

c vs c++ : why don’t we use c for OOP?

c can do OOP, but:

  1. doesn’t support inheritance naturally (quirk of c)
  2. can’t control scope (c has no namespace, c++ uses :: to choose scope)
  3. structs only that are “default constructed”, but can’t define/implement ctors
  4. variables need to be allocated and initialized (you need to malloc and free yourself, very inconvenient)

Hence c isn’t as well suited for OOP as c++.

adt (abstract data types)

Abstract data types are user-defined types that bundles together: ranges of valid values or data and functions and operations for those values.

ADTs are a means to an end (tool), the client code helps define the ADT’s functionality and only needs to be aware of the interface of the ADT (not the implementation).

Abstracts are the idea of complex data.

Use the compiler or definition to enforce the proper usage/rules of the ADT. i.e. valid ranges of data

example:

#include <iostream>
using namespace std;
int main(){
	cout << "enter rational number (a/b) : ";

	//need to define default ctor for Rational class
	Rational r,p,q;

	//overload >> operator w istream&, return Rational&
	//needs to be ref because:
	//1. modify original value later
	//2. iostream can't be copied, won't compile by value
	cin >> r >> q;

	//overload + operator with Rationals, return by value
	//needs to be by value because new object result
	//if by ref: heap allocate rational ref, manually delete later???
	//no. that's a mem leak.
	p = q + r;

	//overload << operator w ostream, return const Rational&
	// const ref optimized by compiler, faster copy
	cout << q/r;

	//define copy ctor for rational adt
	Rational z{q};
}

Things to define:

  1. the default ctor for the Rational class
  2. overload », «, +, /
  3. define the copy ctor

does an adt have to be a class? nope.

ADT is a concept, not an implementation. The data structure is an implementation of an ADT. For example, we can also implement an ADT with a struct.

Why use c++ classes then?

  1. Construction is guaranteed*
  2. Destruction is guaranteed*
  3. Can enforce legal value ranges using field visibility (encapsulation aka public, private, protected)

*on the stack: not guaranteed if you create an object on the heap aka new and delete

encapsulation is a language mechanism to restrict access to some objects’ components, facilitate bundling of data

On the other hand, c structs:

  1. can’t define member functions (in c, functions are globals where the object is passed in as a parameter, no this, aka functions don’t belong to structs)
  2. can’t make ctors and dtors, only stick with what’s available. Also need to know the size to malloc, can potentially disallow self-referencing classes (which is bad design anyways, you should use pointers)

side note: when you pass an non-pointer object, you pass around a lot more memory than you need. The size of struct/class is at least the sum of the size of all its fields (compiler will set extra variables like vtables to store address of member? functions…), so a pointer is relatively much smaller and is better design.

do you always have to define a default constructor? nope.

Only if there are appropriate defaults to set. i.e. default birthday????? doesn’t make sense.

The original default constructor is implicitly defined. BUT Disappears when you define any constructor.

side note: similarly the default dtor is implicitly defined and disappears when you define a dtor, but you really just need one dtor so lol it’s ok

why use MIL (member initialization list)?

Short answer: used to init data members/fields

example: class::class(param) : my_field(param) {}

Need to use if fields or superclass doesn’t have a default constructor. For example, if a superclass has a constructor with params, it loses the default constructor. Then, you would need to specify the constructor using the member initialization list.

Object Construction Process in C++:

  1. allocate space for the new object
  2. initialize the superclass if needed: will use the default ctor unless MIL tells compiler which ctor to use based on function signature (aka params)
  3. initialize all object members/fields using ctor in order of declaration in the header, unless told to use other ctor and initialize all primitive fields (PoD)
  4. new object’s ctor’s body code runs

Note that object members are created in step 3, but if you reconstruct objects in the body, objects will be created twice

 class A {
 	public:
 		A(){};
 };

 class B {
 	A a;  
 	//will call A's default ctor, creates throwaway A 
 	//before body of ctor also creates an A
 	public: 
 		B(){ 
 			a = A(); 
 		};
 };

What if the superclass’ default constructor does exist? A is constructed twice because once before for all member objects, and once when you get into the body then is move assigned/copied to another “A” object into a, in line a = A();.

If you don’t initialize properly (aka don’t use the MIL), your superclass gets default constructed and then you waste that time because you’ll just overwrite that default constructor in the body again. THIS IS VRY INEFFICIENT AND SLOW >:(

aka you created an object you didn’t want, just to overwrite it again in the object’s constructor. Just initialize A right the first time… don’t initialize an object multiple times.

exaggerated example:

class Foo {
	public: 
		Foo() : size{large}, x{new int[large]};
}

class Bar {
	Foo f;
	#ifdef FAST
		//do the quick things
	#else 
		Bar(size_t x){ 
			//first construct f with large crap
			//unfortunately initialized to random values
			Foo otherF{x}; //fast way, 
			// but ctor body runs after all MIL object construction are done
			// reassign a shit ton of values copying things over... 
			f = otherF;	
			//time consuming :(
		}
}

defining the rational class

class Rational { 
public: 
	Rational();
	Rational(int num, int denum) throw (char const*); 
	explicit Rational(int num);
}

throw (char const*) tells the compiler that the Rational(int, int) ctor may have an implementation of exception catching, might trigger/throw of type char const*

explicit keyword:

class Foo {
public: 
	/*explicit*/ Foo (int x) {};
}

void doBar(Foo f){
	//...
}

In this case: without the keyword explicit, doBar(42) would construct Foo(42) as its param since doBar() only takes in Foo params, because it will try to convert 42 into a Foo somehow

This isn’t always a mistake, but in cases it is.

With explicit on Foo’s constructor, doBar(Foo(42)) would be the only valid usage, and doBar(42) won’t compile.

Helps to catch programmer mistakes.

accessors and mutators

Accessors: will not change state of object, only returns, getter

Mutators: can change content of class, setter, ideally checks client-provided values, may throw error if invalid, can implement exceptions to guarantee

constructor with MIL

Construction should only happens once. In the following order, whichever does it first.

  1. MIL
  2. Class members
  3. Ctor body

MIL is only a ctor thing, not applicable to other functions.

attempt 1

class Rational{
	int num_, denum_;
	
	public: 
		Rational() : num_(0), denum_(0) {};
		Rational(int num_) : num_(0), denum_(0) {};
		Rational(int num_, int denum_) : num_(0), denum_(0) {};
}

Too many constructors, gross. We can replace all that with a ctor with default parameters.

default parameters

compiler will translate Rational(int num_ = 0, int denum_ = 0) : num_(num), denum_(denum) {}; into one with n param, n-1 param, …. 0 param, decreasing from the right.

Order is rightmost/end for defaults, and non-defaults must be on the left/front so that there isn’t any ambiguity.

attempt 2

class Rational{
	int num_, denum_;
	
	public: 
		Rational(int num_ = 0, int denum_ = 0) : num_(num), denum_(denum) {};
		// default parameters must be trailing
}

In this example, Rational will never have a ctor with just a denum_ and no num_. It will have both because both are declared as defaults.

Notice that foo(int x, int y=s, int z) is NOT ok, we can’t put non-default z as the last. Will becomes ambiguous, not formal language, will have multiple meanings…

hence: Default params must be trailing!

In other words, default arguments MUST only appear in the function declaration. Once the default is used in the function call, all next arguments in call must be defaults else ambiguous (the compiler doesn’t see the parameter names)

i.e.

Rational(int, int = 1){}
// above is equivalent to declaring below
Rational(int, int){}
Rational(int) { int = 1; }

copy constructor

Rational(const Rational& r) : num_(r.num), denum_(r.denum) {};

The curly copies. Rational B{A} where A is an existing Rational object, into the new Rational B.

When you can, always use const.

& because if it’s by value, it’ll look for that Object’s copy ctor, which is what you’re currently defining you doof.

Generally, you should always use:

  1. a const reference param whenever you can
  2. a reference param because it’s still quicc
  3. copying by value because you don’t want to change the original (last resort) (good practice, follow this hierarchy)

Doesn’t make too much of a difference for primitives.

overloads on operators

Overloading because even though the function names are the same, they take in different param types (function signature is different, can be guaranteed to call the correct one because Rational is a newly defined class).

Note: Different return type cannot validate a function overload.

This is a BAD overload that compiler will cry about:

int foo();
Rational foo();

Hence, changing the return type and not the parameter types would not count as an overload. It must be in the parameters.

You can define operators (functions with names as symbols) with custom functionality. The only guideline is the function name: operator concat function_symbol.

Operator functions are special functions where instead of calling the function name, you just call the symbol in most cases (has exceptions).

i.e. the copy assignment operator is an overload on the “=” operator

copy assignment operator

Rational& operator=(const Rational& other){
	num_ = other.num_;
	denum_ = other.denum_;
	return *this; //dereference this, which is a ptr
}

Why is the return “this” ? To be able to chain copy assignments i.e. a = b = c = d = e; The execution order would be d = e; c = d; b = c; a = b… nested from the right.

why Rational& ? and subsequently return *this;

  1. We could return a copy by constructing a new Rational, but when we exit the end of the function/the scope, the returned new constructed Rational will be destructed.
  2. Something on the heap exists in the global scope, so can be dereferenced and returned (return by reference).
    • (sidenote: passing/returning by value calls the copy constructor.)
    • (clarification: returning by reference doesn’t actually return just the address, it returns the object at that address, but not as a copy, like that literal original teleported object.)
  3. Also because code like (p=a)++ exists.
    • Order of operation:
      1. a is assigned to p, which is an l-value
      2. operator=() returns p as *this, which is incremented

The first param is implicitly the Rational pointed by the this pointer for operators. Basically def func(self, param1): equivalent of Python, but you don’t need to explicitly state for c++.

operator+: between 2 Rationals

attempt 1 : as a non-member function

Non-member function are outside of the class and don’t have access to private member fields, unless it’s a friend.

Here, the implications of a non-member function mean that operator+() has no access to numerator or denominator (all private fields/members). Thus, must tell the Rational class that this function is a friend, so that we can access all the Rational’s private fields.

Note: we can mark a function as friend multiple times/places.

Rational operator+(const Rational& LHS, const Rational& RHS) { 
	//const ref for speed optimization since no modifications
	//is friend so we can access private fields
	return Rational{LHS.num_ * RHS.denum_ + RHS.num_, RHS.num_ * LS.denum_, denum_ * RHS.denum_}
}

Here, we don’t want to release the information of the private fields to the client, hence declare operator+() as a friend inside the class:

friend Rational operator+(const Rational&, const Rational&);

Note that argument names are not needed in function signature.

Recall that you can declare things many times, but can only define things once.

Drawbacks of attempt 1:

attempt 2 : member function

Rational operator+(const Rational& RHS) { 
	//const ref (2nd term) for speed optimization
	return Rational{num_ * RHS.denum_ + RHS.num_ * denum_, denum_ * RHS.denum_}
};

Only uses one param, because function is within class. Hence the first param is this. Note that because there isn’t a conflict with variable names, we can omit the this->varname. Behaves the same anyways.

Difference from attempt 1:

Generally you should always define member functions as const.

Operator+: between Rational and an Int

We also need to be able to add an int to a Rational. Function overloading: same function name, different parameter types.

Rational operator+(int x) { 
	return Rational{x * denum_ + num_, denum_}
};

Currently, addition between a Rational and an Int is not fully functional: not symmetric because we’re missing int + Rational.

Rational p = r + 7; is defined: r is this when + is called. Rational p = 7 + ris not defined: 7 is this, but no int operator+(const Rational&) defined.

Because of the way the + is called, we can’t have the reverse to be a member function because wherever int is implemented, we don’t have access to modify operations of int. Hence operator+ on an int and a Rational in that order needs to be defined as a non-member function.

We define this function as a friend, even if int doesn’t have private values, Rational does, so it needs to be a friend in the Rational class.

friend Rational operator+(int x, const Rational&);

Implementation:

Rational operator+(int x, const Rational& r){
	return r + x; 
	//which calls operator+(int x)
	//which is implemented
}

Now int + Rational will call Rational operator+(int x, const Rational& r).

Addition now works in both orders.

operator/:

Exactly the same idea as operator+, just different math.

operator«: between ostream and a Rational

friend ostream& operator<< (ostream&, Rational&);

Generally, unless specified or by common sense, your implementation should not have an endl; because:

ostream& operator<< (ostream& out, const Rational& r){
	return out << r.num_ << "/" << r.denum_ ;
}

operator»: between istream and a Rational

Inside the class:

friend istream& operator>> (istream&, Rational&);

Implementation (not a member function):

istream& operator>> (istream& in, Rational& r){
	return in >> r.num_ >> r.denum_;
}

in general, prefer to design non-member, non-friend functions

Why: want to limit the access of privates as much as possible, and implement setters and getters instead. Friendship in c++ must be used carefully.

i.e. if heap, don’t get all, just be able to get root or something. (use accessors and mutators)

Friendship is not commutative unless you friend both sides.

rvalues and lvalues

tl;dr:

R-Value (return value)

The return value of foo() is guaranteed to not exist after the foo() statement. R-values in c++ are temporary values: lives in a register without an address.

R-values only appear on the right hand side.

Node foo() {
	Node p ....
	return p;
}

int main() { 
	Node n = foo();
}

Note here, you can’t call bar() on an r-value, because its type is an l-value reference of 5+3. Since 5+3 is stored in a register temporarily, no address so none to pass to bar().

void bar(int &x){
	... some assignment command idk
}
int main(){
	bar(5+3); //doesn't work
}

UNLESS 5+3 is const: the compiler will allow it by potentially creating a temporary address. Since it’s const, the compiler knows that you won’t mutate it, so the address can be created.

You can’t bind an r-value to an l-value.

L-Value (lifetime value)

The opposite of an r-value, it’s guaranteed to have a memory address and has a lifespan past the individual statement.

L-values can appear on the left hand side, except const l-value (can’t be assigned).


Foo doFoo(Foo &&f){

}

int main(int argc, char const *argv[])
{
	Foo f;
	doFoo()
	return 0;
}

linked list by hand attempt 1

We want the client to do: Node n{3,new Node{2, new Node{}}};, which makes a linked list of 3->2->1.

Also needs this functionality:

Node p{n};
p.next->data = 20;
cout << p; //expected: 3, 20, 1
cout << n; //expected: 3, 2, 1

Tangent: what’s a string? it’s an array of char even in C++, just wrapped in a handy String class.

constructor attempt 1

We want deep copy, implemented using recursion. (Not going to worry about encapsulation rn).

Why did we want deep copying? Lists need to be distinct. But is there any duplication? Nope, it’s guaranteed that the original copy will die after the line of creation. (r-value)

class Node {
public: 
	int data_;
	Node *next_;
	//constructor
	Node (int data, Node *next_ = nullptr); 
	//deep copy constructor with recursion
	Node (const Node& other) : data {other.data}, 
		next {other.next? new Node{*other.next} : nullptr};
	//base case == next is nullptr, and normal case
}

Knowing r-values, we actually don’t need to deep copy the list.

constructor attempt 2 (move constructor with shallow copy)

Sidenote: Node (Node &&o) is not a reference to a reference, it’s the ref of an r-value.

We have temporaries to copy (i.e. move constructor) but we don’t want to deep copy because that’s slow. (And don’t care for deep copying).

How else can we move it? Shallow copying the pointer.

Node (Node &&o): next{o.next}, data{o.data}{
	o.next = nullptr;
}

When you move o.next, it immediately dies and frees its list, so we reset o.next to a nullptr so that it doesn’t deallocate the list we just stole with the MIL. So instead, it’ll become a dangling pointer, it doesn’t delete the list immediately.

NOTE: that o is a reference to an r-value. But o as a parameter is not an r-value: o.data is an l-value.

what is data{o.data} ??? We don’t want to call the copy constructor because o is about to die and we don’t want to deep copy it. Let’s move o.

data{o.data} calls the string’s copy constructor. BUT we want to treat this thing as an r-value, because we know that it’s an r-value.

Solution: std::move overrides the compiler’s decision, swaps it like an r-value.

using std::move;
Node (Node &&o): next{o.next}, data{o.data}{
	o.next = nullptr;
}
Node::Node(Node &&other) : data_{std::move(other.data_)}, next{other.next} {
    other.next = nullptr;
}

a little bit like casting.

copy assignment

copy assignment operator attempt 1

Node& operator= (const Node &other){
	data = other.data;
	delete next;
	next = new Node{other.next} //BUT new might fail
	return this;
}

Reasons why new would fail:

  1. run out of memory
  2. OS tells the process “no.!” i.e. if your OS limits your program’s resource

What’s wrong if new fails?? It’s not NULL, it’s a dangling pointer. If you dereference a dangling pointer, you won’t segfault, but you’ll get garbage instead :(

If new fails, we want to ensure that our Node doesn’t get mutated. How? Call new first.

copy assignment operator attempt 2

Node& operator= (const Node &other){
	Node &tmp = new Node{other};
	data = other.data;
	delete next;
	next = tmp; //there is no tmp when you delete next = tmp
	return this;
}

A failed new could be handled by exceptions now. Better to write this way.

First copy, then delete, also solves another issue. What happens with :

Node n ....;
n = n;

Self-assignment, assigning this object to reference. When you delete next, you’re freeing the memory for the next pointer

When you try to deep copy other’s next pointer, you

Trying to reference a dangling pointer is a memory error. The copy and swap idiom solves this issue, but you’re still doing a deep copy unnecessarily.

Solution: if self-assignment, return this. Two addresses are the same, if they reside in the same location in memory. Check for self-assignment by if (this == &other) return *this;

copy assignment operator attempt 3: copy and swap idiom

Node& operator= (const Node &other){
	Node tmp{other};
	using std::swap;
	swap(data,other.data);
	swap(next,other.next);
	return *this;
}

destructor (memory leak handling)

~Node() { delete next; }

Explicitly calling the destructor for next isn’t enough. How to deallocate the next Node?

Every time there is a new, there must be an equal and opposite delete.

When you delete a heap-allocate object, it goes out of scope and gets destructed. The idea of recursion calls each element next on the list, which handles the rest of the nodes.

At the end, delete the nullptr and then we’re good.

move assignment operator

move assignment operator attempt 1

Node& operator= (Node && other){
	data = other.data;
	next = other.next;
}

This would fail test cases. Once other goes out of scope, the list gets deleted.

move assignment operator attempt 2

Node& operator= (Node && other){
	data = other.data;
	delete next;
	next = other.next;

}

Memory leaks. Better than

move assignment operator attempt 3

#include <utility>

Node& operator= (Node && other){
	using std::swap;
	//within this scope, swap is from std
	swap(data,other.data);
	swap(next,other.next);
	return *this;

}

Why swap instead of assigning? Easier to implement, more memory efficient than copying. We reused swap, might as well create a private swapping function.

closing notes of the linked list

Client can break rules…

Node n {3, new Node{2, nullptr}}
{
	Node p{4, &n}
}

Error with constructing Node p

p will go out of scope when exiting the code block, and runs p’s destructor, which calls delete on the next pointer. BUT!!! the next pointer was a stack-allocated address, can’t call delete on that! Even if n is heap-allocated, then n is still going to end up as a dangling pointer, which is not good behavior.

Hence, we have some rules that we must uphold so that our ADT can work properly. Rules are a result of some assumptions we made when writing the code.

invariants

Invariant: assumptions or properties that must hold for the code to work properly. Assumption example: delete next; in destructor, (either assume that object is always a heap-allocate object, or it’s never a heap-allocated object).

You cannot trust that your client code will uphold your invariants. Also, they shouldn’t have to. Don’t expect the client to memorize all your rules.

summarizing the big 5

  1. copy constructor
  2. move constructor
  3. copy assignment operator (cao)
  4. move assignment operator (mao)
  5. destructor.

General rule of thumb: all or nothing

If you have to provide a user-defined definition for one of these above, you should define all of them.

built-in default behaviour:

  1. copy constructor: copies all values and copy constructs all fields (shallow copy, bad for pointers because you only copy the value, hence have multiple pointer pointing to the same space, and deletion will leave other pointers pointing to garbage).
    //To delete this ctor, you're going to have to explicitly define it as `= 0;`
    //Defining the copy constructor will not delete the default move constructor
    //may be both lies
    
  2. move constructor: move all values, shallow move bad for pointers.

  3. copy assignment operator (cao): copies all fields and copy assigns all fields

  4. move assignment operator (mao): move all fields and move assigns all fields
    //Note that if the MAO is defined, you lose the default CAO
    
  5. destructor.

destructor

Use destructor when an object goes out of scope. If heap allocated, then when object’s delete is called. If stack allocated (statically allocated), when their enclosing scope ends.

class B {};
class A {
	B b;
}
A *p = new A;
delete p;

Object A pointed by p is dynamically allocated. Object B pointed by p is on the heap (created as part of A), is statically allocated. When *p dies, b dies as well.

copy constructor

  1. Uses copy ctor when you construct an object with another object of the same type.
  2. When a function receives an object parameter by value
  3. when a function returns a value except when a move constructor is defined (because then the move ctor is used to return a value)

If case 1, 2 use an r-value as the argument, then the move ctor is used as well.

The compiler provides built-in implementations of ctors: the copy ctor executes a byte-wise copying all plain old data PoD (int, char, bool, all basic types, pure structures) and copy constructs all object fields.

Doing a byte-wise copy on pointers is insufficient, because you’d copy the pointer’s address and not make a new object. Hence copy ctor was redefined for the linkedin.

The built-in move constructor also does byte-wise

The copy assignment operator byte-wise copying all PoD, and copy assigns all object fields.

You’ll lose efficiency if you only define the CAO, it will never use MAO because it’s not defined.

invariants

assumptions that must hold true for our code to work properly. It’s hard/impossible to reason about the code without them.

i.e.

^^^ but currently we have no control over these

Should not be the client’s responsibility to know and uphold the rules. Why can the client break these rules:

There is currently no checks in constructor: this allows the client to select the next pointer (next Node), but we can’t guarantee that clients use them properly.

representation exposure

Allowing the client to use nodes at all is representation exposure. Representation exposure is external access to the implementation of the ADT, meaning that client code can modify the representation directly.

The ADT we want to give to the client is a linked list, not Node pointers. The clients really shouldn’t know how the linked list is implemented (or all the invariants of the implementation).

THEREFORE: we want to encapsulate the implementation logic and hide it from the client

linked list by hand attempt 2

i.e. usage

List l;
l.push(3).push(2).push(1); 
//{1,2,3}
l.ith(i) = 5;
//list.h
class List {
	class Node {
		//private nested member
		//implement as before
	}
	Node *head;
public: 
	List() head {nullptr};
	List& push(int data);
	//Big 5 for lists:
	int& ith(int i);
}
//list.cc
List::Node::Node(int data, Node *next) ...
List& List::push(int data) {
	head = new Node { data, head };
	return *this;
}

Changing the header file: client code needs to recompile

Changing the cc file: client code doesn’t need to recompile???

reference is just part of a type signature

Giving integers by reference

int & List::ith(size_t i) {
	Node * node = head;
	while ( i > 0 && node){
		--i;
		node = node->next;
	}
	return ith->data;
	//crashes if node
}

Why is ith() bad??? Look at this client code:

#include <iostream>
using namespace std;

...
list l; 
size_t (....)
for (size_t i = 0; i < len; ++i){
	out << l.ith(i) << endl
}

ith() takes to iterate through a list…

We need to give user a similar way to iterate through the lists as they did before, but not expose the representation, and improve on the runtime.

What we want is an iterator:

See client code:

for (thing = beginning of list; thing != end of list; ++thing){
	*thing = *thing + 1;
	cout << *thing;
}

What helpers/components do we need to implement an iterator??

  1. get the beginning of list::iterator i.e. list::begin()
  2. get the end of the list::iterator i.e. list::end()
  3. be able to increment the list::iterator
  4. implement the unary star operator (*) dereference operator
  5. need inequality (and equality is nice to have )

What private data do we want to put in the iterator?

class List {
	Node* head;
public:
	class Iterator {
		Node *curr;
	public: 
		bool operator != (const Iterator&);
		Iterator& operator++;
		int& operator&();
		friend class List;
	}
};
//back in the List struct definition
Iterator begin();
Iterator end();
//@list.cc
List::Iterator List::begin() {
	return Iterator{head};
}
List::Iterator List::end() {
	return Iterator{nullptr};
}

the iterator pattern

(our first design pattern)

The design pattern is a common solution to a common patterns

(missing singleton things :(((( )

entity adt

i.e. physical objects, people, records, transactions

value adt

i.e. mathematical types, measurements, quantities of money, colour/location/time properties, restricted value sets like postal codes/number ranges

example of adt

entity: people, planes, runways, bookings, deck, card, player,

value: rational, lists, units of measurement, point, force, birthdates, suit, score

mutable vs immutable objects

mutable objects change via mutators (set()) or other functions that act on them

value-based objects are usually not mutable.

immutable object:

example: license plate adt

license plate is an adt value is a value, but simplifying

requirements:

examples:

operator< for sorting

assumptions:

  1. plates are issued in order
  2. vanity plates can’t be duplicates/replace old vanity plate

== we need information about all license places created, and hence, we need some state that is maintained not just within the lifetime of an object, but across the entirely of that class. (i.e. cd)

static member variable

essentially a global variable (that’s how the compiler will implement this), but with some extra context and properties (scope…)

All objects share the same variable.

class Foo {
	int x;
public: 
	static int count;
	Foo(int x) : x{x} {++count;}
	static void 
}

can’t define twice, so we need to put the definition in foo.cc can declare things as much as you want

class Foo; //declaration
class Foo; //declaration
class Foo; //declaration
class Foo {}; //definition
foo.cc //implementation

You can write the definition outside of a class, but you would never be able to use it.

int main(){
	Foo f{5};
	Foo f2{10};
	cout << f.count << " " << f2.count << endl;
	cout << Foo::count << endl;
	Foo f3{7}
	f.printCount();
	Foo::printCount();
}

we probably also want a helper, to increment our next available

class License Plate {
	static std::string nextAvailable;
	std::string plateNo;
	static void updateAvaliable();
public: 
	LicensePlate();
	LicensePlate(std::String);
	Bool op
}

adding a header guard

#ifndef LICENSE_H
#define LICENSE_H

#endif

To avoid files that include files that include headers, hence the headers would be copied twice, which is not good. Remember, the rule is to define only once, but can declare many times.

i.e.

//a.h
#include "b.h"

//main.cc
#include "a.h"
#include "b.h"

When you include, it copies from a.h to main.cc, but a.h also has a copy of b.h. The compiler will complain that of multiple definition compile error. Using #ifndef and #define means if-not-defined, define, which is a header guard.

If you wrap your header with the header guard, then preprocessor will execute checks and only copy if needed. Any subsequent includes will have no effect, when using the header guard.

implementing the license plate entity adt

Attempt 1: simplification to ignore vanity plates

So far, we’ll need class LicensePlate, with plateNo, and ctors.

license.h

class LicensePlate; is a forward declaration

class LicensePlate{}; is a definition, and hence needs to be header-guarded.

#ifndef LICENSE_H
#define LICENSE_H
#include <string>

class LicensePlate{
	static int fourDigits;
	static char charOne, charTwo, charThree;
	static void updateNextAvailable();
	std::string plateNo

	public:
		LicensePlate();
		LicensePlate(string::string name);
		//this is a bad idea 
		//License(std::string vanityPlate = "");
};
#endif


Why is License(std::string vanityPlate = ""); a bad idea? i.e. if empty string, then not a vanityPlate.

Make things behave as expected! Weird case where the user tries to create a vanity plate with an empty string should return an error, not a normal plate. Compiler should at least complain (if not using exceptions).

Why don’t we write using namespace std in the header as well?? Because it’ll also pull in the namespace into the .cc whenever included. The headers should not enforce which namespace to use.

You should actually NEVER use using namespace ... for header files. Try to include as little as possible.

overloading input operator

public:
	bool operator<(const LicensePlate &other) const;

Declare functions as const whenever possible!

license.cc

As opposed to the header files, include all that you need, even twice. Be thorough.

#include "license.h"
#include <string>
#include <sstream>
using namespace std;

int LicensePlate::fourDigits = 0000;
char LicensePlate::charOne = 'A';
char LicensePlate::charTwo = 'A';
char LicensePlate::charThree = 'A';

void LicensePlate::updateNextAvailable(){
	if (fourDigits < 9999){
		++fourDigits;
		return
	} else if (charThree == 'Z'){ //last char
		if (charTwo == 'Z'){
			++charOne; //assume not Z
			charThree = charTwo = 'A';
		} else {
			++charTwo;
			charThree = 'A';
		}
		fourDigits = 0;
		return ;
	}
	fourDigits = 0;
	++charThree;
	//build in constructor
	return; 
}

LicensePlate::LicensePlate(){
	//combine all together
	//write to io string stream
	stringstream ss; 
	stringstream charStream; 

	//init and set ss properties
	ss << setfill('0') << setw(4);

	//combine all these types in one string!
	charStream << charOne << charTwo << charThree << "-";
				string(charThree);
	
	string numberString;
	// will grab the first set of contiguous non whitespace set of num
	ss >> numberString;
	plateNo = charStream.str() + numberString();
	updateNextAvailable();
}

void LicensePlate::nextPlate(){
	
}

iostreams: use the most suitable one depending on whether you need to input/output…

ISSUE: can copy construct license plates, which doesn’t make sense because license plates are unique. By default, copy ctor exists.

Options:

  1. define move ctor and operator
  2. define copy ctor as private functions so that users outside cannot use it
  3. LicensePlace(const LicensePlate&) = delete; LicensePlace &operator=(const LicensePlate&) = delete; gives “use of deleted function” error message

compiling without a main

g++ -std=c++14 -c myfile.cc

-c means to compile only, no linking of code. Will only compile the given inputs into corresponding myfile.o

ex1

This is very important as we need it for separate compilation:

ex2

This compiles both and then links: g++ -std=c++14 main.cc license.cc -o myProgram

changes

What happens if I change main.cc? Need to run g++ -std=c++14 -c main.cc and g++ license.o main.o -o myProgram in the first example.

What if license.h changes? Recompiles every .cc file that has a true compilation dependency with license.h. A true compilation dependency includes license.h when compiling the file with the dependency.

Compiler needs to know how

If it’s not a true dependency, don’t introduce dependencies by including files, just forward declare:

//a.h
class A{}

//b.h
class A;
class B{
	A* a;
	//forward decl is enough
	//no instantiation
	//compiler always know size of ptrs
}

//c.h
#include "a.h"
class C{
	A a;
	//stores A in C, needs to include
}

//d.h
class A;
class D{
	A& a;
	//references may not take up space
	//compiler implement with ptr
	//not actually storing A in D
	//no compilation dependency
}

//e.h
#include "a.h"
class E : public A{
	//size of class E depends on class A
	//true compilation dependency
}

//f.h
class A;
class F{
	A myFunction(A a);
	//implementation will need to know about A
	//but declaration does not require A
}

The goal is to not have to include lots of headers in the header files.

Only include when you absolutely must. Else, if possible, just forward declare. Modularize!

A header (interface) fle and its corresponding .cc file (implementation) together is a module.

We want to break ou programs up into small distinct reusable modules. This means that our program will be split up into many files that we need to compile and link… huge time consuming task for the programmer. Tool: Makefiles using make

makefiles

output_target_name: dependencies.o instruction to compile

i.e

myprogram: main.o
<tab> linking command
myprogram: main.o list.o iter.o node.o
	g++-5 -std=c++14 main.o list.o iter.o node.o -o myprogram

main.o: list.cc list.h node.h
	g++-5

list.o: ...

Go into directory with the Makefile and run make to build. Run make clean to build the clean target instead the first listed target.

g++-5 is version 5, can say g++

Variables in Makefiles:

CXX = g++-5
CXXFLAGS = -std=c++14 -Wall
#CXXFLAGS = -std=c++14 -Wall -MMD
EXEC = myprogram
OBJECTS = 

-MMD automatically infer dependencies using header files. Then, the Makefiles results in:

${EXEC}: ${OBJECTS}
	${CXX} ${CXXFLAGS} ${OBJECTS} -o ${EXEC}

heap or stack allocated

need to know that constructor exists.

virtual functions - a reintroduction

struct Book
{
	int typeFlag; //0
	int numPages;
	char* title;
	char* author;
};

struct Comic
{
	int typeFlag; //1
	int numPages;
	char* title;
	char* author;
	char* hero;
};

struct Text
{
	int typeFlag;
	int numPages;
	char* title;
	char* author;	
	char* subject;
};

int isItHeavy (void *bp){
	int *ip = (int*)bp;
	if (!*ip){
		return *(ip+1) > 200;
	} else if (*ip == 1){
		return *(ip+1) > 50;
	} else if (*ip == 2){
		return *(ip+1) > 100;
	}
}
class Book{
	int numPages;
	std::string title, author;

public: 
	Book(int numPages, std::string title, std::string author);
	virtual book isItHeavy();
}

//Comic.h

class Comic : public Book {
	std::string hero;
public: 
	Comic(int numPages, std::string title, std::string author, std::string hero);
	bool isitHeavy() final override;
}

final keyword:

override keyword:

i.e.


Book* pb = new Comic(75, "C++ Man Saves the Day", "Bjarne Stroustrup", "Compiler");
pb.isitHeavy(); 

Compiler produces an error about overrides because the function name isn’t the same (either that, or the function signature), and hence isn’t overridden.

//Book.cc
Book::Book(int numPages, string title, string author): numPages{numPages}, title{title}, author{author}{}
bool Book::isItHeavy(){ return numPages>200 }
//Comic.cc

Comic::Comic(int numPages, string title, string author, string hero){
	this->numPages = numPages;

}

Why won’t this compile?

  1. numPages, title and author are all private fields of Book, so we can’t even change them.

  2. No specification on how to construct Book. The steps of object creation will construct numPages, title, and author from the superclass Book, before constructing the fields of the base class. However, because this isn’t specified in the MIL, then Book will try to default construct, which doesn’t exist.

Note that this applies to all fields that need to be initialized: i.e. const fields, references

comic attempt 2

Make a getter to access private fields.

//Book.cc
int Book::getNumPages(){ return numPages; }
//Comic.cc
Comic::Comic(int numPages, string title, string author, string hero) : Book{numPages, title, author}, hero{hero} {}
bool Comic::isItHeavy(){ return getNumPages() > 50; }

Text class will look similar, with different fields.

Book *pb = new Book(150, "Jabronis", "Dwayne the Rock", "Johnson");
Book *pc = new Comic(150, "Jabronis", "Spider Man vs the Prague", "Stanley", "Spider-Man");
Book *pd = new Text(300 ...);

cout << pb->isItHeavy(); //False
cout << pc->isItHeavy(); //True
cout << pd->isItHeavy(); //False
int main(int argc, char* argv){
	string whatToMake{argv[1]};

	Book *pb;
	if (whatToMake == "Book"){ pb = new Book{150...}};
	else if (whatToMake == "Comic") ...;
	else if (whatToMake == "Text") ...;
	pb->isItHeavy(); //prints????	
}
#include <iostream>

struct A {
	int x = 5;
	void foo() {cout << x << endl;}
};


struct B {
	int x = 5;
	virtual void foo() {cout << x << endl;}
};

why is it different??

For classes with virtual functions, the compiler will store an extra pointer in those objects (B). That pointer is what allows the compiler to do virtual dispatch. (Not reading into the future).

abstract classes and abstract base classes (abc)

The interface of BoolExpression: Can (and in some cases, must) have an implementation.

class BExp {
	public: 
		virtual bool evaluate() = 0;
		virtual ~BExp(){} // to NOT leak mem
}

=0 declares this function as pure virtual, essentially says that this function has no implementation. But pure virtual doesn’t mean that there is for sure no implementation (not an IFF relation)

A class with at least one pure virtual function is called an abstract class. You cannot instantiate objects of an abstract class.

BoolExpression b; is not ok, because no way of creating it.

If you can’t create objects, what are they good for???? Well, they are used as the base class in a hierarchy to define the interface.

= Abstract Base Classes (ABCs)

class BinaryOp : public BExp{
	BExp *lhs, *rhs;
	char op;  //"l" or "&"
	//can also use enums
public: 
	BinaryOP(BExp &lhs, BExp *rhs) : lhs{lhs}, rhs{rhs} {}
	bool evaluate(){
		if (op == '&') return (lhs->evaluate() && rhs->evaluate());
		else if (op == 'l') return (lhs->evaluate() && rhs->evaluate());
	}
	~BinaryOP(){ delete lhs; delete rhs; }
}
class UnaryOP : public BExp {
	BExp *child;
public:
	UnaryOP (BExp *child) : child{child} {}
}

Atom = Atomic Node

class Atom : public Bexp {
	bool val;
public:
	Atom(bool)
}

class NegOP : public BExp {
	BExp *child;
public:
	NegOP (BExp *child) : child{child} {};
	bool evaluate() {
		return !child->evaluate();
	}
	~NegOp() { delete child; }
}
int main() {
	BExp *b - new BinaryOP { new BinaryOp { new Atom {false}, new Atom{true}, 'l'}, new NegExp {new Atom {false}}, "&"}
}

When we call delete, the destructor of the function will indeed call binaryOp’s destructor through virtual dispatch. We need to make sure that the correct destructor is called. Hence destructors should ALWAYS be virtual

4 phases of object destruction:

remember that creation is:

  1. allocate space
  2. make superclass
  3. create object fields
  4. run ctor body

hence destruction is in this order:

  1. destructor’s body runs
  2. fields that are objects get destroyed
  3. superclass component gets destroyed
  4. dealloc/delete space

Recall our book hierarchy :

Book, Comic : public Book, Text: Public Book.

Book &operator= (const Book &other){
	numPages = other.numPages;
	title = other.Title;
	author = other.Author;
	return *this;
}

Comic &operator= (const Comic &other){
	Book::operator=(other);
	hero = other.hero;
	return *this;
}

Text &operator= (const Text &other){
	Book::operator=(other);
	topic = other.topic;
	return *this;
}
Book *b = new Book {...};
Book *c = new Comic{...};
*c = *b;

class Book{
	Book& operator=() ...
}

Note that they aren’t virtual. Will call book’s assignment operator, because the compiler sees 2 Book pointers, and has an operator between 2 dereferenced book references.

class Book {
	virtual Book &operator=(const Book*);
}
class Comic {
	Comic &operator=(const Comic*, &other);
}

Not a valid override, because parameter list is different. Book != Comic ultimately. Can say this though: Comic &operator=(const Book*, &other);, because Comics are Books.

Oh no.

r2hackma’s words: Shouldn’t implement them virtually.

*c = *b

return type of dereferenced Book pointer, gives you Book reference. Virtual function does virtual dispatch

LHS will virtual dispatch, at Comic’s assignment operator.

A text is a book, and now you’re being able to

If the copy assignment operator is non-virtual, then assignment through base class pointers only does the base class assignment (called the partial assignment).

If it is a virtual function, then the parameters has to be a base class reference, and you get mixed assignments (i.e. a comic to a text).

If it isn’t a virtual function, then we have partial assignment.

Can’t be non-virtual, but can’t be virtual…. Does assignment through base class pointers make sense??

Assignment through base class pointers is generally a bad idea. We would like to disallow this.

disallowing

Attempt 1: make book assignment operator protected. Issue: users can’t assign books then.

Attempt 2: make all base classes abstract

Instead of:



The structure of OOP should be:

class AbstractBook {
	int numPages;
	std::string title, author;

protected:
	AbstractBook &operator=(const AbstractBook &other){
		numPages = other.numPages
		...  
	}
public: 
	//rest of book class as before
	virtual ~AbstractBook() = 0;
}

Note that the destructor should always be pure virtual, so that it can be abstract class.

Note2: leave isItHeavy() as pure virtual, so that we have at least one pure virtual, so that it can be an abstract class.

//AbstractBook.cc
AbstractBook::~AbstractBook(){}

What does this mean?

This implementation solves our problems. You can’t base class assign something that you can’t create.

chess board example

class CheckBoard {
	char **board;
public: 
	ChessBoard();
	void PrintBoard();
	void PlayTurn(string s);
	...
}

void ChessBoard::PrintBoard(){
	for (int y = 0, y < height; ++y){
		for (int x = 0, x < width; ++x){
			cout << board[y][x];
		}
		cout << endl;
	}
}

What if I want to display my code in another stream??? Have to re-implement everything :((

attempt 1: could make the function take in a stream as parameter input. Okay, but what if I want tot display it graphically???

attempt 2: what if I want both textual and graphical???

should my class ChessBoard be talking to the user at all???

Our chessboard shouldn’t be talking to the user at all, it should have only one reason to change: game logic state and display.

single responsibility principle:

A class should have only one reason to change.

We should have a separate display for our model (data).

observer pattern

Subjects: (pub)

Observers: (sub)

class Subject{
	vector<Observer*> obs;
public:
	void attach(Observer* o) { obs.emplace_back(o); }
	void detach(Observer* o) { 
		for (auto it = obs.begin()l it != obs.end(); ++it){
			if (*it == 0){
				obs.erase(it);
				return;
			}
		}
	}
	void notifyObservers(){
		for (auto ob : obs){
			ob -> notify;
		}
	}
}

Note: using an iterator on a mutated vector is undefined behavior!!!!! ^^

for-range: syntactic sugar is syntax within a programming language that is designed to make things easier to read or to express. It makes the language “sweeter” for human use.

class Observer{
public: 
	virtual void notify() = 0;
	virtual ~Observer(){}
}

pure virtual method notify

class HorseRace : public Subject {
	ifstream raceFire;
	string lastWinner;
public:
	HorceRace(string fname) : raceFile {fname}{}
	void doRace(){
		raceFile >> lastWinner;
		notifyObservers();
	}
}
class Bettor : public Observer {
	string name, horse;
	HorceRace *hr;
public: 
	void notify() override {
		cout << name << (horse == hr->getState()? "wins!" : "loses") << endl;
	}
}
Bettor(string name, string horse, HorseRace *hr): name{name}, horse{horse}, hr{hr} {
	hr->attach(this);
}

~Bettor(){
	hr->detach(this);
}

Still have the issue of observers outliving the subject. Can’t live past the data that you’re observing.

If subject goes out of scope before the observer:

HorseRace* hr = new HorseRace{ ... };
Bettor b{..., hr};
Bettor c{..., hr};

delete hr;

Now Bettor b and c are holding the dangling pointer hr, which is already deleted. You don’t want the client to manage the memory.

uml

UML stands for Unified Modeling Language. We’re going to talk about Class Diagrams, with the purpose of communicating OOP design.

Implementation agnostic.

how to show a class in uml

uml example 1

Foo


- myName : string + myAge : int


+ doThing(p : int) : void

relationships in uml

aggregation

Example:

class A{
	vector<B*> bs;
public: 
	~A();
}

Draw diamond to the owner/”contains” class. Draw arrow to the class that it “refers” to.

If A has a B, in general, B’s lifetime is not tied to A. That is:

We can specify multiplicities (how many) relationships. Means that each A object has n B objects.

Means that each A object has 1 to n B objects.

Means that each A object has 0 to infinity/many B objects.

Means that each A object has 4 to infinity/many B objects.

Note: multiplicities on the other side is also valid Means that each B is held by exactly 1 to 3 A.

Here is both: Means that each B is held by exactly one to 3 A, but each A has 2 to many B.

composition

If you copy a subject, it does not own the pointer. LinkedLists want to own pointers of their node, which is a composition relation

specialization

random

class A {
	B b1;
	B b2;
}

A concrete example:

class Resident {
	Address mailing_address;
	Address billing_address;
}

observer pattern in uml

Side note: Inheritance in c++

case 1

class A : public B

All public functions of B are accessible through A as well. the keyword public is a cap, or limit on the visibility of inherited fields or methods.

Which means, you have the same visibility as the class that you inherited from.

class B {
	int x;
protected:
	int y;
public:
	int z;
}

Then in A:

case 2

class A : protected B

A is not a B. Everything public in B is protected in A. This is not a is-a relationship. B should then be a field in A.

In A:

case 3

class A : private B

Everything public and protected in B is private in A. This is not a is-a relationship.

In A:

vectors in c++

#include <vector>

Uses:

Note that curly braces constructor can also be overloaded: as a member list initialization syntax.

Can be overloaded for vectors, gives you the vector with that list as its contents. i.e. vector<string> vec{"..", "..", ....};

template <typename T>
class vector {
public: 
	vector(size_t n, T val); 
}

This constructor creates a vector of n vals. vector<int> ints(3,4); is an vector of {4,4,4,4}. Only confusing when your type T is also size_t.

accessing a vector

Uses:

error handling

vector::at(size_t i) is a checked version of the index operator: checks if the index is out of bounds, and if it is, gets mad.

Error handling is inherently a non-local problem.

attempt 1: error handling with sentinel values

In c:

The sentinel value is a form of in-band data that makes it possible to detect the end of the data when no out-of-band data (such as an explicit size indication) is provided.

Sentinel value not ideal:

attempt 2: c++ exceptions for error handling

The function that detects an error will raise or throw an exception (if it can’t recover itself). don’t use it as your flow control.

Either some caller down the call chain catches that exception, or the program terminates.

Exception in c++ is anything that is thrown: anything in c++ can be thrown. But typically, we would like to use meaningful error classes as exceptions.

To raise an exception, we use the keyword throw.

Note that throws clause is deprecated.

#include <except>
int at(size_t i){
	if (i > mySize){
		stringstream ss;
		ss << "Index: " << i << " out of bounds:" << mySize;
		throw std::out_of_range{ss.str()};
	}
}

The std exceptions all take a string param in their constructor, that is meant to describe what went wrong for error reporting purposes.

example: what does this program print?

int Foo(){
	throw 10;
	cout << "Hi" << endl;
}

int Bar(){
	Foo();
	cout << "Bar" << endl;
}

int main(){
	Bar();
}

when an exception is thrown, the current executing function stops, and stack unwinding occurs.

stack unwinding

Occurs when a function ends, and the function stack frame is popped off.

All stack allocated data is freed, and then the exception/stack unwinding propagates down the call chain, until a matching try/catch is found.

If main propagates an exception, then the program terminates.

Previous example’s unwinding:

  1. Foo throws 10
  2. Foo propagates exception (Hi doesn’t get run)
  3. Bar get exception
  4. Bar doesn’t catch, propagates exception (doesn’t print Bar)
  5. main gets exception, propagates exception
  6. oops program terminates.

With catch modifications:

int Foo(){
	throw 10;
	cout << "Hi" << endl;
}

int Bar(){
	try{
		Foo();
	}
	catch (int) {
		cout << "caught an int" << endl;
	}
	cout << "Bar" << endl;
}

int main(){
	Bar();
}

Exception unwinding:

  1. Foo throws 10
  2. Foo propagates exception (Hi doesn’t get run)
  3. Bar get exception
  4. Bar catches int-type exceptions (foo wrapped in try catch), handles by printing “caught an int” and continues Bar execution (prints Bar)
  5. main does not see exception
  6. main continues program execution

For more information on the error:

int Bar(){
	try { Foo(); }
	catch (int n) { cout << "caught int " << n << endl;}
	cout << "Bar" << endl;
}
try { v.at(100000000); }
catch (std::out_of_range e){
	cout << e.what();
}
catch (int) { ... }
catch (Foo) { ... } 

.what() is a function all the std errors provide that returns the string they were constructed with.

error is passed from function frame to frame similar to a return value.

throw by value, catch by reference

int Foo(){
	throw C{1,2,3};
}

int Bar(){
	try{
		Foo();
	}
	catch (A a) {
		cout << "caught A" << endl;
	}
	catch (B b) {
		cout << "caught B" << endl;
	}
	catch (C c) {
		cout << "caught C" << endl;
	}
}

int main(){
	Bar();
}

First matching handler is executed, in this case the one for A, because C “is-a” A.

similarly, but virtual dispatch

struct X {
	virtual void hi(){
		cout << "x" << endl;
	}
};

struct Y : public X {
	virtual void hi(){
		cout << "y" << endl;
	}
};

struct Z : public Y {
	virtual void hi(){
		cout << "z" << endl;
	}
};


virtual foo() {
	throw z;
}

int main() {
	try{
		foo();
	} 
	catch (X x){ x.hi(); } 
	catch (Y y){ y.hi(); }
	catch (Z z){ z.hi(); }
}

matches the first matching handler, a z is-a x, so the X one matches. X is a local copy of the object thrown, so virtual dispatch doesn’t happen. X::hi() is called, which prints X.

So, general maxim in c++ is throw by value, catch by reference.

int main(){
	try { foo(); }
	catch (X &obj) { obj.hi(); }
	catch (Y &obj) { obj.hi(); }
	catch (Z &obj) { obj.hi(); }
}

The first catch block is still the one that executes, but now virtual dispatch must occur, since the compiler can’t know the runtime type of obj, so it prints out z properly.

When a matching handler is not found, the same exception is being propagated through the call chain until a matching handler is found.

A function can catch an exception, and:

int bar(){
	throw z;
}

int foo(){
	try { bar() }
	catch(x &obj) { throw obj; }
}

int main() {
	try { foo(); }
	catch(z &obj) { throw obj; }

}

foo calls bar, which throws a Z type, that foo catches. But foo’s exception handler rethrows an X, which is not a Z. The main’s exception handler doesn’t type match and the program crashes.

throw obj; doesn’t behave as we like because it changes the type being thrown to the type caught.

Could write more handlers, and order from most derived to least derived…

what if i dont want to write catches for every type

To rethrow the exact same thing, use throw;. Can’t be used outside of a handler.

memory leak

main received and deleted array1

ret* gets created with new, but is never returned to main…. so no one is able to delete this ptr.

If a function has resources (memory, network sockets, file pointers….) and an exception is throwing during its execution, how can you guaranteed that that those resources are freed?

To solve this: catch exception, do cleanup, rethrow

try{
	foo(i);
} catch (BadBehaviour &obj{
	delete p;
}

But you don’t want to write duplicate try-catches. Code duplication is :

How can we guarantee that cleanup code is always executed at the end of our function regardless of how it terminates (exception, return)?

attempt 1: catch-all with ... syntax

void foo() {
	//allocation
	try{ code }
	catch(...) { free rsc, rethrow? }
}

Downsides:

attempt 2: destructor will always run

Use objects to wrap around, such that no matter how the function exits, stack unwinding happens and resources are destructed.

Note that stack allocated data is always freed. As well, the destructor of any stack allocated object will run. Hence, make sure that all that needs to be cleaned up is in stack allocated destructors.

For example, consider:

int* getArray(int begin, int end){
	int* array = new int[end - begin];
	int i = begin;
	while (i != end){
		array[i - begin] = i;
		//throw exception here, if mem leak array ptr is lost
		++i;
	}
	return err;
}

The array might memory leak, which results in dangling ptrs. So, wrap arrays in a stack allocated object that manages them, such that the destructor frees them, and this is no longer a problem.

Actually, wrap all resources in a stack allocated object that manages them. == resource acquisition is initialization

RAII (resource acquisition is initialization)

Any time you acquire a resource (ex: memory, file pointer, network socket… ) it is only by initializing some stack allocated object which manages it.

To encapsulate the previous dynamically allocated array example:

vector<int> getArray(int begin, int end){
	vector<int> array;
	while (begin != end){
		array.emplace_back(begin);
		++begin;
	}
	return array;
}

which happens to be an existing wrapper to array: std::vector.

exception safety

In case new fails, it throws an exception.

Going back the the assignment operator of the node class

Node& Node::operator=(const Node& other){
	if (this == &other) return *this;
	delete next;
	next = new Node{*other.next};
	data = other.data;
	return *this;
}

the invariant of Node:

The next ptr is one of 2 things:

  1. nullptr
  2. a valid ptr to a heap allocated node

But here, if new fails, then our old next is still deleted and we are left with a dangling ptr.

Even if the client caught the dangling ptr exception, the LinkedList is irreparable.

exception safety tiers

Levels of exception guarantee

  1. nothing
  2. basic guarantee
  3. strong guarantee
  4. no-throw guarantee

nothing

Program may be in an invalid state i.e. Node::operator=.

basic guarantee

If a function offers the basic guarantee, it promises that if it throws or propagates an exception, then the program will be left in a valid but unspecified state

Definition: valid means that no resource leaks, no invariants are violated.

strong guarantee

If a function throws or propagates an exception following the strong guarantee, the program state will be left as if nothing occurred, as if this function was never called.

i.e. vector.emplace_back(), program state leaves as if emplace_back() was never called.

  1. if array is full, allocate bigger array (double it)
  2. copy all elements over
  3. emplace back
  4. free the old array

We don’t care about the old array values, so it makes more sense to move the elements of the old array into the new realloc-ed array. But what happens if the move constructor throws in the middle??

A moved-from object is no longer valid, and will leave the old array in a invalid state. emplace_back offers the strong guarantee, but using move will violate the strong guarantee. Hence, emplace_back will use the copy constructor to keep the old array intact while creating the new array, unless the move constructor is declared as noexcept. !!!

no-throw guarantee

This function will always complete its task and never throw an exception. (Relates beyond the design of the function itself)

Tell the compiler of the no-throw guarantee with the keyword noexcept.

class Node{
	Node& operator=(Node &&other) noexcept{
		swap(next, other.next); //assign ptrs (numbers)
		swap(data, other.data); //assign plain ol data ints
		return *this;
	}
}

Note:

Hence operator= is noexcept

Should declare any possible function which doesn’t throw as noexcept, facilitates compiler optimization.

Example:

What guarantee does bar() offer???


class A {
public:
	void foo(); //strong guarantee
	void baz(); //strong guarantee
	void bar(){
		foo();
		baz();
	}
}

aka, is exception guarantee transitive??? nope

Note that neither foo() nor baz() are const function:

Hence at best, it offers the basic guarantee.

How can bar() offer the strong guarantee? i.e. kind of like undo the mess of foo().

But undo-ing is impossible, violates the nature of wrapping things up in function because otherwise bar() would need to know exactly what foo() does such that it can undo foo().

We can rewrite the function as such:


class A {
public:
	void foo();//strong guarantee
	void baz(); //strong guarantee
	void bar(){
		B temp{b};
		temp.foo();
		temp.baz();
		swap(temp, b);
	}
}

But what if swap throws? Still the same problem

A non-throwing swap for user-defined classes is at the heart of writing exception safe code in c++

How to write a non-throwing swap??? We can swap() nothrow but we still need to copy especially if it’s not a POD (i.e. use object’s copy ctor) … and copy might throw.

What’s a copy that will never throw? Any plain-ol-data or pointer!

This leads to the pImple idiom.

pointer to implementation idiom (pImpl)

Idea:

class XWindow{
	Display *d;
	Window *w;
	int gc, gx;
}

Do we know what all these fields mean? Do we care??? No, we don’t care about the implementation of the fields: it’s an abstraction resulting in an interface.

If the creators of Xwindow class decide to change the layout of the class or the underlying implementation, lead to compilation dependencies: changes imply that all client code that uses XWindow object is recompiled.

The pImpl idiom solves this:

struct XWindowImpl{
	Display *d;
	Window *w;
	int gc, gx;
}

implemented in the header.

And class XWindow just needs to store the XWindow implementation XWindowImpl.

class XWindow{
	XWindowImpl *pImpl;
}

There is no recompilation need of all code that uses XWindow, we just need to recompile XWindow.cc itself, and relink to the client code using XWindow.

Small change to client code: All field accesses to XWindow need now to be prefixed pImpl->: example w to pImpl->w

benefits:

= The added level of abstraction maintains the separation between the implementation and the client usage

reasons to not do this:

aka you don’t pay for what you don’t use

instances of pImpl usage

But what about individual heap allocated data (not an array)?

Foo *genFoo(){
	Foo *ret = new Foo();
	if (...) return;
	} else {}
}

This does not follow RAII, because if anything throws, we have a memory leak!!

If you follow RAII strictly, you will never see the keyword new. We could write a class that manages Foo* for us. But c++ has classes for wrapping parents already! std::unique_ptr<T>, std::shared_ptr<T> are included in #include <memory>.

#include <memory>
using namespace std;

unique_ptr<Foo> genFoo() {
	ret{ new Foo() };
} //unique_ptr<Foo> 

Better:

auto ret = make_unique<Foo>( /*ctor args*/ );

If any of this throws, unique_ptr

unique_ptr assumes sole ownership of the memory that it points to. As such,

what not to do:

int *p = new int;
unique_ptr u_p{p};

{
	unique_ptr p2{p};
}

Note that p2 does out of scope, deletes p; u_p is now a dangling ptr aaaaaa.

BUT shared_ptr! can be copied, because it is shared, and will only delete its data when the last shared_ptr to that data dies.

shared_ptr maintains a ref count of the shared_ptrs to that data.

Is when a shared_ptr is created, it allocates a size_t ptr and sets that number to 1. It is the only shared_ptr to that data.

When you copy construct a shared_ptr, when that size_t ptr is shallow copied so that share the same count. The size_t is incremented

~shared_ptr decrements the ref count, checks if its 0 after decrementing, if it is calls delete on the ref count and the data ?????????

{
	shared_ptr<int> sp = make_shared<int>{s};
	{
		shared_ptr<int> sp2{sp};
		//ref count is 1
	}
	//ded but still 1
}
//ded for reals

smart ptrs

next design pattern : decorator pattern

We want to have an object hierarchy where at runtime we can mutate the behavior of the relevant functions provided by that hierarchy

i.e. adding or removing functionality at runtime

pizza problem

We want to create a pizza ordering system where the user can add things to the pizza, changing the price and description.

class Pizza {
public:
	virtual float price() = 0;
	virtual string desc() = 0;
	virtual ~pizza(){};
}
class CrustAndSauce : public Pizza(){
public:
	float price() override { return 5.40; }
	string desc() override { return "Pizza" }
}

Composition or aggregation?? Potential client code:

Pizza *p = new CrustAndSauce{};
p = new Topping{"Ham", p};
p = new Topping{"Pizza", p};
p = new FreeExtra{"Well Done", p};

How to delete??

//option 1

//

option 2 is valid if you really don;t want your object owning your decorator

We’ll go with option 1 (owns-a decorator, filled in diamond)

This is a design decision.

This is Abstract

class Decorator : public Pizza{
protected:
	Pizza *base; //so that toppings can access it
public:
	~Decorator() { delete base; }
	Decorator(Pizza *p);
}
class Topping : public Decorator{
	string topping;
public: 
	Topping(string t, Pizza *p): Decorator{p}, topping{t}{};
	float price() override {
		return 1.49 + Decorator::price();
	}
	string desc() override {
		return base->desc() + "with " + topping;
	}
}

If we dont want Pizza *base protected, then we would just override it in decorator (which makes it non abstract anymore)

Instead of calling base::price we call

If you inherit pure virtual functions but don’t declare them as abstract.

class FreeExtra: public Decorator{
	string extra;
public: 
	string desc(){
		return extra + base->desc();
	}
}

Now the client code is:

int main(){
	Pizza *p = new FreeExtra{"A well done", 
				 new Topping{"basil", 
				   new Topping{"pineapple", 
				     new Topping{"ham", 
				       new StuffedCrust{new CrustAndSauce}}}}};
	cout << p->desc() << endl;
}

This is like a stack, but a stack has to manually do the concatenation.

The output would be: A well done pizza with stuffed crust with ham with pineapple with basil. The outermost is printed last because of the recursive call.

Since this is an owning (has-a) relationship, all memory is deleted.

Good thing about the decorator pattern is that you can: myPizza[0] = new Topping{"cheese"}; to add new toppings even after the creation of the pizza.

The creation is essentially a linked list of objects: stuffed crust -> pepperono -> crust and sauce

The removal of the pepperono results in: stuffed crust -> crust and sauce.

the strategy pattern

Suppose you have some task you want to achieve but the different classes achieve it differently i.e. different level of difficulty cpu players for chess require different implementations.

Basically the idea is literally virtual methods (i.e. makeMove) and have all the derived classes override it which their specific behaviour. polymorphism.

What if we want to make sure that at the beginning of each makeMove, the cpu’s regardless of difficulty should check if there is a checkmake in one (if there is a move to immediately win), then the cpu should take it.

Want to enforce some general behaviour that they all should follow. This implementation does not allow that.

class cpuPlayer{
public: 
	virtual void makeMove() = 0;
	virtual ~cpuPlayer();
}

We could copy and past the check for checkmate into every override method. BUT is error prone, tedious, bad.

non virtual interface idiom (nvi)

A virtual method is a “hook” for our derived classes to inject specialized behaviour.

A public method is part of the interface to the client.

A public virtual is both (a hook for the derived as part of the client interface).

The NVI idiom states that:

This is an idiom that in most cases, you have no reason to not follow:

In order for our base class ???

The base class cannot have virtual public methods ???

The abstract base class has no control over what ?????

Rewrite as such:

class cpuPlayer{
	virtual void doMove() = 0;
public: 
	void makeMove() { doMove(); }
	virtual ~cpuPlayer();
}

Where the concrete base class is:

class easyCPU : public cpuPlayer{
	void doMove(){
		... //code for easy strategy
	}
public: 
	void makeMove() { doMove(); }
	virtual ~cpuPlayer();
}

Yes! private methods can be virtual and derived classes can override them

class mediumCPU : public cpuPlayer{
	void doMove(){
		... //code for medium strategy
	}
public: 
	void makeMove() { doMove(); }
	virtual ~cpuPlayer();
}

If we want to enforce some behaviour that always occurs regardless of which derived type the object is, we can place it in the non-virtual makeMove function.

i.e.:

class cpuPlayer{
	virtual void doMove() = 0;
public: 
	void makeMove() { 
		checkMateInOne();
		doMove(); 
	}
	virtual ~cpuPlayer();
}

What if we were creating a video game. In this game we have easy and harder levels () and we have 2 types of enemies: turtles and bullets.

the policy/strategy we want to follow to create levels is different per level:

Create a virtual method createEnemy();

Factory method pattern is just strategy pattern to a policy of object creation.

templates??? (post midterm)

(edit: yes, templates)

vector<Foo> v;

We’ve already seen classes in the stl, like vector and smart pointers, where the type itself is parameterized when declaring an object.

When declaring an object of that type, you must provide another type inside the < >.

What’s actually going on here??

back to the iterator pattern

An iterator is any type for which !=, unary* and operator ++ are provided.

A class that implements the iterator pattern provides begin and end that return iteratos.

void for_each(iter start, iter end, fn f){
	while (start != end){
		*start = f(*start);
		++start;
	}
}

Well how can we do this?? Currently what if we wanted to run this function on our iterators for our LinkedList example from class and our ConnectX iterator from assignments.

We’d have to write 2 functions…

void for_each(LinkedList::iterator start, LinkedList::iterator end, int (*fn) (int));
void for_each(ConnectX::iterator start, ConnectX::iterator end, int (*fn) (int));

… we’d have to write different functions for each type of container, even though the inside implementation is basically the same.

We could try creating an Abstract Iterator type, which defines the interface of iterator types (albeit not well, because now every thing that is an iterator must inherit from it).

Also, that still doesn’t solve the problem of these functions having different types.

Sometimes an interface is insufficient. An ABC is really just defining an interface, and that isn’t sufficient enough: a raw pointer is an iterator by definition (has !=, *, ++).

But a pointer is a POD, it can’t inherit from an interface. What do we really want to say for our types that our functions consume????

Writing a function over our AbstractIterator is insufficient to operate over all iterators.

What we really mean about the types this function takes is: any type for which !=, *, ++ are defined.

the answer to this problem^ is templates

To write a template function, you start with the template keyword.

template <typename T>
T max(const T& lhs, const T& rhs){
	return lhs > rhs? lhs : rhs;
}

template <typename T> says we have ONE template we’ll refer to as T in our function, T will essentially get replaced with whatever type the client parameterizes with.

For which types can max me used on?

Any type that has:

The requirements of a template type are only exactly what’s enforced on it, by how that template type is used. Templates use duck typing i.e. if it walks like a duck and talks like a duck then it is a duck ah yes

A note on using template functions: if then compiler can unambiguously deduce the type then you don’t need to parameterize that function.

example:

int x = 10; 
int y = 0;
max(x,y); //valid

example:

template <typename Iter, typename Fn>

void for_each (Iter& start, Iter& end, Fn f){
	while (start != end){
		*start = f(*start);
		++start;
	}
}

types allowed: @Iter

@Fn

exists in the STL???

Note that we had templated them like this: max<int>(5,4); parameterizing the function with type int.

However, template functions do not have to be manually or explicitly parameterized.

implicit parameterization

The type of the template argument can be unambiguously deducible, hence you wouldn’t need to explicitly parameterize it.

i.e. max(5,4); automatically parameterized

So, template functions are incredibly useful when the abstraction that you want to work over is not a specific type, but rather a set of behaviour.

templating classes

Classes can be templated too. Consider a LinkedLst, if stores only integers as its data. If we wanted it to store something else, we’d have to copy and paste all of LinkedList and only change the type of data everywhere.

template <typename T>
class LinkedList {
	struct Node {
		T data;
		Node* node;
	}

	Node* head;
public:
	void addToFront(T data){
		head = new Node(data, head);
	}

	class iterator {
		Node* curr;
		iterator (Node* c) : curr{c} {}
		friend class LinkedList<T>;
		/* ... */

		//LinkedList is an incomplete type, must specify which type to template it with. 
		//The only change is the return type of the dereference unary * operation
		T& operator*() {return curr->data; }
	}
}

Now we can create LinkedLists over any type of data that matches the way we use it, as long as T is copy constructable.

Client code usage:

LinkedList<string> ls;
ls.addToFront("hi").addToFront("aloha");
// aloha -> hi

If we’ve defined the Big5, then we have a copy ctor, which means that we can have linkedlists of linkedlists!

LinkedList<float> lf;
LinkedList<LinkedList<LinkedList<int>>> lololi;

Sidenote: LinkedList of LinkedList of LinkedList… tokenizing >>> is very hard. Ambiguous grammar, still broken. i.e. templating with int.

Now LinkedList is a considerably more powerful and useful class, and we didn’t have to write any new code.

behind the scenes behaviour

How does this actually work??

The first time that the compiler sees you parameterize a template function or class with a type that you haven’t used yet, it creates a whole new function or class of that type.

Consider this example:

LinkedList<string> ls;
LinkedList<float> lf;
LinkedList<LinkedList<LinkedList<int>>> lololi;

Compiler will create 5 LinkedList class during compile time:

This is why the implementation has to be provided in the header file. (can be written further down, but still in the header file).

If the implementation of LinkedList is in the .cc file, the compiler can’t check if the types are valid, nor can’t generate the different functions/classes for the different types.

Hence, become of this, template method/functions must be defined (not just declared) in the header file, otherwise the compiler couldn’t create that new type of class/function when it sees a new type.

side note: can compile main with '-c'

Another example: simple implementation of shared_ptr

We’re not going to write make_shared(), but still going to consider the big 5.

template <typename T>
class shared_ptr{
	T* data;
	size_t count;
}

destructor

Let’s first consider our destructor.

We want sharing between different objects. Don’t use static because that’s sharing between the entire class. Use pointers.

shared_ptr::~shared_ptr(){
	--(*count);
	if (*count == 0){ // !(*count)
		delete data;
		delete count;
	}
}

constructor

shared_ptr::shared_ptr(T* p): data{p},count{new size_t{1}} { }

Note that making two shared pointer from the same raw pointer, both will think that they are the first and only one, and thus, when you kill one shared pointer, you lose your raw pointer because it will delete itself.

copy constructor

We are becoming a copy of another share pointer.

shared_ptr::shared_ptr(const T* other): data{other.data}, count{ &(++(*other.count)) } { }

which is basically:

shared_ptr::shared_ptr(const T* other): data{other.data}, count{ other.count } {
	++(*count); 
}

If the user doesn’t make another shared pointer to the same piece of data without using a shared_ptr copy constructor, then there is nothing we can do about it. (I guess we could implement a giant map of the pointer addresses)

move constructor

Can’t set count to a nullptr because when it goes out of scope. Hence, you could just increment count as a solution. Which is the same as the copy constructor

So hence, don’t write it at all.

//tada just use the copy constructor

copy assignment operator

shared_ptr& shared_ptr::operator=(const shared_ptr<T>& other){
	--(*count); 
	if (*count == 0){ // !(*count)
		delete data;
		delete count;
	}
	data = other.data;
	count = other.count;
	++(*count); 
}

move assignment operator

Same as copy assignment operator intuitively.

== big 3 instead of big 5

variadic templates

templated max function is nice, but what if we want the max of an arbitrary list of items? instead of between 2 elements only.

Make variadic templates using a “parameter pack”.

template <template T, typename... Rest>

T my_max(T first, Rest... rest){
	T maxRest = my_max(rest...);
	return first > maxRest ? first : maxRest; //needs base case still
}

We need a base case, actually as a separate function

template <template T>

T my_max(T t){
	return t;
}

Note that this variadic max function casts types:

i.e.

my_max(12.5, 13.0, -1, 213.5); //returns 213

Equivalent to:

float my_max(12.5, 13.0, -1, 213.5);

float my_max(13.0, -1, 213.5);

int my_max(-1, 213.5);

int my_max(213);

Whereas:

my_max(12.5, 13.0, -1.0, 213.5); //returns 213.5

template meta programming

Every time the compiler sees an instantiation of a template it hasn’t seen before, it creates a new class or function with that instantiation.

Template, other than types, can also take integer values.

you can combine these two pieces of information to compile things at compile time.

This is called template, meta programming.

very little reason to use this in c++, maybe in hardware drivers……..

template <long long N>
struct Fib< ???? > 

How can we store a number in a clasS?? static fields

template <long long N>
struct Fib{
	const static long long val = Fib<N-1>::val + Fib<N-2>::val;
}

That’s our recursive call. How do we make the base case?? Template specialization!

template<>
struct Fib<1> {
	const static long long val = 1;
}

And for the n-2 recursive call:

template<>
struct Fib<0> {
	const static long long val = 1;
}

This is different from getting the val from a function. What is the Fib calculation O() ??

This is actually memoized by the compiler.

When printed out, it’s constant time! But the integers for Fib<?> have to be there on compile time, must be integer constants.

Compile time is going to be linear tho

How to tell the client what the implementation do, and how to use it

signature about syntactic requirements

specification about the modules behaviour

interface specification

contract between the module’s provider and the client programmer, that document each other’s expectations.

benefits of modularity

hook

Precondition: constraints that hold before the method is called

//requires

Postcondition: constraints that hold after the method is called, assuming that the precondition holds.

//modifies
//throws
//ensures
//returns

ex1

sumVector, use prefix increment.

//requires that vect is validly constructed (redundant, should be implicitly true) 
//requires the content of vect are such that addition in order will not overflow 
(are sufficiently small that their value should not cause sumVector to overflow)

//returns sum of vector

ex2 : replace

int replace(std::vector<int>& vect, int oldElem, int newElem){
	for (int i = 0, i < vect.size(), ++i){
		if (vect[i] == oldElem){
			vect[i] == newElem;
			return i;
		}
	}
}

replace an element in vector, return position of new element

//requires: oldElem to actually be in vector
//modifies: vect
//ensures: let i be the index of oldElem in vect such that there doens't exist q in Natural numbers or q less than i, and vector[q] = oldElm. Then, vect[i] will be set to newElem
//returns: i, as above

ex3 : isSubstring

Pre/post descriptions should be short and straight to the point

//returns: true iff there exists a (possibly empty) string A and B such that A word B = text

specifying derivations

derived classes inherit not only interface signatures

Makes sense to foc all the fields in the derived classes

CheapAccount : public Account virtual void bill()

//Bill()
//modifies: this->balance, this->minutes
//ensures: 
minutes = 0; 
balance = balance@pree + fee + rate*(max(minutes - freeminutes, 0))

#derived classes

ensures is required for derived classes, but other fies

##interface specification

what are the conforming implementations

returns: (exists j: vec[j] == val) ? j : vec.size()

returns: (exists j: vec[j] == val) ? j : -(j < 0 or j > vec.size())

returns: (exists i: vec[i] == val) ? smallest i : -1

impl1 : a

int find (const vector<int> &vec, int val){
	for (int i - 0;; i++){
		if (vec[i]==val) return i;
	}
}

impl2 : a, b, not c (doens’t return size) , d,

int find (const vector<int> &vec, int val){
	for (int i = 0;; i++){
		if (vec[i]==val) return i;
	}
	return -1;
}

impl3: a, c, d, not e

int find (const vector<int> &vec, int val){
	for (int i = vec.size() -1; i >= 0; i++){
		if (vec[i]==val) return i;
	}
	return vec.size()
}

how precise to specify ??

= acceptable solutions

specificand set acceptable solutions

comparing specifications

A is weaker (less restrictive)

Require B Requires A

A’s postconditions are equal or stronger than B’s postconditions

Require B (Ensures A and Requires A) (ensures B and returns B)

Checking preconditions

The client needs to uphold these

Which is okay, because these requirements are part of the interface

Best practice: have some checks of the preconditions if it’s constant time, throw assertion failure or exception if not satisfied

oop design principles

Characteristics, properties and advice for making decisions that improve the modularity of the design

OOP Basics

OO Principles

oop design principles: coupling and cohesion

coupling

Coupling is the degree to which two modules are interconnected (have to know about each other)

high coupling:

mid-ish coupling

low coupling

We desire low coupling, because otherwise changes to one module are more likely to cause mandatory changes in another.

cohesion

to what degree is an individual module (header + implementation) specifically focused on a goal

high cohesion

mid-ish cohesion

low cohesion

We want high cohesion, strictly because it makes modules more manageable. i.e. knowing where to look to make a change, or to find a bug

oop design principles: open closed principle

principle: a module should be open for extension but closed for modification

AKA prgram to an interface, define and give it to the clients, and the clients can extend

Follow NVI

LSP

maintain no more,

weaken no les

pre pre pre_based && post_derived post_base

void stack::push(int n) {
	vec.emplace_back(n); 
}
void bounded_stack::push(int n){
	if (vec.size() >= cap) throw stackFull {}
	vec.emplace_back(n);
}

Rob’s nitpick on word:

parameters:

arguments:

Is ChequingAccount (with a credit limit) substitutable for Account?

No, mainbalance can be greater than these two

We want to make account more general

Encapsulation of Components

Information Hiding: Modular design should hide design and implementation details, including information about components.

All the logic that relates to one component, be wrapped in that component (not in base class)

If you can’t g

If you give them protected setters,

and the setters have code to maintain invariants

and follow NVI, such that all our virtual functions should also be non-public

ClientCodeLeft

t->addTermRecord("Spring2018")
t->computeTermGPA("Spring2018")
t->printTermRecord("Spring2018")

ClientCodeRight (bad)

Transcript *t;
TermRecord *tr;
...
tr = t->getTermRecord("Spring2018");
tr->computeGPA();
tr->print();

in general, we dont like to return pointers to our fields client s

void Store::settlebill(float total) {
Customer->getPayPal()->getCreditCard()->charge(total);
//we give clietn a settle bill method

But still non-ideal, because paypal should know its methods

we shouldn’t

the component interface should do all the work

which leads us to the Law of Demeter

law of demeter

“Law” tests encapsulation: an object “talks only to its neighbours”

if m2 returned an f m1 can talk to b,c and d and m2 should talk to c and d

aka:

But:

example, is this substitutable??

For every min over 200 a month, it’s an extra $1. BasicAccount::call() creates a record of a cellphone call, recording the start date and start time of the call and the duration in minutes. BasicAccount:bill() decrements the account’s balance by the monthly service fee ($100). BasicAccount::pay() increments the balance by the amount paid.

CheapAccount::call() creates a record of a cellphone call, and updates the number of minutes (numMinutes) of calls in the current month. CheapAccount:bill() decrements the account’s balance by the $30 monthly service fee and by $1 for each minute of calls beyond the free 200 minutes of calls in the current month; it also resets numMinutes to 0 to start recording number of call minutes for the next month.

Are the signatures matching?? (i.e. types) yes

Are derived methods promising less?? or requiring more??? no, they both promise that the account are charged the correct amount

to be:

line 21: issue, it’s calling the output operator for item->startDate, item->endDate

Just overload the output operator for a callRecord(), for line21-22 to be std::cout << *obj << endl; instead of the client manually printing the fields.

double dispatch (visitor pattern)

problem statement:

we want a function that runs depending on the type of 2 objectS:

i.e. you’re creating a video game:

So we want something : virtual void attack(Weapon &w, Enemy &e);

But we can only place the virtual function in one class. If we put it in weapon, the actual function dispatches based on Weapon, but not Enemy.

Vice versa if we put it in Enemy.

solution:

Combine overloads and overrides to achieve the desired behaviour

class Enemy {
public:
	virtual void beStruckBy(Weapon &w) = 0;
}
class Turtle: public Enemy {
public:
	void beStruckBy(Weapon &w) override {w.strike(*this);}
}

class Bullet: public Enemy {
public:
	void beStruckBy(Weapon &w) override {w.strike(*this);}
}

Note that they are different: *this is i.e. a Turtle reference, specifically not a Bullet reference.

class Weapon { 
public: 
	virtual void strike(Turtle& t) = 0;
	virtual void strike(Bullet& b) = 0;
}
class Stick : public Weapon { 
public: 
	void strike(Turtle& t){ 
		/*code to strike TURTLE with Stick*/ 
	}
	void strike(Bullet& b){ 
		/*code to strike BULLET with Stick*/ 
	}
}

//Rock is the same as Stick
class Rock : public Weapon { ... }

Client usage:

Enemy &e = ...;
Weapon &w = ...;
e.beStruckBy(w);

Steps:

  1. Appropriate beStruckBy() is called based on the actual type of enemy (virtual dispatch from e)
  2. beStruckBy() calls w.strike(*this) which virtual dispatch calls the appropriate strike() method, based on the overload.
  3. Virtual dispatch means the correct strike based on weapon type gets called.

visitor pattern’s flaw

The visitor, which in this case is the Weapon classes, is HIGHLy coupled to the Enemy class.

If we want to add new types of enemies, we need more strike methods for the new enemies.

We agree that it should be highly coupled

Add functionality in a class for the whole hierarchy without ..???? breaking the single responsibility rule

class AbstractBook { 
	string title, author;
	int numPages;
public: 
	virtual void accept(BankVisitor&) = 0; //beStruckBy() equiv
}
class Comic: public AbstractBook { 
public: 
	void accept(BankVisitor&v) override {
		v.visit(*this);
	}
}

//similarly for Text and Comic
class BookVisitor {
public: 
	virtual void visit(Text& t) = 0; //strike()
	virtual void visit(NormalBook& b) = 0; //strike()
	virtual void visit(Comic& c) = 0; //strike()
}

we want a catalogue that keeps track of how many Books we have for each :

#include <unordered_map>
#include <map>

using namespace std;

class Catalogue : public BookVisitor { 
	unordered_map<string, int> theCatalogue;
public: 
	void visit(Comic& c)override {
		++theCatalogue[c.getHero()];
	}
	void visit(Text& t)override {
		++theCatalogue[t.getTopic()];
	}
	void visit(NormalBook& b)override {
		++theCatalogue[b.getAuthor()];
	}
}

Note that the index operator [] used on stl::map will return the value if it exists, otherwise it will add that key and default init the value (default construct if its an object, or zero our the bits if its a POD)

virtual NormalBook& AbstractBook::operator=(NormalBook&);

Sometimes you need a value to be treated like another type, or more commonly, treated like the type it actually is. To achieve this we use casts.

In general casts should be avoided (because they are often indicative of bad design). If you must cast, you should use the c++ cast, NOT the c-style cast.

//c_style casts
int* p ... 
void* v = (void*) p;
book* b = (book*) v;
// aka can cast anything

//c++ casts
//doesn't let you cast everything

c++ cast comes in 4 varieties:

static_cast:

for sensitive casts with well-defined behaviour

float x = 4.5f;
int y = static_cast<int>(x);

Also casts from base class pointers to derived pointers. Dangerous, you’re telling the compiler to trust your cast, that pointer actually points to the object that I say it does.

Comic c ...;
AbstractBook *pb = &c;
static_cast<Comic*>(pb); 

Rip partial assignment and more.

reinterpret_cast

Student *s = new Student("Harry");
Turtle *t = reinterpret_cast<Turtle*>(s); //is undefined behaviour
Weapon *w = new Stick;
w->strike(*t); //error

const_cast

for casting away const behaviour, should NOT be used to modify const objects. Should only use when you know casting it still won’t modify the value.

i.e. working with a library that you don’t own, a function takes in a non_const parameter, but you know it doesn’t modify the const promise.

// not your code but you know it doesn't modify the Foo
void doSomething(Foo *p);

// client code (your code):
const Foo *p;
doSomething(*p); 	    		  //Error, doesn't work
doSomething(const_cast<Foo*>(p)); //ah yes

dynamic_cast

is for casting pointers of references that are to a base class, down to a derived class pointer or reference

Attempts the cast, if the object the pointer points at is not actually of that derived class (the type you’re trying to cast to), then it returns the nullptr instead.

This following code is valid:

void WhatIsIt(AbstractBook *pb){
	if (dynamic_cast<Comic*>(pb)){ //nullptr returns false
		cout << "tis a comic" << endl;
	}
	if (dynamic_cast<Text*>(pb)){ //nullptr returns false
		cout << "tis a textbook" << endl;
	}
	if (dynamic_cast<Comic*>(pb)){ //nullptr returns false
		cout << "tis a comic" << endl;
	}
	// this is not polymorphism
	// this code is HIGHLY coupled to the book hierarchy, and 
	// defeats the purpose of having a hierarchy
}

But, what if a cast is a reference? and what if it fails

i.e.

NormalBook b{ ... };
AbstractBook &r = b;
Comic &c = dynamic_cast<Comic&>(r); //obviously fails

It throws an exception, of std::bad_cast (perhaps).

With dynamic cast, we could finally (if we wanted to) provide a polymorphic assignment operator, but I still suggest you disallow the client fro assignment through base class ptrs.

class AbstractBook { 
	string title, author;
	int numpages;
	public:
	virtual AbstractBook& operator=(const AbstractBook& b){
		title = b.title;
		author = b.author;
		numpages = b.numpages;
	}	
}

//this is how you would do it, if you need assignment between different

class Comic: public AbstractBook{
	string hero;
public: 
	Comic& operator=(const AbstractBook& b){
		Comic &other = dynamic_cast<Comic&>(b);
		//throws if not actually a comic (mixed assignment)
		Book operator=(b);
		hero = Other.hero;
		return *this;
	}
}

Dynamic cast only works if the compiler can figure out what the actual type of an object is. (i.e. virtual dispatch, gotta figure out what the object is)

Dynamic cast only works on types that have at least one virtual function (and hence a vtable).

how are virtual functions implemented by the compiler??

How do virtual functions really work?

struct A {
	virtual void hello() { cout << "im an A" << endl; }
};

struct B {
	void hello() { cout << "im an B" << endl; }
	//overwritten A's hello()
};

int main(){
	A* ap;
	char c;
	cin >> c;
	if (c < 'c') ap = new A;
	else  ap = new B;
	ap->hello(); //what does this program print?
}

Note that if the user inputs a char that is less than ‘c’ in the ascii table, then it prints, im an A. Otherwise, it prints “im a B”, (if ignoring the fact that a read will fail and own garbage).

How does the compiler achieve this??

Recall that a function call is just pushing appropriate data onto the stack and then jalr (jump and link, changes the program counter to another place, store the location so that we can return when we pop the stack frame).

This works fine for non-virtual methods or standalone methods.

If A::hello was non-virtual, then at the line ap->hello(), the compiler goes to the definition of the function and knows exactly where to go. So since hello() is virtual, how does the compiler know where to jump on ap->hello()??

Can’t be based on input, because compilation happens before the program is run, so the decision of which method to call is made at the step of creating the object ap.

Well luckily, of course at the point of object creation, the compiler knows what type of object it is creating. While at ap->hello() where it has no idea what ap actually points at.

So the compiler at the point of object creation leaves itself a trail of breadcrumbs. What it does is store a pointer as the first sizeof(ptr) (system dependent, but 8) bytes of each object (from a class with virtual methods)*

* the standard doesn’t specify how virtual methods must behave: the implementation is up to the compiler. But virtually all compilers implement it this way.

The pointer it stores is called the virtual function table pointer, which is a pointer that points to a table of function pointers to the implementations of the virtual methods of that class.

Note that each class wit virtual methods has one table. Each object of the same type thus shares the same table/has the exact same pointer.

struct A { 
	int x;
	virtual void hello() {...}
	virtual void boo() { ... } 
}

struct B { 
	int y;
	virtual void hello() {...}
	virtual void boo() { ... } 
}

Client code:

A a;
B b;

So now, when the compiler sees ap->hello(), it knows where to jal. It’ll access the table via the pointer stored in the first bytes of the object, and then read the offset in the table to find out the offset for the desired function, and jal to that location.

i.e.

Undefined behaviour:

A a1;
A a2;
B b;

int **pa1 = reinterpret_cast<int**>(&a1) 
//dereferencing *pa1 gives you the pointer to an int, which is the first 8 bytes of the a object, which is the pointer to the virtual function vtable
int **pa2 = reinterpret_cast<int**>(&a2) 

cout << *pa1 << endl;
cout << *pa2 << endl;
// instances of same object share the same pointer to vtable
//same print

//manually call A.hello() and B.hello(), using information stolen from vtable. 
//g++ looks for the *this pointer, breaks. but clang++ compiles the next two lines
reinterpret_cast<void(*)()>(**pa1)()  
//cast it as a function pointer, of return type void with no parameters, and call that function
//im an a

reinterpret_cast<void(*)()>(**pb1)()  
//cast it as a function pointer, of return type void with no parameters, and call that function
 //im a b


//overwrite the first 8 bytes of 
//which assigns A's vtable to B's vtable

*pa1 = *pa2

reinterpret_cast<A*>(pa1)->hello() //should print im a B, because of virtual dispatch
//but compiler cache knows that it's an A, doesn't do 

a1.hello()
//im an A

(&a1)->hello()
//im a B
//changed the identity of the a1 object

multiple inheritance

In OOP, it is often the case that our classes may support a variety of interfaces

For example, consider you’re making a video game and you want an interface that specifies which objects are “drawable”.

class Drawable {
	Renderer &r;
public:
	void draw(int x, int y) = 0;

};

now every entity that is drawable will inherit from Drawable.

class Controllable {
	Renderer &r;
public:
	void draw(int x, int y) = 0;

};

This situation of multiple inheritance is an issue.

Does this receive two A? yes. It’s a compilation error.

i.e.

D obj;
obj.x; //what am i referring to here??

This is ambiguous. Class D has two x because it has two A objects effectively, one inherited from B and one from C.

We can specify which one you want:

obj.B::x = 5;
obj.C::x = 10;

cout << obj.B::x; //prints 5, x are distinct variables

This is called the deadly diamond problem, and also known as the diamond of death problem, or the deadly diamond of death problem.

C++ solves this problem with virtual inheritance

virtual inheritance

class A {
public:
	int x;
}

class b : public virtual A {

}


class C : public virtual A {

}


class D : public B, public C {

}

But this makes our result very strange.

The first result is that it fixes our problem.

i.e.

D obj;
obj.x; //no longer a problem because D has only one X

How does the compiler achieve this?

Before multiple inheritance, if you looked at the beginning address of an object, it looked like any of its ancestors:

Uses sizeof() to cover the object (oldest grandparent … all the way to youngest child)

Then, for multiple inheritance:

For multiple virtual inheritance, the metadata stored in object layout has multiple vtables to tell you offsets, then this can look like any of these objects.

Consider we want to find the A fields of athis object, while it is pointed at by a B pointer. What are the possibilities?

The distance to the A fields through a B ptr is not knowable at compile time, just as its not knowable at compile time whih irual method to call.

Use vptr to jump to other objects’ vptr, which uses that information to