CS 246 - Object-Oriented Software Development
TTH 1:00PM - 2:20PM
MC 2065
Adrian Reetz

TTH 11:30AM - 12:50PM 
MC 4045
Brad Lushman

40 asg | 20 mid | 40 final

1 | Basic C++

1.1 | I/O stream

cin and cout use the bitwise shift operator

This is an example of overloading (same function or operator has multiple implementation and the compiler chooses at compile time)

21 >> 3 // evaluates to 2 (10101 -> 10)

cin overrides values

int a = 1
cin >> a; // input: 2
cout << a; // output: 2

cin returns a bool

#include <iostream>
using namespace std;
 
int main (void){ // entry point
	int a;
	while (true) {
		cin >> a;
		if (cin.fail()) break; // or if(!cin)
		cout << i << endl;
	}	
	return 0;
}

What does the operator >> do?

inputs: cin (istream), placeholder for data (several possible types)
output: produces cin (istream)
This is why we can write cin >> x >> y >> z;

Example 3.0

int main (){
	int i;
	while (true){
		if (!(cin >> i)) break;
		cout << i << endl;
	}
}

Example 4.0

int main (){
	int i;
	while (cin >> i){
		cout << i << endl;
	}
}

Ex: Read all ints and echo on stdout until EOF. Skip non-integer output.

int main (){
	int i;
	while (true){
		if (!(cin >> i)){
			if (cin.eof()) break; // done - EOF
			else {
				cin.clear() // you MUST reset the stream's failure flags
				cin.ignore() // remove the offending character from input stream
			}
		}
		else {
			cout << i << endl;
		}
	}
}

I/O Manipulators (hex, dec, oct)

Note that manipulators set flags in the standard stream
These are effectively global variables, meaning they affect the whole program
Good practice: change stream settings back when you’re done (cout.flags())

cout << 95; // prints 95
cout << hex << 95 // prints 5f

1.2 | Strings

In C, strings are arrays of chars (char * or char[]) terminated by '\0'
- You have to allocate memory by overwriting '\0'
In C++, you can import <string>
- These grow as needed and are safer to manipulate
  - string s = "Hello" creates a C-style string

String Operations

Equality / Inequality: s1 == s2, s1 != s2
Comparison: s1 <= s2
Length: s.length() (runs in $O (1)$ unlike strlen which is $O (n)$ )
Individual characters: s[0]
Concatenation: s3 = s1 + s2

int main (){
	string s;
	cin >> s; // stops at whitespace
	cout << s;
}

What if we want whitespace?

getline(cin, s)

Strings are an abstraction:

They wrap an interface of getting and putting items around the keyboard and screen
Would this be useful anywhere else? Files

1.3 | File Access

Files:

Read/write from/to a file instead of stdin/stdout
std::ifstream for reading
std::ofstream for writing

File access in C:

#include <stdio.h>
int main(){
	char s[256] // hoping no word is longer than 255 chars
	FILE *f = fopen("file,txt", "r");
	while (1){
		fscanf(f, "%255s", r)
		if (feof(f)) break;
		printf("&s\n");
	}
	fclose(f);
}

File access in C++

Using same mechanism as cin/cout

#import <iostream>
#import <fstream>
#import <string>
using namespace std;
int main (){
	// Declaring and initializing the ifstream variable `f` opens the file
	// This is a heap-allocated variable
	ifstream f{"fle.txt};
	string s;
	while (f >> s){
		cout << s << endl;
	}
	// File is closed when the ifstream variable goes out of scope
}

Strings: Anything that can be done with cin/cout can be done with if/ofstream

Extract data from chars in a sting: std:istringstream
Send data from a string as chars: std:ostringstream
These can be imported with import <sstream>;
Imagine these as “stuffing things into a sock and then cutting open the sock”

string intToString (int n){
	ostringstream oss; // string that writes to a string
	oss << n;
	return oss.str(); // extract the string
}
	```
 
Ex: convert a string to a number
```cpp
int n;
while (true){
	cout << "Enter a number " << end;;
	string s;
	cin >> s;
	if (istringstream iss{s}; iss >> n) break;
	cout << "I said, ";	
}
cout << "You entered" << n << endl;

Ex: echo all the numbers, skip all non-numbers

int main(){
	string sl
	while (cin >> s){
		int n;
		if (istringstream iss {s}; iss >> n){
			cout << n << endl;
		}
	}
}

Application: Processing the command line To accept command line args in C or C++, always give main the following params:

argc is the number of the command line arguments, always >=1 because it includes the program name
argv is an array of C-style strings
- argv[0] = program name
- argv[1] = 1st argument
- argv[c] = NULL

int main (int argc, charc *argv[]){
}

Ex: ./myprogram abc 123

argc = 3
argv[0] -> ./myprogram\0
argv[1] -> abc\0
argv[2] -> 123\0 Note: the args come in as C-style strings. We’re recommended to convert to a C++ string before processing

int main (int argc, char *argv[3]){
	for (int i=1; i<argc; ++i){ // 1-indexed to ignore program name
		string arg = argv[1]
	}
}

Ex: print the sum of all numeric args on the command line:

int main (int argc, char *argv[]){
	int sum = 0;
	for (int i=1; i<sum, ++i){
		string arg = argv[i]
		int n;
		if (istringstream iss{arg}; ss > n){
			sum += n;
		}
	}
	cout << sum << endl;
}

1.4 | Default Function Arguments

void printWordsInFile(string name = "file.txt"){
	ifstream file {name};
	for (string s; file s>>s;){
		cout << s << endl;
	}
}
printWordsInFile("othername.txt"); // reads from othername
printWordsInFile(); // raeds from file.txt

Notes

Optional params must be last
The missing arg is supplied by the caller, not the function

Why?

The caller passes params by pushing them on the stack
The function fetches params by reading them off the stack from where they are expected to be
If an arg is missing, the function has no way of knowing that, and would instead take whatever is in that part of the stack
So instead, the caller must supply the extra arg if it’s missing:
- printWordsInFile() gets replaced with
- printWordsInFile(file.txt)
Thus, default arguments are part of a function’s interface, and not implementation
So defaults go into the interface file, not the implementation file

1.5 | Overloading

In C, you would write

int negInt (int n){ return -n }
bool negBool(bool b){ return !b }

In C++, you don’t need to!

The correct version of neg for each function call is chosen by the compiler (at compile time) based on the number and types of arguments
In the call, overloads must differ in the number or types of arguments - just differing in the return type is not good enough (we’ve seen this with >>, <<. +)

1.6 | Structs / Constants

Structs

// wrong version
struct Node{
	int data;
	struct Node *next
}; // don't forget the ;
 
// right version
struct Node{
	int data;
	Node next;
};

Constants

Declare as many thingsconst as you can - it helps catch errors

const int passingGrade = 50; // must be initialized

NULL used to just be 0

Node n{5, nullptr}; // do not say NULL or 0
const Node n2 = n; // immutable copy of N

1.7 | Parameter Passing

void inc (int n) { ++n; }
 
int x = 5;
inc (x);
cout << x; // 5 becuase pass by-value

Pass-by-value:

inc receives a copy of x, mutates the copy
Original unchanged
Solution: - If a function needs to mutate an arg, pass a pointer

void inc (int *n) { ++*n } // x's address is pased by value

Q: Why cin >> xand not cin >> &x? A: C++ has another ptr-like type references

References - Important!

int y = 10;
int &z = y; 
// Z is an lvalue reference to int like a pointer
// similar to int *const z = &y
 
z = 12; // NOT *z = 12, now y = 12 - z is like an alias for y
int *p = &z; // gives the address of y

How can we tell when & means “reference” or “address of”?

Whenever & occurs as part of a type (eg. int &z), it always means reference
When & appears in an expression, it means “address of” (or bitwise-and)

Things you CAN’T DO with future references

Leave them uninitialized (egint &x;), must be initialized to something that has an address (an lvalue)

// Leave them unitialized
int &x = 3
int &x = y+z
int &x = y; // good
 
// Create a ptr to a reference
int &*x; 
int *&x = y // good
 
// Create a reference to a reference
int &&r - y
 
// Create an array of refs
int &r[3] = {1,2,3};

What can you do?

Pass as function params

void inc(int &n){ ++n; }
int x = 5;
inc (x);
cout << x;

Why does cin >> x work? Takes x as a reference

istream &operator >> (istream &in, int &n)

Why is the stream being taken and returned as a reference?

To save the copying!

What does return by reference mean?

Pass-by-value, eg int f(int n) copies the argument
- If the arg is big, the copy is expensive
- Pass-by-value can save time

struct ReallyBig{ ... }
int f (ReallyBig rb) { ... } // copy - slow
int g (ReallyBig &rb) { ... } // alias - fast, but can change rb
int h (const ReallyBig &rb) { ... } // fast no copy, but param can't be changed

But what if a function does want to change rb locally, but doesn’t want those changes visible to the caller? Then, the function must make a copy of rb

int k (const ReallyBig &rb){
	ReallyBig rb2 = rb
	// mutate rb2
}

If you need to make a copy anyway, it’s better to just use pass-by-value and have the compiler make it for you

You should be passing by const ref for any argument larger than a pointer
Unless the function needs to make a copy anyway - in that case, then use past by value

Recall:

past-by-const-ref is better for anything larger than a pointer
otherwise pass-by-value is better because the function will make a call anyway

int f(int &n){}
int g(const int &n){}
 
f(5); // error because can't initialize an lvalue ref to a literal value (5)
g(5); // legal, since n can never be changed
// 5 is stored in a temporary location (on the stack) so it has an address
 
istream fopreator >> (istream &in, int &n);
// the istream is being passed and returned as a reference to save copying
// This is important because stream vars are not allowe dto be coped

1.8 | Dynamic Memory Allocation

Don’t do this:

int *p = malloc( _* sizeof(int));
free (p)

Do this instead: new/delete - type-aware, less error-prone

struct Node {}
Node *p = new Node;
...
delete p;

all local vars reside on the stack
vars deallocated when they go out of scope (stack is pooped)
allocated memory resides on the heap
remains allocated until delete is called
if you don’t delete all allocated memory, that’s a memory leak
- bad things will happen

Array:

Node *nodeArray = ndew Node[10];
...
delete [] nodeArray

Memory allocated with new must be freed with delete
Memory allocated with new _ [_] must be freed with delete[]
Mixing these is undefined behaviour (UB)

Returning by value / ptr / ref

Node getMeANode() { // "expensive" - n is copied to caller's stack frame on return
	Node n;
	return n;
}
// return a ptr (or ref) instead?
 
Node *getMeANode(){ // returns a ptr to stack allocated data (popped on return)
	Node n;
	return &n; // BAD BAD BAD BAD BAD
}
Node &getMeANode(){ // also bad
	Node n;
	retrun nn
}

Why is it okay for the operator >> to return an istream&?

Because the reference is not a to a local variable
The returned ref is the same ref that was passed as “in”, so it refers to something accessible by the caller
Just return by value!

Node *getMeANode(){ // ok - returns a ptr to heap data
	return new Node; // but don't forget to delete it when done
}

1.9 | Operator Overloading

Give meanings to C++ operators for types we create

struct Vec {
	int x,y;
}
Vec operator+(const Vec &v1, const Vec &v2){
	Vec v = {v1.x+v2.x, v1.y+v2.y};
	return v;
}
Vec operator*(const int k, const Vec &v){
	return {k*v.x, k*v.y};
}
Vec operator*(const Vec &v, const int k){
	return k*v;
}

Special case: overloading >>, <<

struct Grade{
	int theGrade;
}
 
ostream&operator << (ostream &out, const Grade &g){
	out << g.theGrade << '%';
	return out;
}
 
istream &operator >> (istream &in, Grade &g){
	in >> g.theGrade;
	if (g.theGrade < 0) g.theGrade = 0;
	if (g.theGrade > 100) g.theGrade = 100;
	return in;
}

1.10 | Separate Compilation

Split programs into modules, which each provide

interface: type defs, headers for functions
implementation: full definition, headers for functions

Declaration vs Definition

Declaration: asserts existence
Definition: full details, allocates spaces

int x; // definition
extern int x; //definition

// vec.cc | interface
export module vec;
export struct Vec {
	int x,y;
}
export Vec operator+(const Vec &v1, const Vec &v2);
 
// main.cc 
import vec;
int main (){
	vec v{1,2};
	v = v+v;
	...
}

Implementation (vec-impl.cc)

module vec // this file is part of module vec, implicitly imports file interface
 
vec operator+(const Vec &v1, const Vec &v2){
		return {v1.x + v2.x, v1.y+v2.y};
}

Interface files start with export module _;
Implementation files start with module _;
Compiling separately: g++ -c _.cc (c stands for compile only, do not link / build executable)
- Creates an object file (.o)

Compiling modules (MUST BE IN DEPENDENCY ORDER)

Interface must be compiled before implementation, client

g++20 -c vec.cc
g++20 -c vec-impl.cc
g++20 -c main.cc
g++20 vec.0 vec impl-o main-o -o exec
./exec

2 | Object Oriented Programming

2.1 | Classes

We can put functions inside of structs!

// student.cc
export struct Student {
	int assns,s mt, final;
	float grade();
};
 
// student-impl.cc
float Student::grade(){
	return assns*0.4 + mt*0.2 + final*0.4
}
 
// client.cc
Student s{60,70,80};
cout << s.grade() << endl;

Parts of a class:

class is essentially a struct that can contain functions
- C++ has a class keyword - later
object - an instance of a class: student = class, s = object

student s {60,70,80}

Function grade - called a member function (or method)
:: called the scope resolution operator
- C::f means f in the context of class C
- :: is like . where the LHS is a class (or namespace), not an object (like std::)

What do assns, mt, final mean inside of student::grade?

They are fields of the receiver object - the object upon which ‘grade’ was called
s.grade() is a method call - it uses the fields of s

Methods take a hidden extra param this, which is a pointer to the object on which the method was called

s.grade() // this == &s
struct Student {
	...
	// do this in a serparate file
	float grade(){
		return this->assns*0.4 + this->mt*0.2 + this->final*0.4
	}
};

Initializing Objects

Student s{60,70,80}; // ok, but limited
 
// Better: write a method that initializes a constructor
struct Student {
	int assns, mt, final;
	float grade();
	Student(int assns, int mt, int final);
}
 
Student::Student (int assns, int mt, int final){
	this->assns = assns;
	this->mt = mt;
	this->final = final;
}
Student s{70,80,90}; // better

If a constructor has been defined, 70,80,90 are passed as args to the constructor
If no constructor has been defined, C-style field by field initialization is only available if you haven’t written a constructor

Alternative syntax:

Student s = Student {70,80,90};

Looks like the creation of an anonymous student object which is then copied to initialize s
But it’s not semantically identical to Student s{70,80,90};

Heap allocation:

Student *p = new Student{70,80.90};

Advantages of constructors: they’re functions

Can write arbitrarily complex initialization code
Default params, overloading, sanity checks (eg. ensure grade is between 0 and 100)

struct Student {
	Student (int assns=0, int mt=9, int final=0){ // default
		this->assns = assns;
		...
	}
};
Student s2 {70,80};; // 70,80,90
Student newkd; // 0,0,0

When an object is created, a constructor is always called

Even if you didn’t write one, every class comes with a default (zero-arg) constructor
vec v; the default constructor does nothing!

What if you didn’t write one?

Every class comes with a default (i.e. 0-arg) ctor (which just default-constructs all fields that are objects)
e.g. Vec v; // default ctor - does nothing in this case
But the provided default ctor goes away if you write any ctor

struct Vec {
	int x, y;
	Vec(int x, int y) {
		this->x = -x;
		this->y = -y;
	}
};
 
Vec v; // error
Vec v{1, 2}; // OK
 
struct Basis {
	Vec v1, v2;
};
 
Basis b; // won't compile because the default ctor for Basis would default-construct v1, v2, but Vec has no default ctor, so the default ctor for Basis can't exist

Could we write our own default ctor?

struct Basis { // STILL doesn't work - too late. the body of the ctor can contain arbitrary code, so the fields of the class are expected to be constructed and ready to go before the ctor body runs
	vec v1, v2;
	Basis() {
		v1 = Vec{1, 0};
		v2 = Vec{0, 1};
	}
}

2.2 | Object Creation and MIL

When an object is created, 3 steps:

Space is allocated
Fields are constructed in declaration order (i.e. constructors run for fields that are objects)
Ctor body runs

Initialization of v1, v2 must happen in step 2, not step 3. How can we accomplish this?

Member Initialization List (MIL) Step 2:

Student::Student(int assns, int mt, int final):
	assns{assns}, mt{mt}, final{final} // step 2, field names outside braces, params inside braces
	{} // step 3

Note: Can initialize any field this way, not just object fields

struct Basis {
	Vec v1, v2;
	Basis(const Vec &v1, const Vec &v2): v1{v1}, v2{v2} {} // something to think about: what ctor of Vec is being called here?
}

Default values for the MIL:

struct Basis {
	Vec v1{1, 0}, v2{0, 1}; // if the MIL does not mention a field, these values will be used
	Basis() {} // uses defaults above
	Basis(const Vec &v1, const Vec &v2): v1{v1}, v2{v2} {}
}

Note: Fields are initialized in the order in which they are declared in the class, even if the MIL orders them differently

MIL sometimes more efficient than setting fields in the body

Consider:

struct Student {
	int assns, mt, final; // not objects
	string name; // object
	Student (int assns, ..., string name) { // name is default-constructed to the empty string in step 2 then reassigned in step 3
		this->assns = assns;
		...
		this->name = name;
	}
	
	Student (int assns, ..., string name): // name is initialized correctly in step 2 - no extra step, more efficient
		assns{assns}, ..., name{name} {}
};

MIL must be used for:

Fields that are objs with no default ctor
Fields that are const
Fields that are references (basically just constant pointers)

MIL should be used as much as possible.

Recall once again:

Basis::Basis (const Vec &v1, const Vec &v2): v1{v2}, v2{v2} {} // what ctor is used for v1, v2?

Consider also:

Student s{60, 70, 80};
Student s2 = s;

How does this initialization happen?

The copy ctor: for constructing one object as a copy of another

Note: Every class comes with

default ctor: default-constructs all fields that are objs; lost if you write any ctor
copy ctor: copies all the fields
copy assignment operator
destructor
move constructor
move assignment operator

Building your own copy ctor:

struct Student {
	int assns, mt, final;
	...
	Student(const Student &other): assns{other.assns}, mt{other.mt}, final{other.final} {}
}; // equivalent to built-in

When is the built-in copy ctor not correct? Consider:

struct Node {
	int data;
	Node* next;
};
 
Node* n = new Node{1, newNode{2, newNode{3, nullptr}}}'
Node m = *n;
Node* p = new Node{*n};

Simple copy of fields - only the first node is actually copied (shallow copy)

If you want a deep copy (copies the whole list), write a copy ctor

struct Node {
	...
	Node(const Node &other): data{other.data},
		next{other.next ? new Node{*other.next} : nullptr} {} // new Node{*other.next} recursively copies the rest of the list
};

The copy ctor is called:

When an obj is initialized from another obj of the same type
When an obj is passed by value
When an obj is returned by value … for now. The truth is more nuanced, as we will see.

2.3 | Single-Argument Constructors (explicit)

Note: Careful with constructors that can take one argument

struct Node {
	Node (int data, Node *next=nullptr):data{data}, next{next}{}
};
// Single-argument constructors create implicit conversions

Node n{4} // ok
Node n = 4 // also ok, implicit conversion from int to Node

Same thing as

string s = "Hello"
// C style string | const char x

What’s the problem?

void f(Node n):
f(4) // works becuase 4 is implicitly converted to Node

Danger: accidentally passing an into to a function and expecting a node

Solent conversion
No error from the compiler
Potential error not caught

Don’t do things that limit your compiler’s ability to help you. Disable the implicit conversion by marking the constructor explicit

struct Node{
	explicit Node (int data, Node *next=nullptr)
}
 
Node n{4} // yes
Node n=4; // no
f(4); // no
f(Node{4}); // yes

2.4 | Destructors

When an object is destroyed, a method called the destructor runs

Stack allocated: goes out of scope
Heap allocated: is deleted

Classes come with a destructor, which gets called for all object fields

When an object is deleted

Dtor body runs
Field dtors invoked in reverse declaration order (for object fields)
Space deallocated

When do we need to write a dtor?

Node *np = new Node {1, new Node {2, new Node {3, nullptr}};

If np goes out of scope, the ptr is reclaimed (stack-allocated), and the nodes are leaked
IF we say delete *p;, it calls *np destructor which does nothing

Write a dtor to ensure the whole list is freed

struct Node{
	...
	~Node(){ delete next; } // recursively deletes the whole list
	// this is safe because deleting a nullptr (the last node) IS SAFE
}

2.5 | Copy Assignment Operator

Student s1 {60,70,80}
Student s2 = s1 // copy ctor
Student s3; // default ctor
s3 = s1 // copy, but not construction
// copy assignment operator - uses the compiler-supplied default

May need to write our own

// WRONG AND DANGEROUS
struct Node {
	...
	Node &operator (const Node &other){
		data = other.data
		delete next;
		next = other.next ? nwe Node {*other.next}: nullptr;
		return *this;
	}
}
 
// WHY?
Node n{1, new Node {2, new Node {3, nullptr}}};
n = n; // deltes n then tries to copy n to n
 
// good version
struct Node {
	...
	Node &operator (const Node &other){
		if (this == &other) return *this; // if same, no need to delete
		data = other.data
		delete next;
		next = other.next ? new Node {*other, next}: nullptr;
		return *this;
	}
}

How likely are you to write n=n?

Not likely, but what if you wrote *p = *q and they both pointed to the same location?
Or `a[i] = a[j], i = j’

An even better implementation

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

Altrenative: copy and swap idiom

import <utility>
using namespace std;
struct Node {
	...
	void Swap (Node &other){
		swap(data, other.data);
		swap(next, other.next);
	}
}
 
Node &operator = (const Node &other){
	Node tmp = other;
	swap (tmp);
	return * this;
}

rvalues and rvalue references

an lvalue is anything with an address
- an lvalue ref (&) is like a const ptr with auto-deref and it alsways initialized to an lvalue

Node odsOrEvens(){
	Node odds{1, new Node{3, new Node {5, nullptr}}};
	Node evens{2, new Node {4, new Node {6, nullptr}}};
	char c;
	cin >> c;
	if (c == '0) return evens;
	return odds
}
 
Node n = oddsOrEvens(); // copy construction

”other” here is a reference to:

The temporary object created by the constructor to hold the result of oddsOrEvens
The copy constructor deep-copies data from the temporary into n
BUT the temporary is just going to be discarded anyway, as soon as the statement Node n = oddsOrEevns(); is done
It’s wasteful to have copy data from the temp: why not just steal it again and save the cost of a copy?
We need to be able tot ell whether other is a reference to a temporary object (where stealing would work), or a standalone object (where we would have to copy)

Rvalue References: Node&& is a reference to a temporary object (rvalue) of type Node

struct Node {
	...
	Ndoe (Node &&other) // called a move ctor
	data {other.data}; // steals other's data
	next {other.next}{
		other.next = nullptr;
	}
}
Node n = oddsOrEvens(); // move ctor
Node n = m; // copy ctor
 
// alternatively
Node m;
m = oddsOrEvens; // assignment from temporary

Move assignment operator (take my stuff before you get pushed off a cliff):

struct node{
	...
	Node &operator(Node &&other) { // steal other's data
		swap (data, other.data); // Destroy my old data
		swap (next, other.next); // swap without copy
		return *this; // temp will be destroyed and take old data with it
	}
}

If you don’t define a move cotor / move assignment operator, the copying versions of these operations will be used instead.

2.6 | Copy/Move Elision

Elide = to leave something out

vec makeAVec(){
	return Vec {0,0}; // invokes basic Vec ctor	
}
Vec v = makeAVec(); // what runs? copy or move ctor?

Answer:

It’s just the base ctor, not the copy or move ctor
In certain cases, the compiler is required to skip calling copy/move ctors.
In this example, makeAVec writes its result (Vec {0,0}) directly into the space occupied by v in the caller, rather than copy it later

void doSomething (Vec v); // pass by value, copy/move construction
 
doSomething (makeAVec()); // result of makeAVec written drectly into param
// no copy / move

This happens, even if dropping the ctor calls would change the behaviour of your program (eg. if ctors print something)

You are not expected to know exactly when elision happens - just that it does happen

Summary: Rule of 5 / Big 5

If you need to write any one of these, then you usually need to write all 5

Copy ctor
Copy assignment operator
Dtor
Move ctor (steal)
Move assignment operator

What characterizes classes that need the big 5? (some don’t need any)

Ownership = If it’s the class’s job to manage resources (memory, files, windows, network connections)
- (eg. nodes manage the node behind them)

2.7 | Operator Overload

Notice: operator= is a member function

Previous operators we’ve written have been standalone function
When an operator is declared as a member function, *this plays the role as the first operator

struct Vec {
	int x,y;
	...
	Vec operator+(const Vec &other){
		return {x+other.x, y+other.y};
	}
	Vec operator* (const int k){
		return {x*k, y*k}; // ONLY IMPLEMENTS V*K
	}
	// How would we implement k*v?
	// Must be a standalone function, not a member function
	Vec operator*(const int k, const Vec &v){
		return v*k;
	}	
}

Overloading I/O operators:

struct Vec {
	...
	ostream &operator<< (ostream &out){
		return out << x << ' ' << y;
	}
}

What’s wrong with this? Makes Vec the first operand, not the second Use as v << cout, which is confusing w << (v << cout)

So define >>, << as standalone. These operators must be members:

operator=
operator[]
operator->
operator()
operator T (where T is a type)

2.8 | Arrays of Objects

struct Vec{
	int x,y;
	Vec (int x, int y): x{x}, y{y}{}
};
 
// These want to call the default ctor on each item
// If no default ctor, they cant initialize array items: ERROR
Vec *vp = new Vec[10];
Vec moreVecs[5];

Options

Provide a default ctor
1. Bad idea unless it makes sense for the class to have one
For stack arrays:

Vec moreVecs[3] = {{0,0},{1,1},{2,2}};

For heap arrays: create an array of ptrs

Vec **vp = New vec*[5];
vp[0] = new Vec{0,0};
vp[1] = new Vec{1,1};
...
for (int i=0; i<5; i++) delete vp[i];
delete[] vp;

2.9 | Const Objects

Const objects arise often, especially as params

int f (const Node &n);

Can we call methods on a const object?

Issue: This may modify fields and violate const
We can call methods that promise not to modify the fields

struct Student{
	int assns, mt, final;
	float grade() const; // does not modify fields
}

Compiler checks that const methods, don’t modify fields
You can’t call non-const methods on a const objects
But you can call const objects on a non-const object

Consider: we want to collect usage stats on Student objs

Struct Student{
	int numMethodCalls = 0;
	float grade() const{
		++numMethodCalls;
		return ...
	}
	// but this breaks our const promise!
}

Now we can’t call grade on const students - it can’t be a const method
But mutating numMethodCalls affects only the physical const-ness of student objects, not the logical const-ness
- Physical const-ness: Whether the actual bits that make up the objects have change
- Legal const-ness: Whether the object should eb regarded as different for the update

Mutable fields

Mutable fields can be change, even if the object is const.
Use mutable fields to indicate that a field does not contribute to the logical const-ness of the object

2.10 | Static Fields and Methods

What if we want statistics about our program (eg. how many Students are created)?

Static members (fields/methods): associated with the class itself, not with any specific instance (object)

struct Student{
	...
	inline static int numInstances=0;
	Student (...):...{
		++numInstances;
	}
}

Static member functions don’t depend on the specific instance (this param), but can only access static fields of other static member funcitons

struct Student {
	...
	static void howMany(){
		cout << numInstances << endl;
	}
}
// calling
Student s1{_,_,_}, s2{_,_,_};
Student::howMany(); // 2

2.11 | Invariants & Encapsulation

struct Node{
	int data;
	Node *next;
	...
	~Node(){delete next;}
}
 
Node n1 {1, new Node, {2, nullptr}};
Node n2 {3, nullptr};
Node n3 {4, &n2};

What happens when these go out of scope?

n1 - dtor runs, entire list is deleted. OK
n2, n3’s dtor tries to delete n2, but n2 is on the stack, not the heap! UB

Invariants

Class Node relies on an assumption for its proper behaviour that next is either nullptr, or was allocated by new
This assumption is an example of an invariant - statement that must hold true and doesn’t vary - on which Node relies
But we can’t guarantee this invariant, because we can’t trust the user to use Node property

Eg: Stack

Invariant because the last item pushed is the first item popped
But not if the client can rearrange the underlying data
Hard to reason about programs if you can’t trust invariants

To enforce invariants, we introduce encapsulation (has all 5 vowels in it)

We want to treat objects as black boxes (capsules)
Creates an abstraction - seal away the implementation so you can only interact via provided methods

struct Vec{
	Vec(int x, int y); // default visibility is public
private: 
	int x,y; // private
public: 
	Vec operator+ (const Vec &other); // public
};

In general: we want private fields, only methods should be public Better to have default visibility = private Switch from struct to class

class Vec{
	int x,y;
	public:
		Vec(int x, int y),
		Vec operator+(const Vec &other);
	...
};

Difference between struct in class is default visibility

Public in struct, private in class

Let’s fix our linked list class:

// list.cc
export class List {
	struct Node; // private nested class, only accessible in class List
	Node *theList = nullptr;
	public:
	void addtoFront (int n);
	int &ith (int i);
}
 
// list-impl.cc
struct List::Node{
	int data;
	Node *next;
	...
}
~Node(){ delete next; }
 
void List:addToFront(int n){
	theList = new Node{n, theList};
}
int List::ith(int i){
	Node *cur = theList;
	for (int n=0; n<i; ++n) cur = cur->next;
	return cur->data;
}

Only List can create / manipulate Node objects, thus, we guarantee the invariant that next is nullptr or allocated by new

2.12 | Iterator Pattern (auto)

But now we can’t traverse the list form node to node as we would a linked list Repeatedly calling ith to access the whole list is $O (n^{2})$ time. But we can’t expose the nodes or we lose encapsulation

SE Topic: Design Patterns Certain programming challenge arise often - keep track of good solutions to these problems - reuse and adapt

Solution: Iterator Problem

Create a class that manages access to nodes
Abstraction of a pointer - walk the list without exposing the actual pointers

for (int *p=arr; p!=arr+size; ++p) printf("%d ", *p);
 
class List{
	struct Node;
	Node *theList;
	public:
		...
		class Iterator{
			Node *p*
		public:
			ITerator(Node *p):p{p}{}
		}
	// let's try writing this manually
	Iterator &operator++(){ p=p->next; return *this; }
	int &opreator *() { return p->data; }
	bool operator!=(const Iterator &other) { return p!=other.p; }
	
	Iterator begin(){ return Iterator{theList}; }
	Iterator end(){ return Iterator{nullptr}; }
	...
};
 
// Client
int main(){
	List l;
	l.addToFront(1);
	l.addToFront(2);
	l.addToFront(3);
	// everything in the loop is O(1), runs in O(n)
	for (List::Iterator it=l.begin(); it!=l.end(); ++it){
		cout << *it << " ";
	}
	// same thing as:
	for (auto it=l.begin(); it!=l.end(); ++it){
		cout << *it << " ";
	}
	// auto x = y;  give's x y's type
}

Fun fact about auto:

Making new keywords is super hard because what if 1/1m people use it as a variable? breaks their code
Exists in C and means “automatic storage duration” or “stack allocated”
It’s the opposite of “static” - auto int x means x on the stack
Saying auto is the same as saying nothing!

Shorter-cut: range-based for loop:

for (auto n:l){
	cout << n << " ";
}

Available for any class with:

Methods begin, end that produce iterators
The iterator must support !=, unary*, prefix++ (like the ones we implemented)!

2.13 | Encapsulation Continued

List client can create iterators directroy:

auto it = List::Iterator{nullptr};

Violates encapsulation - client should be calling begin/end

We could make iterators ctor private

Then client can’t call List::Iterator{...};
But then neither can List

Solution give List privileged access to Iterator

Make it a friend!

class List{
	public:
		class Iterator{
			Node **p;
			Iterator (Node *p);
			public:
				...
				friend class List; // list has accesss to all members of Iterator
		};
	...
};

Advice: you don’t want a lot of friends, it weakens encapsulation

You only want to make friends with people that can do something for you

Getting access to private fields - accessor / mutator methods

class Vec{
	int x,y;
	public:
		...
		int getX() const{return x;} // accessor
		void setY(int z;) {y = z;} // mutator
}

2.14 | Comparing Objects

Recall string comparison in C

strcmp(s1, s2);

Returns the lexicographical comparison

<0 if s1 < s2
0 if s1 = s2
0 if s1 > s3

Compare to string comparison in C++:

s1 < s2; s1 == s2; s1 > s2;

One drawback:

string s1 = ..., s2 = ...;
if (s1 < s2) ... // compare s1, s2 (linear scan)
else if (s1 == s2) ... // linear scan again
else ...

In C, we would just need

int n = strcmp(s1, s2); // one linear scan

Can we achieve the same thing with C++ strings (one comparison)?

Introducing the three-way (lol) comparison operator (spaceship <=>)

import <compare>
string s1 = ..., s2 = ...;
std::strong_ordering result = s1 <=> s2; // <0 if less, =0 if equal, >0 if greater

How can we add <=> to our classes?

struct Vec{
	int x,y;
	auto opertator<=> (const Vec &other)const {
		auto n = x<=>other.x;
		return (n==0) ? (y<=>other.y): n; // if equal cmp y, otherwise cmp x
	}
}

Now we can say Vec v1 {1,2}, v2{1,3};

v1 <=> v2;

We can also say v1 <= v2, etc because the compiler rewrites <, <=, >=, > in terms of <=>

v1 <= v2 // is rewritten as (v1<=>v2 <= 0)

Sometimes you can get <=> for free:

struct Vec{
	int x,y;
	auto opetator <=> (const Vec &other) const = default;
	// this does lexicographical ordering on the fields of vec
};

When might the provided behaviour be incorrect?

struct Node{
	int data; // lex order would compare ptr values - useless
	Node *next
	
	auto operator<=>(const Node &other) const{
		auto n = data<=> other.data;
		if (n != 0) return n;
		if (!next && !other.next) reutrn; // equal length
		if (!next) return std::strong-ordering::less; // shorter
		if (!other.next) reutrn std::strong-ordering::greater; // longer
		return *next <=> *other.next
	} // assumes non empty lists
};

2.15 | Equality Revisited

Suppose we want to add a length() method to the list. How? Options

Iterate and count nodes $(O (n))$
Store length as a field of list and keep it up to date. $O (1)$ with negligible additional cost to update

How shall we write == on lists?

((l1 <=> l2) == 0); // O(n), n is the length of the shorter list

Shortcut: lists of different length cannot be equal, so comparing lengths could sometimes be $O (1)$

3 | Inheritance

3.1 | System Modelling

Visualize the structure of the system (abstractions and relationships among them) to aid design and implementation

Popular standard: UML (Unified Modelling Language)

Name	Vec
Fields (optional)	-x: Integer -y: Integer
Methods (optional)	+getX: Integer +getY: Integer
Visibility: private (-) or public (+)

3.2 | Relationship: composition of classes

class Basis{
	Vec v1, v2;
}

Embedding one object (eg. Vec) inside another (Basis) is called composition

A basis is composed of 2 Vecs. They are part of the basis and that is their only purpose
Relationship: a basis “owns” two Vecs

If A “owns a” B, then typically:

B has no identity outside of A (no independent existence)
If A is destroyed, then B is destroyed
If A is copied, then B is copied (deep copy)

Eg: A car owns its engine - the engine is part of the car

destroy the car → destroy the engine
copy the car → copy the engine

Implementation - usually as composition of classes

┌─────────────┐              ┌─────────────┐
│   Basis     │              │    Vec      │
├─────────────┤              ├─────────────┤
│ - v1: Vec   │◆────────────→│ - x: float  │
│ - v2: Vec   │   owns(2)    │ - y: float  │
└─────────────┘              │ - z: float  │
                             └─────────────┘

3.3 | Aggregation

Compare car parts in a car (“owns a”) vs car parts in a catalogue

The catalogue contains the parts, but the parts have an independent existence.
This “has a ” relationship is called aggregation

If A “has a” B, then typically

B exists apart from its association with A
If A is destroyed, B lives on
If A is copied, B is not (shallow copy)
- Copies of A share the same B

Ex: Ducks in a pond

class Pond {
		Duck *ducks[maxDucks];
};

┌─────────────────┐              ┌─────────────┐
│     Pond        │              │    Duck     │
├─────────────────┤              ├─────────────┤
│ - ducks: List   │◇────────────→│ - name: str │
│                 │   has (0..*) │ - weight    │
└─────────────────┘              └─────────────┘

Case Study: Does a pointer field always mean non-ownership?

No! A Node owns the Nodes that follow it, then list owns the first node
But these ownerships are implemented in pointers

┌─────────────────┐              ┌─────────────┐
│     List        │              │    Node     │
├─────────────────┤              ├─────────────┤
│ - head: Node    │◆────────────→│ - data      │
│ - size: int     │  owns (0..*) │ - next: Node│
└─────────────────┘              └─────────────┘

We could view the List object as owning all the nodes within it

Thus, List is taking responsibility for copying/creating/destroying Nodes rather than Node
Possible iterative (loop-based) management of pts vs recursive routines when Nodes managed other Nodes

3.4 | Specialization (Inheritance)

class Book{
	string title, author;
	int length; // # pages
  public:
	Book(...)
	...
};
 
class Test{
	string title, author;
	int length;
	string topic;
  public:
	Text(...);
	...
};

Comic Books:

Comic
-title: String
-author: String
-length: Integer
-hero: String
This is ok, but doesn’t capture relationships among Book, Text, Comic? And how do we create an array/list that contains a mixture of these?

Union

union BookTypes{Book *b; Text *t; Comic *c;}; // like a struct declaration
BookTypes myBooks[20];

Array of void* (void pointers point at any type)

Rather: Texts and comics are kind of Books (extra features). Use Inheritance

// base / super-class
class Book{
	string title, author;
	int length; // # pages
  public:
	Book(...)
	...
};
// derived / sub-classes which get the same fields
class Text:public Book{
	string topic;
  public:
	Text(...);
	...	
};
class Comic: public Book{
	string hero;
  public:
	Comic(...);
	...
};

Any method can be called on Book can be called on Text, comic. Who can see these members?

title, author, length are private in Book - outsiders can’t see them
subclasses like Text, Comic also can’t see them
How do we initialize Test? We need the members (title, author, length) to initialize them

class Text: public Book {
    ...
public:
    Text(string title, string author, int length, string topic) 
        : title{title}, author{author}, length{length}, topic{topic} {}
}

WRONG for 2 reasons:

title, etc. not accessible in Text (and even if they were, MIL only lets you mention your OWN fields)
Once again, when an object is created: the following happens

New steps for object creation

Space is allocated
Superclass part is constructed (NEW!)
Fields are constructed
Ctor body runs

So a ctor for Book must run before fields of Text can be initialized. If Book has no defualt ctor, a ctor for book must be invoked explicitly

class Text: public Book{
  public:
    Text(string title, string author, int length, string topic): 
	    Book {title, author, length}, topic{topic} {}
	// (step 2)                       (step 3)     (step 4)
}

Good reason to keep superclass fields private to subclasses

If you want to give subclasses access to superclass members, use protected visibility

class Book {
  protected: // accessible to Book and subclasses but nobody else
	string title, author;
	int length;
  public:
		...
};
 
class Text: public Book {
	string topic:
  public:
	...
	void addAuthor (string newAuthor){
		author += " "+newAuthor;
	}
	
}

Not a good idea to give subclasses unlimited access to fields.

Make the fields private, but provide protected accessors/mutators

class Book{
	string title, author;
	int length
  protected:
	void setAuthor(string newAuthor);
  public:
	Book(...);
	bool isHeavy() const;
}

Relationship among Test, Comic, Book is call “is a”

a Text is a Book
a Comic is a Book

         ┌─────────────┐
         │    Book     │
         └─────────────┘
                △
                │
        ┌───────┴───────┐
        │               │
┌───────┴─────┐   ┌─────┴───────┐
│    Text     │   │    Comic    │
└─────────────┘   └─────────────┘

When is a book heavy?

class Book{
	... // assume length is protected
  public:
	bool isHeavy() const { return length > 200;}
	...
}
 
Book b {"A small book," ..., 50}; // false
Comic c{"A big comic", ..., 40, ...}; // true
 
cout << b.isHeavy(); // false
<< c.isHeavy(); // true
 
Book b = Comic{"A big comic", ..., 40, ...};

b.isHeavy() causes Book::isHeavy, not Comic::isHeavy to run!

Book b: title, author, length Comic {...}: title, author, length, hero

Tries to fit a Comic object where there is only space for a book object

What happens? Comic is sliced - hero field is chopped off and it becomes a Book
Adding fields leads to slicing, even if the two object types were the same size

When accessing objects through pointers, slicing is unnecessary and doesn’t happen

Comic c {..., ..., 40, ...};
Book *pb = &c;
c.isHeavy(); // true
pb->isHeavy(); // false

…and still Book::isHeavy runs when we access pb->isHeavy()

Compiler uses the type of the ptr (or reference) to decide which isHeavy to run - does not consider the actual type of the object

Behaviour of the object depends on what type of ptr (or ref) you access it through

How can we make Comic act like a Comic, even when pointed to by a Book ptr, i.e. how can we get Comic::isHeavy to run?

Declare the method virtual

class Book {
	...
public:
	...
	virtual bool isHeavy() const { return length > 200; }
};
 
class Comic : public Book {
	...
public:
	bool isHeavy() const override { return length > 30; } // tells compiler you do indeed mean to override; raises error if isHeavy() doesn't exist in parent
};
 
Comic c{__, __, 40, __};
Comic *pc = &c;
Book *pb = &c;
Book &rb = c;
 
pc->isHeavy(); // true
pb->isHeavy(); // true
rb.isHeavy(); // true

Comic::isHeavy runs in each case.

Virtual methods: choose which class’ method to run, based on the actual type of the obj at runtime

e.g. my book collection:

Book *myBooks[20]; // good to make it an array of pointers but i didnt listen to why
...
for (int i = 0; i < 20; i++) {
	cout << myBooks[i]->isHeavy() << endl;
}

Accommodating multiple types under one abstraction: polymorphism (“many forms”)

Note: this is why a function void f(istream&) can be passed an ifstream - ifstream is a subclass of istream

DANGER: What if we had written Book myBooks[20]; and tried to use that polymorphically? Consider:

void f(Book books[]) {
	books[1] = Book{"book", "book author", __};
}
 
Comic c[2] = {{"comic 1", "author 1", 10, "hero 1"}, 
			{"comic 2", "a2", 20, "h2"}};
f(c); // legal - a Comic* is a Book*

What is c now?

{{"comic 1", "author 1", 10, "book"}, {"book author", ???}}; // UB

Never use arrays polymorphically! Use arrays of ptrs.

Punchline: destructor should generally be virtual

3.5 | Destructor Revisited

class X{
	int **;
  public:
	X(int n): x{ new int [n] }{}
	~X() { delete [] x; }
}
class Y: public X{
	int *y;
  public:
	Y(int n, int m): X{n}, y{ new int [m] }{}
	~Y() { delete [] y; }
}
X *myX = new Y{10,20};
delete myX; // leaks, becuase it calls ~X but not ~Y
// only x is freed, but not y

How can we ensure that deleting through a ptr to a subclass will call the subclass dtor?

Always make the dtor virtual in classes that are meant to be subclasses, even if the dtor doesn’t do anything

If a class is not meant to subclasses, declare it final

class Y final:public X{}

3.6 | Pure Virtual Methods and Abstract Classes

class Student{
	...
  public:
	virtual float fees() const;
}

2 types of students:

class Regular: public Student{
  public:
	float fees() const override;
};
 
class Coop: public Student{
  public:
	float fees() const override;
}

What should we put for Student::fees?

Not sure - every student should either be regular or co-op
Can explicitly give Student::fees no implementation

class Student{
	...
  public:
	virtual float fees() const = 0; 
	// method has no (*) impl, called a pure virtual method
}

A class with a pure virtual method cannot be instantiated

Student s; // does not compile
new Student; // does not compile

Called an abstract class - purpose is to organize subclasses

Their subclasses are also abstract classes unless them implement all virtual methods
Non-abstract classes are called concrete (Regular, Coop, List, Node)

UML: virtual/pure virt, methods - italics

Overriding a virtual method in a subclass - non-italics
Abstract classes - class name in italics

3.7 | Inheritance and Copy/Move

class Book{
  public:
	// defines copy/move ctor/assign
};
class Text:public Book{
	string topic
  public:
	// does not define big 5
};
Text t {"Algorithms", "CLRS", 500, "CS"};
Text t2 = t; // no copy ctor for Text - what happens?
// calls Book's copy ctor
// then goes field-by-field for the Text part
// same for other options

To write your own:

Text::Text(const Text &other): Book{other}, topic{other.topic}{}
Text &Text::operator=(const Text &other){
	Book::operator=(other);
	topic = other.topic;
	return *this;
}
Text::Text (Text &&other): Book {std::move(other)}, topic{other.topic}{}
// std::move is from <utility>

Note: even though other “points” at an rvalue, other itself is an lvalue (so is other.topic)

std::move(x) forces an lvalue x to be treated as an rvalue, so that the “move” versions of operations run

Text &Text::operator= (Text &&other){
	Book::operator= (std::move (other));
	topic = std::mvoe(other.topic);
	return *this;
}

Operations given above are equivalent to default

Text t1{}, t2{} // "pascal", "Stroustrup"
Book *pb1 = &t1, *pb2 = &pb2;

Partial assignment - copies only the Book part

Fix this by making operator= virtual

class Book{
	...
  public:
	virtual Book &operator=(const Book &other){ ... }
};
class Text:public Book{
	...
  public:
	Text &operator(const Book &other) override { ... } // not const Text
}

Note: Different return types, but param types must match or it’s not an override and won’t compile

Violates “is a”

Text t{...};
t = Book{...} // using Book to assign Text is BAD (but compiles)
t = Comic{...} // REALLY BAD (might be comic / text)

If operator= is

non-virtual, then there’s partial assignment through base class ptrs
virtual, then it allows mixed assignment

Recommendation: All superclasses should be abstract

class AbstractBook{
	string title, author;
	int length;
  protected:
	// prevents assignment through base class ptrs from compiling
	AbstractBook &operator=(constAbastractBook &other);
  public:
	AbstractBook(...);
	virtual ~AbstractBook()=0; // need at least one pure virtual method
	// if none, use the destructor
}

Note: virtual dtor MUST be implemented, even if it’s pure virtual. AbstractBook::~AbstractBook(){}

because subclass dtors will call it as part of step 3

class NormalBook:public AbstractBook{
  public:
	NormalBook &operator=(const NormalBook &other){
		AbstractBook:operator=(other);
		return *this;
	}
}

3.8 | Templates

class List{
	struct Node {
		int data;
		Node *next;
	};
	...
};

Template = class parameterized by a type (abstract)

template<typename T> class List{
	struct Node{
		T data;
		Node *next;
	}
	Node *theList;
  public:
	class Iterator{
		Node *p;
		...
	  public:
		T &operator*() {return p->data;}
		...		
	};
	...
	T &ith(int i){...}
	void addToFront(T n);
}

Client:

List <int> l1;
List <List <int>> l2;
l1.addToFront(3);
l2.addToFront(&l1);
 
for (List <int>::Iterator it = l1.begin; it!=l1.end(); ++it){
	cout << *it << endl;
}
 
// OR
for (auto n:l1){
	cout << n << endl;
}

Compiler specializes templates at the source code level and compiles from specializations

3.9 | Standard Template Library (STL)

Large # of useful templates (eg. dynamic-length arrays AKA vectors)

Braces don’t always work:

import <vector>;
std::vector<int> v{4,5}; // 4 5
v.emplace_back(6); // 4 5 6
v.emplate_back(7); // 4 5 6 7
 
// NOTE:
vector<int> v(4,5); // 5 5 5 5
 
std::vector w{4,5,6,7}; // no <int>
// if T can be deduced from the initialization, you can leave it out

Looping

for (int i=0; i<v.size(); ++i){
	cout << v[i] << endl;
}
// oh thats why begin and end
for (vector<int>::iterator it=v.begin(); it!=v.end(): ++it){
	cout << *it << endl;
}
for (auto n:v){
	cout << n << endl;
}
// iterating in reverse
for (vector<int>::reverse_iterator it=v.rbegin(); it!=v.rend(); ++it){
	...
}
v.pop_back(); // remove last element

User iterators to remove items from inside a vector (eg. remove all 5s)

for (auto it=v.begin(); it!=v.end(); ++it){
	if (*it==5) v.erase(); // WRONG
	// consider 1 5 5 2
	// it will erase the first 5, shift the second 5 up, then move to the 2 
	// misses a 5 whenever there are two 5s
}
 
// After insertion/erasure, all iterators pointing after are invalid 
// and should be refreshed
for (auto it=v.begin(); it!=v.end()){ // NO ++it
	if (*it==5) it = v.erase(it); // returns an iterator to the point of erasure
	else ++it; // only incremenet if not a 5
}

Life changing realization about v[i]

Unchecked - if you go out of bounds, UB

v.at(i) is a checked version of v[i]

C solution: functions return a status code or set the global variable errno (error number)
But this is unsafe …

3.10 | Exceptions

In C++, when an error condition arises, the function raises an exception

What happens?

By default, execution stops
But we can write handlers to catch and deal with them

vector<T>::at throws an exn of type std::out_of_range when it fails. We can handle it as follows:

import <stdexcept>;
...
	try { // this might fail
		cout << v.at(10000);
	}
	catch {
		(out_of_range r){ // out_of_range is the type, r is the exception
			cerr << "Range error" << r.what() << endl;
		}
	}

Now consider

void f(){
	throw out_of_range {"f"};
}
void g() { f(); }
void h() { g(); }
int main (){
	try{
		h();
	}
	catch (out_of_range){ ... } // no variable here
}

What happens?

main calls h
h calls g
g calls f
f throws

Control goes back through the call chain (unwinds the stack) until a handler is found

all the way back to main, main handles the exn
No matching handler in the entire call chain → program terminates
out_of_range is a class

throw out_of_range {"f"}; // ctor call
// "f" is what what() will produce

A handler might do part of the recovery job (ie. execute some corrective code + throw another exn)

try {...}
catch (SomeError s){
	...
	throw SomeOtherError {...};
}

or rethrow the same exn

try {...}
catch (SomeError s){
	...
	throw;
}

A handler can act as a catch-all:

try {
 ...
}
catch (...){ // literally "...", it finally happened
	...
}

You can throw anything you want - don’t have to throw objects

lectures/23-exceptions/exfact.cc

Define your own exception classes (or use appropriate existing ones)

class BadInput {};
try{
	if (int n; !(cin >> n)) throw BadInput{};
}
catch (BadInput) { cout << "Input not well-formed" << endl; }

NEVER let a dtor throw or propogate an exn

The program will abort immediately (this is defined behaviour)
If you really want to let a dtor throw, you can tag it with noexcept(false)

But if a dtor is running during stack unwinding while dealing with another exn and it throws, you now have two active, unhandled exns, the program will abort immediately.

4 | Design Patterns

4.1 | Observer Pattern

Public-subscribe model

One class publisher / subject - generates data
One or more subscriber / observer classes - receive data + react to it

Eg.

spreadsheet cells - subject
graphs - observer
When cells change, graphs update

Can be many kinds of observer objects - subject should not need to know all the details

┌─────────────────────────┐              0..*     ┌─────────────────────────┐
│       Subject           │◆──────────────────────│   <<interface>>         │
├─────────────────────────┤                       │      Observer           │
│ + attach(obs)           │                       ├─────────────────────────┤
│ + detach(obs)           │                       │ + notify()              │
│ + notifyObservers()     │                       └─────────────────────────┘
└─────────────────────────┘                                   △
            △                                                 │
            │                                                 │
            │ (inheritance)                                   │ (implements)
            │                                                 │
┌─────────────────────────┐                       ┌─────────────────────────┐
│   ConcreteSubject       │                       │   ConcreteObserver      │
├─────────────────────────┤                       ├─────────────────────────┤
│ - state                 │                       │ - observerState         │
├─────────────────────────┤                       ├─────────────────────────┤
│ + getState()            │◄─ ─ ─ ─ ─ ─ ─ ─ ─  ─ ─│ + notify()              │
└─────────────────────────┘    (dependency)       └─────────────────────────┘

Sequence of method calls:

Subject’s state is updated
Subject::notifyObservers() calls each observer’s notify()
Each observer calls ConcreteSubject::getState to query the state of reactor accordingly

Example: horse races

Subject - publishes winners
Observers - individual bettors - declare victory when their horse wins

class Subject {
	vector <Observer*> observers;
  public:
	void attach (Observer *o) { observers.emplace_back(o); }
	void detatch (Observer*o); // remove from observers
	void notifyObservers() { for (auto o:observers) o->notify(); }
	virtual ~subject() = 0; // pure virtual
};
Subject::~Subject() {};
class Observer{
  public:
	virtual void notify() = 0;
	virtual ~Observer() {}
};

Horse Race

class Subject{
	vector <observer *> observers;
  public:
	void attach (Observer *o) { observers.emplace_back(0); }
	void detatch (Observer *o) ; // remove from observers
	void notifyObservers () { for (auto o:observers) o->notify(); }
	virtual ~Subject() = 0;
};
Subject::~Subject(){}
 
class Observer{
  public:
	virtual void notify() = 0;
	virtual ~Observer();
}
 
class Observer{
	ifstream in;
	string lastWinner;
  public:
	HorseRace (string source): in{source}{}
	bool runRace() { return in >> lastWinner; }
	string getState() { return lastWinner; }
};
 
class Bettor:public Observer{
	HorseRace *subject;
	string name, myHorse;
  public:
	Betttor(...); ... { subject->attach(this); }
	~Bettor() { subject->detatch(this); }
	void notify(){
		if (subject->getState==myHorse) cout << "Win!" << endl;
		else cout << "Lose :(" << endl;
	}
}
 
// main.cc
HorseRace hr;
Bettoer larry {&hr, "Larry", "RunsLikeACow"};
// ... other bettors
while (hr.runRace()){
	hr.notifyObservers();
}

4.2 | Decorator Pattern

Want to enhance an object at runtime - add functionality / features

                    ┌─────────────────────┐
                    │      Component      │
                    │      "Window"       │
                    ├─────────────────────┤
                    │ + operation()       │
                    └─────────────────────┘
                          △         △  ↑
                          │         │  │
                          │         │  │
             ┌────────────┘         │  │
             │                      │  │
┌────────────┴──────────┐       ┌───┴──◇───────────────────┐
│   ConcreteComponent   │       │        Decorator         │
│    "Basic Window"     │       │                          │
├───────────────────────┤       ├──────────────────────────┤
│ + operation()         │       │ + operation()            │
└───────────────────────┘       └──────────────────────────┘
                                            △
                           ┌────────────────┴───────────────┐
                           │                                │
              ┌────────────┴──────────────┐     ┌───────────┴──────────────┐
              │     ConcreteDecoratorA    │     │   ConcreteDecoratorB     │
              │      "With Scrollbar"     │     │       "With Menu"        │
              ├───────────────────────────┤     ├──────────────────────────┤
              │ + operation()             │     │ + operation()            │
              └───────────────────────────┘     └──────────────────────────┘

Eg. Windowing system

Start with a basic window
Add scrollbar
Add menu

Component - defines the interface - operations your objects will provide ConcreteComponent - implements the interface Decorators - all inherit from Decorator, which inherits from components

Every decorator IS a component and every decorator HAS A component

Window with scrollbar is a kind of window, and has a ptr to the underlying plain window
Window w/ scrollbar + menu is a kind of window, has a ptr to a window w/ scrollbar, which has a ptr to a plain window
All inherit from AbstractWindow, so window methods can be used polymorphically on all of them

Eg. Pizza

                    ┌────────────────────┐
                    │       Pizza        │
                    └────────────────────┘
                          △         △  ↑
                          │         │  │
                          │         │  │
             ┌────────────┘         │  │
             │                      │  │
┌────────────┴───────┐          ┌───┴──◇──────────────┐
│   CrustAndSauce    │          │      Decorator      │
└────────────────────┘          └─────────────────────┘
                                            △
                           ┌────────────────┼───────────────┐
                           │                │               │
              ┌────────────┴───┐     ┌──────┴─────┐   ┌─────┴─────────┐
              │    Topping     │     │StuffedCrust│   │ DippingSauces │
              └────────────────┘     └────────────┘   └───────────────┘

class Pizza{
  public:
	virtual float price() const = 0;
	virtual string desc() const = 0;
	virtual ~Pizza(){}
};
// basic pizza is crust + sauce
class CrustAndSauce : public Pizza{
  public:
	float price() const override { return 5.99; }
	string desc() const override { return "Pizza"; }
};
class Destructor : public Pizza {
  protected:
	Pizza *component;
  public:
	Decorator (Pizza *p) : component{p}{}
	~Decorator() { delete component; }
}
// new file
class StuffedCrust : public Decorator {
  public:
	StuffedCrust (Pizza *p) : Decorator{p}{}
	float price() const override{ return component->price() + 2.69; }
	string desc() const override { return component->desc() + "w/ stuffed crust"; }
	
};
// Topping, DippingSuace left as exercise
 
// use
Pizza *pi = newCrustAndSauce;
p1 = new Topping {"Cheese", p1};
p1 = new Topping {"Mushrooms", p1};
p1 = new StuffedCrust {p1};
cout << p1->desc() << ' ' << p1->price << endl;
delete p1;

4.3 | Factory Method Pattern

Write a video with 2 kinds of enemies: turtles 4 bullets

System randomly sends turtles + bullets, but bullets are more frequent in higher levels
Never know exactly which enemy comes next, so you can’t call turtle/bullet ctors directly
Instead, put a factory methods in level that creates enemies

                ┌─────────────────────┐
                │       *Enemy*       │
                └─────────────────────┘
                          △          
                 ┌────────┴────────┐
                 │                 │
        ┌────────┴───────┐  ┌──────┴────────┐
        │     Turtle     │  │    Bullets    │
        └────────────────┘  └───────────────┘


                ┌─────────────────────┐
                │       *Level*       │
                └─────────────────────┘
                          △          
                 ┌────────┴────────┐
                 │                 │
        ┌────────┴───────┐  ┌──────┴────────┐
        │      Easy      │  │      Hard     │
        └────────────────┘  └───────────────┘

class Level{
  public:
	virtual Enemy *createEnemy() = 0;
	...
};
class Easy : public Level{
  public:
	Enemy *createEnemy() override{
		// create mostly turtles
	}
};
class Hard : public Level{
  public:
	Enemy *createEnemy() override{
		// mostly bullets
	}
}
// use
Level &l = newEasy;
Enemy *e = newhard;

4.4 | Template Method Pattern

Used when:

Want subclasses to override superclass behaviour, btu some aspects must stay the same
Eg. there are red turtles + green turtles

class Turtle{
  public:
	void draw(){
		drawHead();
		drawShell();
		drawFeet();
	}
  private:
	void drawhead(){...}
	virtual void drawsShell() = 0;
	void drawFeet(){...}
};
 
class RedTurtle:public Turtle{
	void drawShell() override {
		// draw red shell
	}
}
 
class GreenTurtle:public Turtle{
	void drawShell() override {
		// draw green shell
	}
}

Subclasses can’t change the way a turtle is drawn (head, shell feet), but can change the way a shell is drawn

Generalization: Non-Virtual Interface (NVI) idiom

A public virtual method is:
- Public: anybody can call it, an interface to the client, promises certain behaviors, pre/post conditions
- Virtual: subclass would replace this with anything, makes promise you can’t guarantee will be kept
NVI says:
- all public methods should be non-virtual
- All virtual methods should be private, or at least protected
- EXCEPT THE DTOR

Example:

class DigitalMedia{
  public:
	virtual void play() = 0;
};
 
class DigitalMedia{
  public:
	void play(){
		doPlay();
	}
  private:
	virtual void doPlay() = 0;
};

Generalizes template method - puts every virtual function inside a template method

4.5 | Maps (STL) - for creating dictionaries

eg. “arrays” that map strings to integers

import <map>;
map<string, int> m;
m["abc"] = 2;
m["def"] = 3;
cout << m["ghi"] << m["def"]; // if the key is not present it it inserted
// at the default construction value (for ints, 0)
 
m.erase("abc")
if (m.count("def")) ... // 0 = not found, 1 = found

Maps are balanced binary search trees (red/black trees usually) that hold its contents sorted Iterating over a map is in sorted key order

for (auto &p:m){
	cout << p.first << ' ' << p.second << endl;
}

p’s type is paid,string, int> from <utility>

std::pair is implemented as a struct, not a class, meaning fields are public

class implies you are making an abstraction and trying to protect invariants
struct implies there are no invariants (pair is two things glued together, no invariants, all fields valid)

Alternatively:

for (auto &[key, value]: m){
	cout << key << ' ' << value << endl;
}

Structured headings can be used on any structure (class) type with all fields public

// example
Vec v{1,2}; // assuming public fields
auto [x,y] = v; // x=1, y=2
 
// on stack arrays of known size:
int a[] = {1,2,3};
auto[x,y,z] = a; // x=1, y=2, z=3

4.6 | Exception Safety

void f(){
	C c;
	C *p = new C;
	g();
	delete p;
}

No leaks, but what if g throws?

It’s guaranteed that during stack-unwinding, all stack-allocated data is cleaned up
Dtors run, memory is reclaimed
heap-allcoated memory is not reclaimed

If g throws, c is not leaked, but *p is

void f(){
	C c;
	C *p = new C;
	try{
		g();
	}
	catch (...) {
		delete p;
		throw;
	}
	delete p; // in case no exception
	// but duplicate code is ugly and error prone
}

How can you guarantee that something (delete p) will happen no matter how we exit f (normal or exception)?

IN some languages, “finally” clauses guarantee certain final actions, - not in C++
Only thing you can count on in C++ is that dtors for stack-allocated data will run
Thus, use stack-allocated data as much as possible - use that guarantee to your advantage

C++ idion: RAII: Resource Acquisition Is Initialization (bad name)

Every resources should be wrapped in a stack-allocated object, whose job is to delete it

Eg. files

{
	ifstream f{"file"} 
	// acquiring the resource (file)_ = initializing the object (f)
	...
} 
// the file is guaranteed to be released when f is popped from the stack (f's dtor runs)

This can be done with dynamic memory: class std::unique_ptr <T> from import <memory

Takes a T* in it’s ctor
The dtor will delete the tpr
In between you can dereference it like a ptr

void f(){
	C c;
	std:: unique_ptr<c> p{new C};
	g(); // no leaks, guaranteed, even if g throws
}

Alternative:

void f(){
	C c;
	auto p = std::make_unique<c>(); // char args go in the brackets
	// make_unique allocates a C obj on the heap 
	// and puts a ptr next to it in a unique_ptr object
	g();
}

Difficulty

unique_ptr<c> p {new C};
unique_ptr<c> q = p; // won't compile
// two objects think they need to delete this - double free

Copying is disabled for unique_ptr (like with streams)

They can only be moved
”move” is really what we wanted “copy” to be

template <typename T> class unique_ptr{
	T *ptr;
  public:
	explicit unique_ptr (T*p): ptr{p}{}
	~unique_ptr{delete ptr;}
	unique_ptr(const unique_ptr &) = delete;
	unique_ptr &operator=(const unique_ptr &) = delete;
	unique_ptr(unique_ptr &&other): ptr{other.ptr}{
		other.ptr=nullptr;
	}
	// move asg - exercise
	T &operator *(){ return *ptr; }
	T *get(){ return ptr; }
};

What if we still wanted to copy ptrs?

Answer the question of ownership
Who will own the resource (take responsibility for freeing it)?
That ptr should also be a unique_ptr, and all other ptrs should be raw ptrs (can fetch the underlying raw ptr with .get())

New understanding of ptrs

unique_ptr indicates ownership - delete will happen automatically when the unique_ptr goes out of scope
raw ptr indicates non-ownership - i.e. someone else owns the object, so don’t call delete
moving a unique_ptr = transfer of ownership

unique_ptrs are generally moved when passed into a function or returned by a function

Ptrs as paramaters:

void f(unique_ptr<c> p);
// f will take ownerhip of the object pointed to by p
// caller loses custody of the object
 
void g(C *p);
// g will not take over ownership of the object pointed to be p
// caller's ownership of the object doesn't change
// it might not even own the object to begin with

Ptrs as results

unique_ptr<c> f();
// return by value is always a move
// so f is handing ownership of the C object to the caller
 
C *g()
// the ptr returned by g is understood not to be deleted by the caller
// so could be a ptr to non-heap data or heap data owned by someone else

Rarely, a situation may arise that requires shared ownership (any of several ptrs might need to free the resource)

std::shared_ptr

{
	auto p = std::make_shared<c>();
	if (...){
		auto q = p
	}; // q popped, ptr not deleted
} // p popped, ptr is deleted

shared_ptrs maintain a reference count - count of all shared_ptrs pointing at the same obj

Memory is freed when the # of shared_ptrs pointing to it will reach 0

(define lst1 (const 1 (const 2 (const 3 empty))))
(define lst2 (const 4 (rest lst 1)))

It’s not clear when the 2,3 nodes should be freed. Use the type of ptr that accurately reflects the ptr’s ownership role, and that causes dramatically fewer opportunities for leaks

What is exception safety? (important)

It is NOT that exceptions never happen / all exceptions get handled
It IS that after an exn has been handled, the program is not left in a broken or unusable state.

Specifically. there are 3 levels of exception safety for a function f:

Basic guarantee - if an exception occurs, the program will be in some valid state. Nothing is leaked, no data structures, all class invariants maintained
Strong guarantee - if an exception is raised while executing f, the state of the program will be as if f had not been called
No-throw guarantee - f will never throw or propagate an ex, and will always accomplish it’s task

class A {...}
class B {...}
class C {
	A a;
	B b;
  public:
	void f(){
		a.g(); // may throw, but strong guarantee
		b.h(); // may throw, but strong guaranatee
		// this means they either succeed, or thew throw and do nothing
	}
}

Is C::f exn safe?

If a.g() throws, nothing has happened yet - OK
If b.h() throws, effects of a.g() must be undone to offer the strong guarantee (very hard or impossible if g has non-local side effects). - NO, probably not
If A::g, B::h do not have non-local side effects, can use copy-and-swap

class C{
	...
	void f(){
		A atemp = a;
		B btemp = b;
		atemp.g()
		btemp.h()
		// if there's a throw in any of these 4 lines, we're fine
		a = atemp; // but what if copy a assignment throws?
		b = btemp; // or what if this fails?
	}
};

Summary

void f(){
	vector <c> v;
} // everything is cleaned up
 
void g(){
	vector <c*> v;
	...
} // array is freed, ptrs don't have dtors, any objects pointed to by ptrs STAY
// v is considered not to own those objects
 
void h(){
	vector <unique_ptr<c>> v; // owns
} // array is freed, unique_ptr dtors run, objects are deallocated
// no explicit deallocation

vector<T>::emplace_back - offers the strong guarantee. If the array is full (size == cap):

allocate a new array
copy objects over (copy ctor) - if a copy ctor throws:
- destroy the new array (no-throw)
- old array is still intact
- strong guarantee
delete old array (no-throw)

BUT

copying is expensive and the old array will be thrown away
wouldn’t moving the objects be more efficient?
- allocate new array
- move the objects over (move ctor) - if a move ctor throws
  - can’t guarantee strong guarantee
  - original objects no longer intact
- delete old array

If the move ctor offers the nothrow guarantee, emplace_back will use the move ctor. If not, It’ll use the copy ctor (slower). So your move ops should provide the nothrow guarantee, and you should indicate that they do.

class C{
	...
  public:
	C (C &&other) noexcept {...}
	C &operator= (C &&other) noeccept {...}
};

If you know a function will never throw or propagate an exception, declare it noexcept

facilitates optimizations
At minimum, moves and swaps should be noexcept

4.7 | Modularization

So far, each class gets a module.

But a module can contain any # of classes and functions
When do you group together vs keep separate?

2 measures of design quality: coupling and cohesion Coupling = how much distinct modules depend on each other

Low coupling (favoured)
- Modules communicate via function calls with basic params/results
- Modules pass arrays/structs back and forth
- Modules affect each other’s control flow
High coupling (could be done with one file)
- Modules have access to each other’s implementation (friends)
- Changes to one module affect the other modules more

Cohesion = how closely items in a module are related to each other

Low cohesion (could be done with hella files)
- Arbitrary groups of unrelated elements (eg. <utility>)
- Elements share a common theme - otherwise unrelated (eg. algorithm)
- Elements manipulate state over the lifetime of an object (eg. open/read/close files)
- Elements pass data to each other
High cohesion (favoured)
- Elements cooperate to perform exactly one task

Goal: Low coupling, high cohesion Special case: What if 2 classes depend on each other?

// A.cc
class B; // use forward declaration
class A{
	int x;
	B y;
}
 
// B.cc
class B{
	char x;
	A y;
}

Sometimes one class must come before another

class C {...}; // must come first
class D:public C {...}
CLass E { C c; }; // need to know the size of C to construct D+E

How should A+B above be placed into modules?

Modules must be compiled in dependency order
One module cannot forward-declare another module, nor any item within another module
A+B must reside in the same module (they’re tightly coupled anyway)

4.8 | Decoupling the interface / single responsibility principle

Your primary program classes should not be printing things

class Chessboaard{
	cout << "Your move";
}
// bad design - inhibits code reuse
// what if you wanted to reused Chessboard but not have it use stdout?
// give ihe class stream objects for I/O
class ChessBoard{
	istream &in;
	ostrean &out;
  public:
	out << "Your move"
};

Better - but what if we don’t want to use streams at all? Your chessboard should not be doing any communication at all

Single responsibility principle: A class should only have one reason to change

If two or more different parts of the program spec affect the same class, then that class is doing too much
Each class should do only one job - game state and communication are two jobs

Better:

Communicate with the Chessboard via params/results/exns
Confine user communication to outside the game calss
Should have a class to manage communication that is separate from the game state class

4.9 | Casting

In C:

Node n;
int *ip = (int *)&n // cast - forces a Node& to be treated like an int*

Should be avoided in C++, which has 4 kinds of casting

static_cast - casts that have well-defined semantics

// numeric converstions
// superclass ptr to subclass ptr
Book *b = new Text{...}
Text *t = static_cast<Text*>(b);
// You're taking responsibility that b actually points at a text - "Trust me"
 
// eg. double cast
double d;
void f(int x); // calls this one
void f (double x);
f (static_cast<int>(d));

reinterpret_cast - unsafe, implementation-specific, “weird” casts

Student s;
Turtle *t = reinterpret_cast<Turtle *>(s);

const_cast - for converting between const and non-const - the only C++ const that can “cast away const”

void g(int *p); // suppose you know g will not modify *p in the circumstances when f is called
 
void f(const int *p){
	...
	g(const_cast<int *>(p));
	...
}

dynamic_cast - is it safe to cast a Book* to a Text*?

Book *pb = ...;
static_cast<Text *>(pb)->getTopic(); // safe?
// depends on what pb actually points at

Better to do a tentative cast - try and see if it works

Text *t = dynamic_cast<Text *>(pb);

If the cast works (ie. pb really points at a text), t points at the object
If the cast fails, t will be nullptr

if (t) cout << t->getTopic();
else cout << "Not a text";

Can we do these casts on smart pters?

Yes - static_pointer_cast, dynamic_pointer_cast, etc
cast shared_ptrs to shared_ptrs

Dynamic casting also works with refs:

Text t{...}; 
Book &b = t;
Text &t2 = dynamic_cast<Text &>(b)

If the cast doesn’t work, no null refs (throws std::bad_cast)

Dynamic ref casting offers a possible solution to the polymorphic assignment problem

Text *Text::operator=(const Book &other){ // virtual
	const Text &tother = dynamic_cast<const Text &>(other);
	// throws an exn if other is not a text
	Book::operator=(other);
	topic = tother.topic;
	return *this;
}

Is dynamic casting good style?

Can using dynamic Casting to make decisions based on an object’s runtime type information (RTTI)

void whatIsIt(Book *b){
	if (dynamic_cast<Comic *>(b)) cout << "Comic";
	else if (dynamic_cast <Text*>(b)) cout << "Text";
	else if (b) cout << "Book";
	else cout << "Nothing";
}

Code like this is tightly coupled to the Book hierarchy and may indicate bad design

If you create a new type of Book
- whatIsIt doesn’t work anymore - needs a clause for the new type
- must find and fix all uses of dynamic casting before the code will work
Better: use virtual methods

Note: Text::operator= does not have this problem (only comparing with one type, not all types in the hierarchy). Not all dynamic casts are bad

How could we fix whatIsIt?

class Book{
	...
  public:
	virtual void identify(){ cout << "Book"; }
};
void whatIsIt(Book *b){
	if (b) b->identify();
	else cout << "Nothing";
}

works by creating an interface function that is uniform across book types
but what if the interface isn’t uniform across the hierarchy?

Inheritance and virtual methods work best when:

Unlimited # of subclasses all with the same interface
Adding a new subclasses has no effect at all

What about the opposite case?

Small # of subclasses, all known in advance, unlikely to change
Having different interfaces
Adding a new subclass is going to take work but we don’t expect to do it, or we’re expecting the effort

class Turtle:public Enemy{
  public:
	void stealShell();
};
class Bullet:public Enemy{
  public:
	void deflect();
};

Interfaces not uniform, but we don’t expect the set of enemies to grow without doing work. So we could regard the set of enemies as fucked, and dynamic casting on enemies would be fine

But then - maybe inheritance wasn’t the right abstraction medium

If your design says an enemy can be only a Turtle of Bullet, any you accept the additional work that would come from expanding this set, then consider:

import <variant>;
typedef variant<Turtle, Bullet> Enemy;
// equiv, using Enemy = variant<Turtle, Bullet>;
// an Enemy is a Turtle of Bullet, period
Enemy e{Turtle{}}; // or Bullet{}
 
if (holds_alternative<Turtle>(e)){
	cout << "Turtle";
}
else ...
// Extracting the value
try {
	Turtle t = get<Turtle>(e);
	// use t...
}
catch (bad_variant_access){...}

Variant - like a union, but type-safe. Attempting to store as one type + fetch as another will throw

using Enemy = variant<Turtle, Bullet>;
Enemy e {Turtle{}};
try{
	Turtlet = get<Turtle>(e);
	...
}
catch (Bad variant access){...}

If a variant is left uninitialized, the first option in the variant is default-constructed to initialize the variant. This leads to a compile error if the first option is not default constructible.

Options

Make the first option a type with a default ctor
Don’t leave your variant uninitialized
Used std::monostate as the first option
1. ”dummy” type that can be used as a default
2. can be used to create an “optional” type

variant<monostate, T>; // = "T or nothing"
optional<T>;

4.10 | How Virtual Methods Work

class Vec {
	int x,y;
	void f();
}
class Vec2 {
	int x,y;
	vrtual void f();
}
// what's the difference?
// do these two look the same in memory?
Vec v{1,2};
Vec2 w{1,2};
 
cout << sizeof(v) << " " << sizeof(w); // 8 16

Why?

8 is space for 2 ints and no space for the f method
Compiler turns methods into ordinary functions and stores them separately from objs

Recall

Book *pb = new {Book, Text, Comic};
auto pb = make_unique{Book, Text, Comic}(...);
 
pb->isHeavy();

If isHeavy is virtual

The choice of which version to run is based on the type of the actual object
Which the compiler won’t know in advance
The correct isHeavy must be chosen at runtime. How?

For each class with virtual methods, the compiler creates a table of function pairs (the vtable)

class C {
	int x,y;
	virtual void f();
	virtual void g();
	void h();
	virtual ~c();
};

C objects have an extra pointer (the vptr) that points to C’s vtable

Then you call a virtual method, the following happens at runtime

follow vptr to vtable
fetch the ptr with the actual method from thet able
follow the function to call the function
this means that virtual method calls incur a small overhead cost

Concretely, how is an object laid out? Compiler-dependent

Why did we put the vptr first in the obj, and not somewhere else (eg. last)

so we know which version of the function to call

// so a ptr to B looks like a ptr to A if you ignore the last two fields
class A {
	int a,c;
	virtual void f();
};
class B:public A {
	int b,d;
}

4.11 | Multiple Inheritance

Other languages are scared of this, but C++ isn’t!

A class can inherit from more than one class:

class A {
	public int a;
}
class B {
	public int b;
}
class C: public A, public B {
	void f() { cout << a << " " << b; } 
};
 
// chalenge
class D: public B, public C {
	public:
		int d;
}
D dObj;
dOBj.a; // which a is this? ambiguous, so compiler rejects
// need to specify
dObj.B::a;
dObj.C::a;

But if B,C both inherit from A, should there be one A part of D or two?

should B::a and C::a be the same or different?
deadly diamond

Make a virtual base class (virtual inheritance)

class B: virtual public A{...};
class C: virtual public A{...};

4.12 | Template Functions

template <typename T> T max(T x, T y){
	return x < y ? y : x;
}
int f(){
	int x = 1, y = 2;
	int z = max(z,y); // T = int
	// C++ can infer that from the types of x and y
}

If C++ cannot determine T, you can always tell if

z = max<int> x,y;
max('a', 'c'); // T = char
max(1.0, 3.0); // T = double

For what types T can max be used?

i.e. For what types T will the body compile?
any types for which operator< is defined
C++ <algorithm library is a suite of template functions, many of which work over iterators

templaet <typenmae Iter, typename T>
Iter find (Iter start, Iter finish, const T&val){
	// returns an iterator pointing to the first val in [start, finish)
	// or finish, if not found
}
Iter count (Iter start, Iter finish, const T&val){
	// like find, but returns # occurances of val
}
template <typename inInter, typename OutIter>
 
OutIter copy (InIter start, InIter finish, OutIter result){
	// copies one container range [start, finish) to another
	// starting at result
	// does NOT allocate new memory
}

vector V{1,2,3,4,5,6,7};
Vector <int> w(4); // space for 4 ints
copy (v.begin()+1, v.begin()+5, w.begin()); // w = {2,3,4,5}
 
template<typename InIter, typename OutIter. typename Fn>
OutIter transform(InIter start, InIter finish, OutITer result, Fn f){
	while (start != finish){
		*result = f(*start);
		++start;
		++result;
	}
	return result;
}
 
int add1(int n){ return n+1; }
...
vector v{2,3,5,7,11};
vector <int> w(v.size());
transform(v.begin, v.end(), w.begin(), add1); // w={3,4,6,8.12}

How generalized is this code?

what can we use for Fn?
What can we use fir InIter/OutIter?

Part 1: Fn - how is f used? f(*start)

f is anything that can be called as a function
Can write operator() for objects

class Plus1{
  public:
	int operator() (int n) { return n+1; }
}
Plus1 p;
p(4); // produces 5
transform(v.begin(), v.end(), w.begin(), Plus1{});

Generalize

class Plus{
	int m;
  public:
	Plus (int m): m{m}{}
	int operator()(int n) { return m + n; }
};
transofrm (v.begin, v.end(), w.begin(), Plus{1});

Advantage of function objects - can maintain state

class IncreasingPlus{
	int m=0;
  public:
	int operator()(int n){return n + (m++);}
	void reset() { m = 0; }
}
 
Vector v(5,0); // 00000
vector<int> w(v.size());
transform(v.begin(), v.end(), w.begin(), IncreasingPlus{});
// w = {0,1,2,3,4}

Consider: how many ints in a vector are even?

vector v{...};
bool even(int n){return n % 2 == 0;}
int x = count_if(v.begin(), v.end(), even);

If this were Racket, we would use lambda

int x = count_if(v.begin(), v.end(), [](int n){return n % 2 == 0;});
// stuff can go in the []
// lambda doesn't create a function, but an object with an operator()

Part 2: Iterators - apply the notion of iteration to other data sources (like streams)

import <iterator>
vector v{1,2,3,4,5};
ostream_iterator<int>out {cout, ", "};
copy(v.begin(), v.end(), out); // prints 1,2,3,4,5
 
vector<int> w;
vopy(v.begin(), v.end(), w.begin()); // wrong
// copy doesn't allocate space in w (it' can't)
// it doesn't even know that iterator is iterating through a vector

but what if we had an iterator asg operator inset a new item?

copy (v.begin(), v.end(), back_inserter(w)); 
// copies v to the end of w, add new items

Julian's Vault

Explorer

CS 246