CS 246 - Object-Oriented Software Development
Instructor: Brad Lushman
Section: 001
Location: MC 4045
Time: Tuesdays and Thursdays 10:00am - 11:20am
Tutorials: MC 4060 Wednesdays 1:30pm - 2:20pm
Term: Spring 2016

Shoutout to Brian Forbes, Steven Yang, and Ziqi Zhou!

May 3, 2016 - Lecture 1

Grading Scheme

  • Assignments - 0(A0) 7 7 7 7 12(project) = 40%
  • Midterm (4:30pm - 6:20pm, June 23 (Th), 2016) = 20%
  • Final = 40%

This course requires you to work in Linux. There are several options:

  1. Lab machines
  2. Install Linux on your own machines
  3. Make SSH connection to school machines (Use Putty (putty.exe) on Windows, winscp for file transfer, XMing for Xwindows)
  4. Download cygwin - Linux-like environment for Windows
  5. Get a Mac

4 Modules in this Course:

  • Linux Shell (2 weeks)
  • C++ Language, C++14 (10 weeks)
  • Tools
  • Software Engineering (design etc.)

“Homework”: Go on Piazza -> Linux Reference Sheet -> Save and print

Module 1: Linux Shell

A shell is an interface to the operating system, i.e. how we get the OS to do things (run programs, manage files etc.). There are two kinds of shells: graphical (with icons and clicking) and the command line. The shell we will use is Bash. Check if you are using Bash, login to shell and type in:

$ echo $0

It should return “bash”.

Linux file system: working with files

cat - short for concatenate; display contents of a file (e.g. cat user/share/dict/words). In Linux, a directory is considered a special kind of file

ls - list files in the current directory (non-hidden files)

ls -a - list all files (including hidden; hidden files start with a “.”)

pwd - print current directory (pwd = print working directory)

What happens when we only type in “cat”? It just kind of sits there, waiting for input. It’s kinda like a parrot, repeating what you typed in. If we can capture the output into a file…

$ cat > output.txt

It would capture the input. NOT RECOMMENDED: ^C. It would prevent cat from doing clean-up. Let it finish on its own: ^D at the beginning of a line sends an “EOF” signal to cat.

One greater than sign replaces, two appends.
In general, command args > file executes command args + captures the output in file -> called output redirection.

Using less than sign, takes in input from the file.

$ cat < output.txt

The line above displays the file. Seems to be equivalent to what we have before. Are these two things the same? NO. The reason is very important:

  • cat input.txt -> passes the NAME input.txt to cat as an argument. Cat opens input.txt and displays its contents

  • cat < input.txt -> the shell opens the file and passes the contents to cat IN PLACE of keyboard input

wc - word count, displays numbers of lines, words, and characters of a file

cat *.txt - *.txt globbing pattern -> matches any sequence of characters (the shell finds all files that mathch the pattern)

cat < *.txt - ERROR! The shell will only attach one file to cat’s input stream

Many (but not all) commands take both kinds of inputs:

cat < input.txt > output.txt - sends chars from input.txt to output.txt; effectively a copy-paste action

Every process is attached to 3 streams. Stdin goes into the program, stdout and stderr come out of the program. Stdin -> program -> stdout and stderr. By default, stdin = keyboard, stdout, stderr = screen. < connects stdin to file, > connects stdout to file, 2> stdrr. Stderr separates output stream from error messages, so that output error messages can go to different places, and that error messages don’t cut/block output files.

Also, stdout may be buffered. System may assemble characters before displaying. However, stderr isn’t buffered, because user needs to see error messages immediately.

Pipes: Make one program’s output(stdout) another program’s input(stdin). Example: How many words occur in the first 20 lines of sample.txt?

head -n file

gives the first n lines of file

wc -w

counts words (just print the word count)

so

head -20 sample.txt | wc -w
Here, (the pipe symbol) makes the output of the command before it the input of the command after it.


May 4, 2016 - Tutorial 1

To zip your assignment files, do:

zip (directory where your files are).zip *

in the directory where the files are.

marmoset_submit cs246 (question, e.g a0) (file you want to submit, zipped)

is how you submit assignments to Marmoset.


May 5, 2016 - Lecture 2

Suppose we have files words1.txt, words2.txt…, and each of them has one word per line. We want: A duplicate-free list of all the words used in any of these files

We need the following:

  • sort - sorts lines (man: Write sorted concatenation of all FILES(s) to standard output)
  • uniq - remove consecutive duplicate lines from input (man: filter adjacent matching lines from INPUT, writing to OUTPUT)

One possibility:

cat words*.txt | uniq

What’s the problem with this? We must sort our input first, because for aabaacd, it would produce abacd, with duplicates.

This should work:

cat words*.txt | sort | uniq

Sort it first, then call uniq. But there’s still a problem: it’s way too inefficient, beacuse it cat(s) all the files together FIRST, and then sorts it.

This is better:

sort words*.txt | uniq

Q: Is it possible to use the output onf one program as a parameter to another?

Yes. E.g.

echo "Today is $(date) and I am $(whoami)"

The shell executes date and whoami, and subsitutes the results into the command line.

WARNING:

echo 'Today is $(date) and I am $(whoami)'

This will print the LITERAL interpretation, i.e. Today is $(date) and I am $(whoami)
Single quotes do not execute the substitution.

echo "$(ls words*.txt)"

prints a list of names of the text files:
words1.txt
words2.txt

Pattern Matching in Text Files
Use egrep (extended global regular expression print) = grep -E

egrep pattern file

returns all lines that contain the pattern.

E.g. print lines that contain “cs246”

egrep cs246 index.html

What about “cs246” OR “CS246”?

egrep "cs246|CS246" index.html

The vertical bar (|) means “OR”, and the double quotes prevent the shell from interpreting the bar as a pipe.

We can use parentheses to group subexpressions together:

egrep "(cs|CS)246" index.html

The patterns that egrep understands are called regular expressions. NOT globbing patterns.

“(c|C)(s|S)246” is equivalent to “[cC][sS]246”

[…] syntax says to match any SINGLE character in he square brackets. (a|1|c|2) is equivalent to [a1c2].

[^…] matches any 1 character not in the square brackets.

“[cC][sS] ?246” allows for an optional space before the 246. ? syntax says to match 0 or 1 occurrences of the preceding expression.

* syntax which matches 0 or more of the preceding expression. So (cs)*246 -> 246, cs246, cscs246, cscscs246…
cs(cs)*246 matches at least one cs at the front (eliminating the zero case)

(cs)+246 is equivalent to cs(cs)*246. The + syntax matches 1 or more of the preceding expression.

.* will match any sequence of characters

.+ will match any non-empty sequence of characters

“cs *246” matches any string starting with cs, followed by any string, followed by 246.

^ matches beginning of line

$ matches the end of line

^cs246 line starts with cs246

cs246$ line ends with cs246

Want all lines of even length

^(..)*$

The Other Section

Pipes allow us to hook the stdin of one program to the stdout of another. This is done using the pipe character | between commands

cmd1 args1 | cmd2 args2

Regex Rules:

  • Can use parentheses for a sub-pattern
  • Can use square brackets to match any one character in the square brackets
  • [^…] matches any one character EXCEPT those in the square brackets
  • A ? after a pattern or character represents 0 or 1 of that pattern/character
  • A * after a pattern/character represents 0 or more of that pattern/character
  • A + “1 or more”
  • . matches any SINGLE character
  • ^ and $ match the start and end of line respectively

E.g.
.* - anything
.+ - non-empty string
^.+$ - all non-empty lines
^.*$ - all lines

^(..)*$ - grabs all lines with even number of characters

Permissions

  • ls -l gives the long form listing of the files in the current directory
  • First 3 bits: Owner r-read w-write x-execute
  • Middle 3 bits: Group
  • Last 3 bits: Others
  • r: ordinary files-> can be read, directories-> contents can be read, globbing workds, ls works
  • w: ordinary files->can be modified, directories-> contents can be modified, add/remove
  • x: file’s contents can be executed as a program, directories->directories can be navigated (can cd into the directory)

Changing Permissions

  • to change permissions use chmod

      chmod mode file
    
  • mode is broken up to 3 parts - user, operator, and permissions
  • user is either u (owner), g (group), o (other), or a (all)
  • operator is either + (add), - (remove), = (set exactly)
  • permissions are r, w, x

E.g.

chmod o+r filename

gives other group read access to the file

chmod o-r filename

is the reverse

chmod a-r filename

then nobody can read it

chmod u=rwx filename

then the owner can do anything with it.

Shell Scripts

A shell script is a file containing sequences of shell commands execueted as a program. For example if we wanted to print the date, current user, current dir.

#!/bin/bash (this header tells the OS that this is a Bash script; allows the OS to interpret it the following as bash commands)
date
whoami
pwd

.sh is the standard extension of a bash script, but you can put whatever you want. Don’t forget permissions. Needs to be executable. Use chmod to give it executation rights.

Variables

  • Variables can be assigned with single equals.
  • x=1 (NO SPACES!!!)
  • use echo &{x} to grab the value of the variable x (parentheses run what’s inside it in a “subshell”) (curly braces are important: good practice)

Shell Script Example

Write a script that takes in a string to check if it is BAD. A string that can be found in a dict is bad. General format of conditional statements in bash:

if [ cond ]; then // the square brackets cannot "touch" what's inside
...
elif [ cond ]; then
...
else
...
fi

$? contains the return value of the last-run command. $1 retrieves the first parameter

Create a .sh script as follows:

#!/bin/bash

egrep "^$1$" /usr/share/dict/words > /dev/null  # /dev/null is where data goes to DIE

if [ $? -eq 0 ]; then //-eq compares
echo Bad password
else
echo Maybe not the worst
fi

And before you run it,

chmod u+x goodpass.sh

In bash, the pound symbol (#) starts a comment.


May 10, 2016 - Lecture 3

Review:

egrep pattern file

prints all lines in file that contain a match to pattern

Shell Scripts Review

#!/bin/bash  #"Shebang line"  
date  
whoami  
pwd

To run the script in the current directory:

./myscript

Variables

x=1 #NO SPACES  
echo $x #Use $ when fetching the value of a variable
# No $ when setting a var ($ = "fetch the value of")
# Good practice: ${x} - brace brackets, good style
# All vars contain strings, e.g. x is the STRING 1, not the number/int

E.g.
dir = ~/cs246 echo ${dir} /u/bmlushma/cs246 # get the absolute path ls ${dir} # contents of cs246

There are some global variables:
env # environment variables echo ${PATH} # list of directories (where the shell looks for programs)

When you type a command, the shell searches the list in order for a matching program.

echo * # prints all files in the current directory
echo "*" - suppresses globbing pattern
echo '*' - suppresses globbing pattern
echo "$PATH" # expands the quotes, $-expansion happens
echo '$PATH' # absolutely literally

Special Variables for Scripts
$1, $2, … # command-line arguments

E.g. check whether a word is in the dictionary

./isItAWord hello

#!/bin/bash

egrep "^$1$" /usr/share/dict/words # prints the word if found, prints nothing if not

E.g. a good password is not in the dictionary

egrep "^$1$"/usr/share/dict/words > /dev/null # to black hole, suppress output
# we could store the out in a variable
x=$egrep ...

Note: every program returns a status code when finished: egrep returns 0 if found, 1 if not found (general convention in UNIX: 0 means success, non-0 means failure)

$? # status of the most recently executed command

if [ $? -eq 0]; then # the first square bracket is the name of a program, and what's inside the square brackets are its arguments
    echo Bad password
else
    echo Maybe a good password
fi

We want to verify that the user has inputted the correct number of arguments, and print a usage message if it’s wrong

#!/bin/bash

usage() {
    echo "usage: $0 password" # $0 is the name of the script/program as it was typed
}

if [ $# -ne 1 ]; then # $# is the number of arguments
    usage
    exit 1
fi

egrep ... # as established above

Now this is a good program that can also check if the input is valid.

The general structure of conditional statements is as follows:

if [ cond ]; then
    ...
elif [ cond ]; then
    ...
else
    ...
fi

Comparisons to other conditions: Check the Linux reference sheet

Loops

Loops: print the numbers from 1 to $1

#!/bin/bash
x=1
while [ $x -le $1 ], do
    echo $x
    x=$((x+1)) # $(()) for arithmetic
done

Looping over a list, e.g. rename all .cpp to .cc

#!/bin/bash
for name in \*.cpp; do # for ... in sets the variable to each word in the given list
    mv ${name} ${name%cpp}cc # value of name, without trailing cpp
done

e.g. how many times does word $1 occur in the file $2?

#!/bin/bash
x=0
for word in $(cat "$2"); do #good idea - enclose vars in double quotes, prevent bad input
    if [ $word == $1 ]; then #String equality == instead of -eq
        x=$((x+1))
    fi
done
echo $x

e.g. Payday is the last Friday of the month. When is this month’s payday?

2 tasks here: compute date and fomat the answer

cal | awk '{print $6}' | egrep "[0-9]" | tail -1


May 11, 2016 - Tutorial 2

Want: stdout and stderr in the same file

printer » out 2> out # works printer > out 2» out #doesn’t work

#Alternatives printer &> out printer > out 2>&1 printer 2>out 1>&2

Want: Give the top 10 most commonly used words

sort wordCollection uniq -c head # problem    
sort wordCollection uniq -c sort tail # works  
sort wordCollection uniq -c sort -k1,1rn -k2,2 head # sort takes in arguments -k as key; 1,1 = first character r = reverse order(descending) n = sort in numerical order, 2 break ties  
sort wordCollection uniq -c sed ‘s_612 sort tail # Use sed to replace 6s with 12s and then sort lexigraphically
sort wordCollection uniq -c sed ‘s_612 sort -k1,1nr -k2,2 head

egrep:

^ - match beginning of line
$ - match end of a line
^$, ^a$
. - matches any single character
? - matches preceeding pattern 0 or 1 times
* - 0 or more
+ - 1 or more

Note: abc* != (abc)* ab, abccc, abcccccc, in comparison to abc, abcabc, abcabcabc


May 12, 2016 - Lecture 4

Recall: compute payday (last Friday of the month); report nicely

#!/bin/bash

answer() {
  if [ $1 -eq 31 ]; then # inside a fn - $1, $2 etc are the args to the function
    echo "This month: the 31st"
  else
    echo "This month: the ${1}th"
  fi
}

answer $(cal | awk '{print $6}' | egrep "[0-9]" | tail -1) # the whole thing after the dollar sign is ${1}

Generalize to any month:

cal June 2016 # gives calendar for June 2016
Want: let payday June 2016 gives June 2016’s payday

#!/bin/bash

answer() {
  if [ $2 ]; then
    preamble=${2}
  else
    preamble='This month'
  fi

  if [ $1 -eq 31 ]; then
    echo "${preamble}'s payday is on the 31st."
  else
    echo "${preamble}'s payday is on the ${1}th."
  fi
}

answer $(cal $1 $2 | awk '{print $6}' | egrep "[0-9]" | tail -1) $1 # if $1 and $2 are supplied, revert back to previous behaviour

Software Engineering: Testings(aka QA lmao)

  • essential part of program development
  • ongoing, not just at the end
    • begins BEFORE coding
    • test suites - expected behaviour
  • NOT debugging - cannot debug without first testing
  • cannot guarantee correctness, can only prove wrongness
  • ideally, developer + tester should be different people

Human Testing - Humans look over code, find flaws, code inspection, walkthroughs
Machine Testing - Run the program on selected input, check against spec, can’t test everything - choose test cases carefully

Black/White/Grey Box Testing: no/full/some knowledge of program implementation
Start with black box, supplement with white box

  • various classes of input, e.g. numerical ranges, positive/negative
  • Boundaries of valid ranges (edge cases)
  • Multiple simulatenous boundaries (corner cases)
  • Intuition/Experience (“Ayy I’ve seen programs like that before, better try blah lmao”)
  • Extreme cases (e.g. integer overflow; how large can the integer get before it breaks)

White box - executes all logical paths through the program

  • run through the true part and false branch of conditional statements
  • every way you can go from start to finish should be tested
  • make sure every function you write actually gets called

Performance Testing - Is the program fast enough?
Regression Testing

  • Make sure new changes to the program don’t break old tests
  • test suites (ALWAYS ADD TESTS; NEVER SUBTRACT), testing scripts

Module 2: C++ (ayy)

Hello World in C:

#include <stdio.h>

int main() {
  printf("Hello World!\n");
  return 0;
}

Hello World in C++:

#include <iostream>
using namespace std;

int main() {
  cout << "Hello World" << endl;
  return 0;
}

Notes:

  • main MUST return int in C++
  • stdio.h, printf still available in C++
  • preferred C++ I/O: header

Output:

std::cout << ___ << ____ << ____  
std::endl = end-of-line

Using namespace std lets you say cout and endl instead of std::cout and std::endl

Return statement - returns status code to the shell ($?). If left out, main returns 0

Compiling C++ Programs

On the school Linux environment:

    g++-5 -std=c++14 program.cc -o program
    (-o program is the name of the executable binary (if not specified: a.out))
    // OR
    g++14 program.cc -o program // if you have done A0 and made the alias
    // Run the program by
    ./program

Input/Output
3 IO streams: cout - for printing to stdout, cin - for reading from stdin, cerr - for writing to stderr

Operators: « “put to” - Output, » “get from” - input

  cerr << x // x flows to cerr
  cin >> x // input flows to x
  // The operator points in the direction of information flow

E.g. Add 2 numbers

#include <iostream>
using namespace std;

int main() {
  int x, y;
  cin >> x >> y; // cin ignores whitespace; gets two integers, ignoring whitespace
  cout << x+y ;
}

If the input doesn’t contain an integer next - statement fails, value of the var is undefined

What if the input is exhaustive, before we get two ints? - Same as above

If the read failed: cin.fail() will be TRUE
If we got an EOF: cin.fail() and cin.eof() will be both TRUE; cin.eof() not until the attempted read fails

E.g. Read all ints from stdin, echo one per line to stdout. Stop on bad input or EOF

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


May 17, 2016 - Lecture 5

E.g. Read all ints from stdin + echo, one per line, to stdout, stop on bad input of EOF

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

Recall: if read fails, cin.fail() will be true; if EOF: cin.fail() and cin.eof() both true, but not until the attepted read fails

Note: there is an implicit conversion from cin to bool, so cin can be used as a condition. The conversion is that it’s true if fail/bad/eof bits are clear, or false if fail/bad/eof set

E.g. v2.0

int main() {
	int i;
	while (true) {
		cin >> i;
		if (!cin) { // using cin as the condition, means the same thing as the other program
			break;
		}
		cout << i << endl;
		}
}

Note: » is C’s right bitshift operator; a » b shifts a’s bits to the right by b spots

E.g. 21 » 3; 21 in binary is 10101, push the last 3 digits off the cliff, so it becomes 10 in binary, which is 2; equivalent to dividing by 2 to the b-th power, ignoring remainders

But when the left hand side is cin, this is the “get from” operator

operator >>
 	// inputs: LHS cin (istream), RHS data (variety of types); output: return cin (istream)
 	// This is why we can write: cin >> x >> y >> z; cin >> x produces cin, x gets populated, and now we get cin >> y >> z, and so on.

E.g. v3.0

int main() {
  int i;
  while (true) {
    if (!(cin >> i)) { // using it as both a condition and populating i
      break;
    }
    cout << i << endl;
  }
}

E.g. v4.0

int main() {
  int i;
  while(cin >> i) { // changing the break statement into a single while loop
    cout << i << endl
  }
}

E.g. read and echo ints until EOF, skip non-integer input

int main() {
  int i;
  while (true) {
    if (!(cin >> i)) {
      if (cin.eof()) {
        break;
      }
      cin.clear(); // clears the fail bit, so that cin is ready to read again
      cin.ignore(); // throws away the next character
    } else {
      cout << i << endl;
    }
  }
}

E.g. Reading strings: type std::string (#include )

int main() {
  string s;
  cin >> s;
  cout << s << endl;
}
// skips leading white space;
// stops at whitespace (reads one word)

What if we want the hvitespace? Use getline(cin, s), it reads from the current position to next newline, into s.

cout << 95 << endl; // prints 95

What if we want to print a number in hexadecimal?

cout << hex << 95 << endl;
// this will print 95 in hex, 5f
// hex is std::hex, is the I/O manipulator, reconfigures the
// output string, all subsequent ints are printed in hex
// (FOR THE REST OF ETERNITY, nah jkjk till the program terminates); A bit of an overkill?
cout << dec; // goes back to decimal

// Other manipulator, SEE NOTES, don't forget #include <iomanip>

Stream abstraction applies to other fsources of data

Files - Read from a file instead of stdin
std::ifstream reads from a file
std::ofstream writes to a file

File access in C:

#include <stdio.h>
int main() {
	char s[256];
	FILE *file = fopen("suite.txt", "r"); // r = read mode; file is a handle
	while (true) {
		fscanf(file, "%255s", s);
		if (feof(file)) break;
		printf("%s\n", s);
	}
	fclose(file);
}

File access in C++:

#include <iostream>
#include <fstream>
using namespace std;

int main() {
	ifstream file{"suite.txt"}; // creating and initializing an ifstream opens the file
	string s;
	while (file >> s) {
		cout << s << endl;
	}
	// IMPORTANT: the file is closed when the variable (in this case, file), goes out of scope; when the program stops, it's popped of the runtime stack, it then closes.
}

Anything you can do do with cin and cout, you can do with an ifstream or an ofstream. ANYTHING.

E.g. string - attach a stream to a string and read/write it

#include <sstream>
// std::istringstream and std::ostringstream
// read from/write to a string

int hi = ..., lo = ...;
ostringstream ss; // think of it as a sock
ss << "Enter a # between" << lo << "and" << hi; // stuffing the sock with string
string s = ss.str(); // cuts open the sock and gets the string
cout << s << endl;

E.g. convert a string to a #

int n;
while (true) {
  cout << "Enter a number" << endl;
  string s;
  cin >> s;
  istringstream ss {s};
  if (ss >> n) break; // stop if you get int
  cout << "I said,";
}
cout << "You entered" << n << endl;

Example revisited - echo numbers, skip non-numbers

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

Strings

In C, array of char (char* or char[]), terminated by IO. Must manage own memory: get morememory when strings grow; Easy to overwrite IO and corrupt program

In C++, strings grow as needed, and are thus safer.

E.g.

string s{"Hello"}; // it's still an array (C-style string);
// C++ string created from C string on initialization

String Operations:

  • Equality Inequality, s1 == s2, s1 != s2
  • Comparison: s1 <= s2 (lexicographical comparison)
  • Length: s.length()
  • Extract individual characters: s[0], s[1] etc.
  • Concatenation: s3 = s1 + s2, s3 += s4
  • More details: SEE NOTES

Default Function Parameters

void printSuiteFile(String name = "suite.txt") {
  // default value, must be last
  ...
}

printSuiteFile("suite2.txt");
printSuiteFile(); // prints from suite.txt

Note: optional params must be last; if you leave out two parameters, they have to be the last two; 3,3 etc.


May 18, 2016 - Tutorial 2

Shell Scripting

  • Exit codes are important; non-zero return/exit value = ERROR
  • Write to the correct stream
  • Scoping for subroutines, anything defined befored a subroutine is visible(and modifiable) in the subroutine, except positional arguments ($1, $2, …)

Testing

  • Don’t have to worry about invalid inputs
  • Testing is hard
  • Try sanity checks (“No one could make this mistake”)
  • Good coverage: boundary/edge and corner cases, equivalence classes, weird cases

Possible Test Cases

  • Equivalence courses: small, medium, and large values of the target
  • Boundary/edge cases: test containing 0 as target

C++ I/O

  • DO NOT USE C I/O
  • 3 default streams: cout, cerr, cin
  • If a read from cin fails, all subsequent reads will fail

Make I/O More Robust

  • Reading from cin could fail in two ways
    • EOF
    • got unexpected input
  • When a read fails, a flag goes up in cin
    • cin.fail() will be true
    • Only cin.fail() will be true if it was an error
    • Both cin.fail() and cin.eof() will be true if it was EOF
    • How to clear: cin.clear() -> put all cin flags down and turn it into a valid state
    • How to continue: cin.ignore(); order is important: clear then ignore
  • If you want the entire line, use getline(cin, s)

Strings

  • Encapsulates something like char* in C
  • Has length, insert, delete, search methods
  • Can be accessed like an array
  • include
  • at(index): checks for bounds and throws an exception if out of bounds
  • [index]: does not check for bounds


May 19, 2016 - Lecture 6

Overloading

C: Functions with different parameter lists cannot share the same name

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

C++: Functions with different parameter lists can share the same name

int neg(int n) { return -n; }
int neg(bool b) { return !b; }
// example of overloading

Compiler uses number of types of arguments to decide which neg is being called.

Overloads must differ in number of type of arguments, not just on the return type. We’ve seen this before: », « (operators, could be right shift/left shift, or could be input and output; the behaviour depends on types of args)

Structs

struct Node {
  int data;
  Node *next;
}; // don't forget the semicolon

Node n1{5, nullptr}; // nullptr is the syntax for a null pointer in C++.
// Do not say NULL or 0 in this class!!!!!!!
// 0 will be always treated as a number, not pointer

const Node n2 = n1; // constant struct means that its fields
// cannot be changed; n2 is an immutable copy of n1

Parameter Passing

Recall:

void inc(int n) {
  n = n + 1;
  // ...
}
int x = 5;
inc(x);
cout << x << endl; // prints 5; call-by-value
// inc gets a copy of x and modifies the copy, not the original

Sol’n: If a function needs to modify its arugument - pass a pointer

void inc(int n) {
  *n = *n + 1;
  // ...
}
int x = 5;
inc(&x); // x's address passed by value, inc changes value at that address, visible to caller
cout << x << endl; // prints 6

Question: Why cin » x and not cin » &x?
Answer: C++ has another pointer-like type: references

References (IMPORTANT!!!)

int y = 10;
int &z = y; // NEW. Ampersand after int.
// z is an lvalue reference to int (which is y)
// Reference is like a constant pointer, similar to int *const z = &y;
// (z is a constant pointer to an int; z will always point to y implied by const)
// (but y is not constant; you can change y however you like)

References are like constant pointers with automatic dereferencing.

z = 12; // NOT *z = 12
int \*p = &z; // &z gives the address of y.
// No matter what you do to z, you do it y.
// In all cases, z behaves exactly like y. z is an alias for y.

Things you CANNOT do with lvalue references

  • leave them uninitialized, because they are constant, cannot assign later
    • must be initialized with something that actually has an address (an lvalue) since references are pointers
    • E.g.
    int &x = 3; // WRONG: WONT COMPILE!
    // because 3 is not an address, it's a constant literal
    int &x = y + z; // WRONG!
    int &x = y; // GOOD
    
  • create pointer to a reference: int &* x; // WRONG
    • reference to a pointer is legal: int *& x;
  • create a reference to a reference: int && x = …; // means something different (will discuss later)
  • create an array of references: int &a[] = {x, x, x}; // given the similarity between arrays and pointers

Things you CAN do with lvalue references

  • Pass as function parameters:
void inc(int &n) { // const pointer to the argument (x), thus changes to n affect x
  n = n + 1; // no pointer dereferencing
}
int x = 5;
inc(x);
cout << x << endl; // prints 6

Why does cin » x work? It takes x by reference

istream &operator » (istream &in, int &n);

Pass-by-value

E.g.

int f(int n) {...} // copies the argument
// if the argument is big, copying is expensive

struct ReallyBig{}; // Massive struct with thousands of fields
int f(ReallyBig rb) {...} // copying would be slow

int g(ReallyBig &rb) {...} // pass as reference, no copy, it's an alias, fast
// this could change rb in the caller, in contrast to pass by value, which guarantees
// no changes to rb itself after calling

int h(const ReallyBig &rb) {...} // pass constant reference, no copy, fast, and the parameter cannot be changed

Advice: prefer pass-by-const-reference over pass-by-value for anything larger than an int, unless the function needs to make a copy anyway - then maybe pass by value. DEFAULT SHOULD BE PASS-BY-CONST-REF. Sizeof reference is same as size of a pointer

Also:

int f(int &n) {...}
int g(const int &n) {...}

f(5); // LMAO FAILS WON'T COMPILE, because 5 does not have an address;
// can't initialize an lvalue reference (n) to a literal value;
// if n changes, can't change the literal 5

g(5); // OK; since n can never be changed, the compiler will allow this
// How though? The compiler creates a temporary location to hold 5, so that n has something to point at

That’s why const ref is so CRITICALLY IMPORTANT.

Dynamic Memory Allocation

C:

int *p = malloc(n * sizeof(int));
free(p);
// Don't use these in this course though

C++: new/delete

E.g.

struct Node {
  int data;
  Node *next;
}

Node *np = new Node; // allocates a Node on the heap and np points to it
// ...
delete np;
// all local variables reside on the stack
// deallocated (popped) when their scope ends
// Allocated memory is on the heap, it stays there until you get rid of it
// Remains allocated until delete is called

If you don’t delete - MEMORY LEAK

Arrays on the heap

Node *myArray = new Node[10];
// ...
delete [] myArray; // The square brackets have to be there

E.g.

Node getMeANode() {
  // copy to caller's frame, expensive
    Node n;
    return n;
}

Node &getMeANode() {
  // WORST. Returns a ref (essentially a pointer) to
  // stack-allocated data, which is dead on return
    Node n;
    return n;
}

Node *getMeANode() {
  // fast-ish and safe, not returning pointer to dead data
  // caller responsible for delete when done
    Node *np = new Node;
    return np;
}

Considering all options, do No.1.

Operator Overloading
Give our own 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;
}


May 24, 2016 - Lecture 7

Preprocessor Variables

  • We can also define preprocessor symbols via the compiler; with gcc, syntax is -Dvname or -Dvname=val (-DX)
  • ifdef and ifndef directives: these check if a preprocessor variable has been defined (a use for simply defining variables); can be used to debug; #ifdef DEBUG to conditionally print stuff out to debug code; can offload run time to compile time
    • syntax:
        g++14 -DDEBUG program.cpp // set DEBUG
      

Separate Compilation

  • To help readability and create modularity we can split our programs into composable modules. Each module consist of interface (type definitions and prototypes for functions, .h file, contains declarations, won’t allocate space for the variables) and implementation (full details, allocates space for variables/functions, .cpp file, contains definitions)
  • Example: Let’s take the vector struct and overloaded addition operator we created and put in a module so that it can be used by other files; create vec.h and vec.cpp
// vec.h
struct Vec {
  int x, y;
};

Vec operator+(const Vec &v1
              const Vec &v2); // constant reference to vectors, do not modify the originals

// ---------------------------------------
// vec.cpp
#include "vec.h"
// to get the struct definition from the interface file

Vec operator+(const Vec &v1, const Vec &v2) {
  return {v1.x + v2.x, v1.y + v2.y};
}

// main.cpp
#include "vec.h"
using namespace std;

int main() {
  Vec x {1,2};
  Vec y {3,4};
  Vec v = x + y;
  cout << v.x << ", " << v.y << endl;
  return 0;
}

when compiling:

g++14 -c vec.cpp // -c oppresses linking, creates .o (object) file
g++14 -c main.cpp
g++14 vec.o main.o -o main
./main

Global Variables

  • Consider we want to want to define a global variable in a module
// abc.h
int globalNum; // Wrong - definition and declaration
// This won't work, every file that includeds abc.h
// defines a SEPARATE globalNum and the program will not link
  • Solution: put the variable in the .cpp file
// abc.h
extern int globalNum; // Correct, just declaration
// extern keyword
// -------------------------
// abc.cpp
int globalNum;

Multiple Includes

  • Always put #include guards in .h files (ifdef, define, endif)
  • Never put using namespace std in .h files; DO NOT USE ANY NAMESPACES WHATSOEVER!

Classes

  • The big innovation of OOP - we can put functions inside of structs
  • A class is some struct that can contain functions
  • An object is an instance of a class
  • Member functions (aka Methods) are functions inside a class
  • this = pointer to the object a member function is called on; syntax: this->var; s.grade() is like calling grade(&s)


May 26, 2016 - Lecture 8

Classes Continued

Recall: student.cpp, implemented as struct
This class:

Initializing Objects

  • When creating an object typicaly the class will have data members that need to be assigned values - initialized
  • As shown in the student example we could use curly braces to initialize our class, and in C++ this is true for most types - this is called Uniform Initialization
  • Ex. Student bob {60, 70, 80} in the student.cpp example

Constructors

  • Without defining how your class should be constructed C++ just takes those values and assigns them to each field in the order they were declared - this is okay, but has limitations
  • A better idea is to include in your class a method that does the initialization - called a constructor
  • Ex. in the student.cpp example

    Student(int assns, int mt, int final) { // Debug statement here this->assns = assns; this->mt = mt; this->final = final; } // default value given Student(int assns=0, int mt=0, int final=0) { // … }

Notes on Initialization

  • Sometimes variables are initialized with the assignment operator

    int x = 5; string s = “hello”;

  • And sometimes with (), especially when invoking Constructors

    int x(5); string s(“Hello”) Student bob(60, 70, 80)

  • An exception to this: std::vector

    std::vector B{1,3,5} // contains elements 1,3,5 std::vector V(5) // of size 5 std::vector G{1} // actually contains element 1; curly brackets -> element rather than size

  • Also,

    int x = 2.0; // the decimal will get chopped off int x {2.0} // COMPILER ERROR

  • A class is a struct itself, an object is an actual variable of that type

Default Constructor

  • Every class comes with a default (zero-argument) constructor which calls: you can create an object but set its values later
  • As soon as you declare your own constructor, you lose the default

#

  • What about if our class contains a constant field or a reference field?
  • For example let’s consider adding an ID field to our student class, this should be a const value that never changes but is different for each initialized student object
  • Where to initialize them though? Struct definition (i.e. create an ID field in the struct; const int id = 0;)? In the body of the constructor?
  • Problem: const int should be initialized
  • Solution:

Object Creation Steps

  • Space is allocated
  • Fields are constructed
  • Constructor body runs
  • The moddile step is the missing piece of the puzzle where our initialization must go!

MIL

  • The member initialization list is part of our constructor that specifies how to initialize object and non-static data members of our class
  • Can be used for any non-static memebers
  • Initialized in order of declaration in struct
  • Is more efficient, when the constructor is doing the same thing as the MIL, when there is a class inside a class (school class in student class)
  • Ex.

    Student(): assns{assns}, mt{mt}, final{final}, id{id} {

    }

Copy Constructor

  • What happens when you use the assignment opeartor to instantiate an object?
  • Ex.
Student a {60,70,80}
Student b = a;
  • b will be initialized via the copy constructor
  • All classes have an implicit copy constructor that just copies all regular data fields and calls copy constructors on all object fields
  • Ex.
#include "Node.h"
Node::Node(const Node &in) : data(in.data) {
  if (in.next) {
    next = new Node(*in.next);
  } else {
    next = nullptr;
  }
}
// recursively copies the nodes

Implicit Methods

  • Every class comes with
    • A default constructor
    • A copy constructor (just copies all fields)
    • A copy assignment operator
    • A destructor
    • A move constructor
    • A move assignmenet operator

Notes on Copy Constructor

  • The copy constructor (implicit or otherwise) is called when
    • An object is initialized by another object
    • When an object is passed by value
    • When an object is returned by a function

Implicit conversion

  • Be careful with a constructor that takes only one parameter - this will create an implicit conversion

Destructor

  • Necessary if your class has any memory allocated on the heap


May 31, 2016 - Lecture 9

Recall

  • Copy constructor
Node *n = new Node {1, new Node {2, new Node {3, nullptr}}};
Node m = *n; // copy ctor
Node *p = new Node {*n}; // copy ctor
  • Simple copy of fields -> only the first node actually copied (shallow copy)
  • If you want a deep copy (copy the whole list), must write your own copy constructor
struct Node {
	// ...
	Node (const Node &other) :
    data {other.data},
    next {other.next? new Node {*other.next} : nullptr};
    // recursively copies the rest of the list
};

The copy constructor is called:

  1. When an object is initialized with another object (same class)
  2. When an object is passed by value
  3. When an object is return ed by a function

There are exceptions to all 3.

Note: Careful with chars that can take ONE argument

E.g.

struct Node {
  Node (int d): data {d}, next {nullptr} {}
  // ...
};

//Single-argument ctors create implicit conversions

Node n(4);
Node n{4};
// but also
Node n = 4;
// You can also do this now
int f (Node n) {...}
f(4);
// You can do this because 4 is implicitly converted to Node
// How converting C string to C++ string makes sense; generally not a good idea though

Danger: accidentally pass an int to a function expecting a Node

  • Compiler does not signal an error
  • Potential errors not caught

Good idea: disable the implicit conversion

struct Node {
  // ...
  explicit Node (int d): data {d}, next {nullptr} {}
};

// Now these are still fine
Node n(4);
Node n{4};
// But these are not
Node n = 4;
int f (Node n) {...}
f(4);

Destructors

When an obect is destroyed a method called the destructor runs

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

Specifically:

  1. The destructor body runs
  2. Destructor is called on all the fields (called in reverse declaration order; if declared from top to bottom, then destroyed from bottom to top)
  3. Space is deallocated

Class comes with a destructor (just calls destructors for all fields that are objects)

When do we need to write one?

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

If np goes out of scope, the pointer is reclaimed (it was on the stack), the memory is leaked.

If we say delete np; it calls *np’s destructor, which doesn’t do anything (it only frees the very first node (1), 2, 3 are leaked)

Write a destructor to ensure the whole list is freed:

struct Node {
  // ...
  ~Node() { // tilda has the connotation of negation; NOT; opposite of constructor

    delete next; // recursively calls
    // *next's destructor, thus the whole list is deallocated*
    // do not need to check nullptr
  }
}

Copy Assignment Operator

Student billy {60, 20, 80};
Student jane {billy}; // copy constructor
Student joey; // default constructor
joey = billy; // copy, but not construction
// Above is copy assignment operator, uses compiler-supplied default

You need to write your own copy assignmennt operator when there is heap-allocated memory

struct Node {
  // ...
  Node &operator=(const Node &other) {
    // returns Node & so that cascading works
    data = other.data;
    // next = other.next would be wrong (shallow copy)
    // because that's what the default one does
    delete next; // otherwise it leaks, because the old object could point to real data
    // in order to replace the old data, need to delete old data
    next = other.next? new Node {*other.next} : nullptr;
    return *this;
    // DANGEROUS STILL //*
  }
};

Very dangerous.
Why?

Node n {1, new Node {2, new Node {3, nullptr}}};
n = n; // deletes n, then tries to copy n to n, UNDEFINED BEHAVIOUR

// For example:
*p = *q; // where p and q points to the same address
a[i] = a[j]

When writing operator=, ALWAYS watch for self-assignment

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

Better:

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;
}

Above works even if other is in my list, if new fails, Node will still be ain a valid state

Alternative - idiom

#include <utility>

struct Node {
  // ...
  void swap(Node &other) {
    using std::swap;
    swap(data, other);
    swap(next, other.next);
  }

  Node &operator=(const Node &other) {
    Node tmp = other; // copy other
    swap(tmp); // swap with my old data
    return *this; // tmp deallocated, frees my old data
  }
}

Rvalues + Rvalue references

Recall: an levalue is anything an address, an lvalue reference (&) is always initialized by an lvalue

Node n{1, new Node{2, nullptr}};
Node m = n; // copy ctor
Node m2;
m2 = n; // copy assignment operator

Node plusOne(Node n) {
  for (Node *p = &n; p; p=p->next) {
    ++p->data;
  }
  return n;
}

Node m3 = plusOne(n); // What runs? What is other here?
// Compiler creates a temporary object to hold the result of plusOne, so other has something to point at
// copy ctor deep copies data drom the temp object


June 2, 2016 - Lecture 10

  • Need to be able to tell whether other is a reference to a temporary object or a standalone object
  • C++: rvalue reference Node&& is a reference be a temporary object (aka rvalue) of type Node
  • Version of the ctor that takes a Node&&
struct Node {
    // ...
    Node(Node &&other) { }
    // ... called a move ctor
}

What should it do? Steal other’s data.

...
Node (Node &&other):
    data{other.data},
    next{other.next} { // steal data
        other.next = nullptr; // other will be destroyed, so point to null so that the Nodes it points to won't get destroyed
    }

Similarly:

Node m;
m = addOne(n); // Assignment from temporary

More assignment operator:

Node &operator=(Node &&other) {
    // steal other's data
    // destroy my old data
    // so we can just swap without copy

    using std::swap;
    swap(data, other.data);
    swap(next, other.next);
    return *this;

    // temp object will be destroyed and take our old data with it
}

If you don’t define move ctor/move assignment operator, copy versions will be used.
If the move ctor/move assignment operator is defined, it will replace calls to the copy ctor/copy assignment operator where the argument is a temporary (an rvalue).

Copy/Move Elision

Vec makeAVec() {
    return {0,0}; // invokes basic ctor
}

Vec v = makeAvec(); // what operations run here? copy ctor? move ctor?
// Not sure, in g++: just the basic ctor, no cpy ctor, no move ctor

In some circumstances, the compiler is allowed to skip calling copy/move ctors (but doesn’t have to). In the example above, makeAVec writes its result ({0,0}) directly into the space occupied by v in the caller, rather than copy it later

Example:

void doSomething(Vec v) { // pass-by-value copy ctor

}

doSomething(makeAVec());
  • result of makeAVec() written directly into the parameter - no copy
  • This is allowed, even if dropping ctor calls would change the behaviour of the program (e.g. if the ctors print something)
  • In this course, you are not expect edt oknow the eact circumstances under which copy/move elision is allowed

If you need all of the ctors to run:

g++14 -fno-elide-constructors

But this can slow down your program considerably.

In summary: Rule of 5 (Big 5)

If you need a custom version of any one of: 1. copy ctor 2. copy assignment operator 3. destructor 4. move ctor 5. move assignment operator Then you usually need a custom version of all 5. Because the circumstances you need to create one of them, will probably mean that these also apply to the other 4.

Notice: operator= is a member function, not a standalone function. When an operator is a member, “this” plays the role of the LHS argument.

struct Vec {
    int x, y;
    // ...
    Vec operator+(const Vec &other) {
        return {x+other.x, y+other.y};
    }
    Vec operator*(const int k) {
        return {k*x, k*y}; // implements v*k
    }
}

How do we do k*v? Can’t be a member-first arg not vec. Must be a non-member (as before)

I/O operators:

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

What’s wrong? It makes Vec the LHS and ostream the RHS. Use as v « cout

So define «, » as standalone functions.

Certain operators must be members:

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

Arrays of Objects

struct Vec {
    int x, y;
    Vec (int x, int y):
    x{x}, y{y}
    {

    }
};

Vec *vp = new Vec[10]; // ERROR
Vec moreVectors[15]; // ERROR

These want to call the default ctor on each item, but there isn’t one. Thus cannot initialize.

Options:

  1. Provide a default ctor
  2. For stack arrays:
Vec moreVecs[3] = {...};
  1. For heap arrays, create an array of pointers
Vec **vp = new Vec*[5];
vp[0] = new Vec{0,0};
vp[1] = new Vec{1,3}; // etc...
// then delete

for (int i = 0; i < 5; ++i) {
    delete vp[i];
}

delete [] vp;

Separate Compilation for Classes

// Node.h

#ifndef _NODE_H_
#define _NODE_H_

struct Node {
    int data;
    Node *next;
    explicit Node(int data, Node *next=nullptr);
    Node(const Node &other);
}
#endif

// Node.cc

#include "Node.h"

// Prefix with Node::
// Double colon :: = scope resolution operator

Node::Node(int data, Node *next): data{data}, next{next} {}
Node::Node(const Node &other): data{other.data}, next{} {}

// Node::___ means ____ in the context of struct Node
// :: is like . for classes
// . where LHS is a class (or namespace), not an object

Const Objects

int f(const Node &n) {...}    

Const objects arise often, especially in params.
What is a const object? - Fields cannot change.

Can we call methods on a const object?
Issue: method might change fields (violate const)

A: Yes. We can call methods that promise not to mofidy fields

struct Student {
    int assns, mt, final;
    float grade() const; // doesn't modify fields, so declare it const
}

Compiler checks that const methods don’t modify fields. Only const methods can be called on const objects.

Now consider: Want to collect usage stats on Student obj

struct Student  {
    // ...
    int numMethodCalls = 0;
    float grade () { // now can't call on const Students
        ++numMethodCalls;
        return ;
    }
}

But mutating numMethod calls affect only the physical constness of the object (actual bit pattern), not its logical constness (whether it acts like a constant).

Want to update numMethodCalls, even if the object is const. Solution: Declare the field mutable

struct Student {
    // ...
    mutable int numMethodCalls = 0;
    // can be changed, even if the object is const

    float grade () {
        ++numMethodCalls;
        return 100;
    }
}


June 7, 2016 - Lecture 11

Static Fields and Methods

struct Student {
  mutable int nCalls = 0;
  float grade() const {
    ++nCalls;
    return 0; // blah blah blah
  }
};

nCalls tracks the number of times a method was called on a particular object. What if we want the number of calls over all Student objects? Or what if we want to know how many Students were created?

Static Members

  • Associated with the class itself, NOT any particular object
struct Student {
  // ...
  static int numInstances;
  Student() {
    ++numInstances;
  }
};

// in .cc file
int Student::numInstances = 0;

NOTE: Static fields MUST be defined external to the class

Static Member Functions

  • Don’t depend on any particular instance (no “this” parameter) (not methods)
  • Can only access static fields and call other static member functions
struct Student {
  // ...
  static int numInstances;
  static void printNumInstances() {
    cout << numInstances << endl;
  }
};

// main
Student billy {};
Student jane {};
Student::printNumInstances(); // prints 2

Invariants and Encapsulation

struct Node {
  int data;
  Node *next;
  Node(int d, Node *n);
  ~Node() {
    delete next;
  }
};

// main

Node n1{1, new Node{2, nullptr}};
Node n2{3, nullptr};
Node n3{4, &n2};

What happens when these go out of scope? n3’s destructor tries to delete &n2, which is on the stack, not on the heap! Thus, UNDEFINED BEHAVIOUR!

Class Node relies on an assumption, called an invariant, a statement that shold always be true. In this case, the invariant is that next is either:

  • a nullptr, or
  • a valid pointer to the heap

But we cannot guarantee this invariant. Because we cannot control the user, we cannot guarantee any invariant because the user can interfere. For example, in a stack implementation, the invaraint is: last item pushed is the first item popped. If you cannot rely on variants, it would be hard to reason about programs

To solve: Encapsulation - we want clients to treat objects as “black boxes” (or capsules)

  • Implementation details are sealed away
  • Can only interact via the provided methods
  • Can create an abstraction, regain us control

E.g.

struct Vec {
  Vec(int x, int y); // by default, public
private:
  int x, y; // can only be accessed from inside Vec
public:
  vec Operator+(const Vec &v); // anyone can access
};

In general, we want fields to be private, and only methods should be public. Introducing class:

class Vec { // constructors etc are public
  int x, y; // private by default now
public:
  Vec(int x, int y);
  Vec operator+(const Vec &v);
};

Only difference between struct and class: default visibility, otherwise completely identical

Now we fix the linked list class

// list.h

class List {
  struct Node; // private nested class
  Node *theList = nullptr;
public:
  void addToFront(int n);
  int ith(int i);
  ~List();
  // ... etc etc
};

// list.cc
#include "list.h"
struct List::Node {
  // nested class
  int data;
  Node *next;
  Node(int d, Node *n): { // MIL

  }
  ~Node() {
    delete next;
  }
};

void List::addToFront(int n) {
  theList = new Node(n, theList);
}

int List::ith(int i) {
  Node *cur = theList;
  for (int j = 0; j < i; j++) {
    cur = cur->next;
  }
  return cur->data;
}

List::~List() {
  delete theList;
}

Only List can create/manipulate Node objects, thus we can guarantee the invariance that next is either a nullptr or a valid pointer to the heap. BUT, now we can’t traverse the entire list in linear time. Repeated calling ith(int i) to traverse the whole list -> O(n2) time. On the other hand, we can’t expose the Nodes or we will lose encapsulation

SE Topic: Design Patterns

  • Certain problems arise frequently
  • Keep track of good solutions and use them in similiar situations
  • Good Solutions Hall of Fame
  • If you have a situation like this, then this technique may solve it

In this case, we use the Iterator Pattern.

  • Create a class that manages access to nodes (abstraction of a pointer)
  • Walk through the list without exposing the next pointers
class List {
  struct Node; // nested inner class
  Node *theList;
public:
  class Iterator {
    Node *p;
  public:
    explicit Iterator(Node *p): p{p} {}

    int &operator*() { // reference because might want to modify data
      return p->data;
    }

    Iterator &opeartor++() {
      p = p->next;
      return *this;
    }

    bool operator==(const Iterator &other) {
      return (p == other.p);
    }

    bool operator!=(const Iterator &other) {
      return !(*this == other);
    }
  };

  // standalone functions
  Iterator begin() {
    return Iterator(theList);
  }

  Iterator end() {
    return Iterator(nullptr);
  }

  // ... other list functions follow

};

// client

int main() {
  List l;
  l.addToFront(1);
  l.addToFront(2);
  l.addToFront(3);
  for (List::Iterator it = l.begin(); it != l.end(); ++it) {
    cout << *it << endl;
  }
  // prints 1 2 3
}

Shortcut when writing the Iterator for loop: we can use automatic type deduction

auto x = y; // auto gives x y's type

for (auto it = l.begin(); it != l.end(); it++) {
  cout << *it << endl;
}

// "shortercut" - Range-based for loop
for (auto n : l) {
  cout << n << endl;
}

Range-based for loop: available for all classes with:

  • Methods begin, end that produce Iterators
  • Iterator must support !=, prefix ++, unary *

If we want to modify list items(or save copying):

for (auto &n : l) { // use reference
  ++n;
}


June 9, 2016 - Lecture 12

But List client can create Iterators directly by doing the following:

auto it = List::Iterator{nullptr};

This violates encapsulation as the client should be calling begin and end, which we provide.

We could preserve encapsulation by:

  • Making Iterator’s constructor private
    • Then client cannot call List::Iterator
    • But then neither can List
  • Solution: give list privileged access to Iterator -> make it a friend

E.g.

class List {
  // ...
public:
  class Iterator {
    Node *p;
    explicit Iterator(Node *p);
  public:
    // ... Iterator functions
    // friend
    friend class List; // List now has access to all members of Iterator
  }
}

Now, List can still create Iterators, but client can only create Iterators by calling begin and end.

NOTE: Give your classes as few friends as possible, because it weakens encapsulation. Once again, we want to keep fields private.

What if you want to give clients access to fields? “Getters” and “Setters” methods

E.g.

class Vec {
  int x, y;
public:
  int getX() const { return x; }
  void setY(int newY) { y = newY; }
};

What about operator «? It needs x and y, but it cannot be a member function

  • If getX, getY are defined, then we are ok
  • But if you don’t want to provide getX and getY, make operator« a friend function that is standalone

E.g.

// .h file

class Vec {
  // ...
public:
  // ...
  friend std::ostream &operator<<(std::ostream &out, const Vec &v);
};

// .cc file

ostream &operator<<(ostream &out, const Vec &v) {
  return out << v.x << " " << v.y;
}

Tools Topic: Make

Separate Compilation: lectures/c++/tools/example1

g++14 -c list.cc
g++14 -c node.cc
g++14 -c iter.cc
g++14 -c main.cc
g++14 main.o iter.o node.o list.o -o myprogram

Why do we do this? So we don’t have to recompile files that haven’t changed.

But how do we keep track of what’s changed and what hasn’t? Let Linux help you with make. We can create a Makefile that says which files depend on which other files. Refer to /lectures/c++/tools/example1/Makefile

myprogram: main.o list.o node.o iter.o # (myprogram depends on these)
  g++-5 -std=c++14 main.o list.o node.o iter.o -o myprogram # (tab in the beginning)

Then from the command line:

make # builds the whole project
# Now change iter.cc
make # recompiles iter.cc and then relinks myprogram

Command make: builds the first target (myprogram) in the Makefile. And what does myprogram depend on? main.o, list.o, node.o, iter.o. So make recursively builds these if necessary. Make uses a dependency graph.

For example, iter.cc changes, then iter.cc is now newer than iter.o (by checking the last modified date and time). Thus make rebuilds iter.o. Now iter.o is newer than myprogram, thus make rebuilds myprogram

Make can also build specific targets, for example make node.o

Common practice: put a target clean: at the bottom of the Makefile to remove all binaries

.PHONY: clean # (to avoid a file called clean if present)
clean:
  rm *.o myprogram

To do a full rebuild:

make clean
make

Now we can generalize with variables. In the Makefile:

CXX = g++-5
CXXFLAGS = -std=c++14 -Wall # (turns on all warnings)

E.g.

iter.o: iter.cc iter.h
${CXX} ${CXXFLAGS} -c iter.cc

Shortcut: for any make of the form

x.o: x.cc a.h b.h

We can leave out the build command and make would guess that the build command is ${CXX} ${CXXFLAGS}, so we can just write

-c x.cc -o x.o

Biggest problems:

  • Writing dependencies
  • Maintaining them if they change

Can get help from g++:

g++14 -MMD -c iter.cc

This creates iter.o and iter.d, and iter.d contains:

iter.o: iter.cc list.h node.h

Now just include iter.d in the Makefile:

CXX = g++-5
CXXFLAGS = -std=c++14 -Wall -MMD
OBJECTS = main.o list.o iter.o node.o
DEPENDS = ${OBJECTS:.o=.d}
EXEC = myprogram

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

-include ${DEPENDS}

As the project expands, just add .o files to the Makefile

System Modelling

Building an object-oriented system involves identifying abstractions and formalizing the relationships among items. It helps to map out relationships. A popular standard is the Unified Modelling Language (UML). Modelling a class, write its name, fields (optional), and methods (optional), and use + to denote public and - to denote private

Relationship: Composition

class Vec {
  int x, y;
public:
  Vec(int x, int y);
};

class Basis {
  Vec v1, v2;
};

// client
Basis b;

This will not compile because Basis cannot initialize v1, v2, because the default constructor for b calls default constructors for v1, v2, which do not exist.

class Basis {
  Vec v1, v2;
public:
  Basis(): v1{1, 0}, v2{0, 1} {} // default constructor, now it will compile
};

Embedding one object (v1) into another (b), called composition. The relationship between Basis and Vec is called “owns-a”, as a Basis “owns a” two Vecs.

If A owns a B, then typically:

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


June 14, 2016 - Lecture 13

A car owns 4 wheels

  • A wheel is a part of a car
  • Destroy the car -> Destroy the wheels
  • Copy the car -> Copy the wheels
  • Implementation: Composition of classes
  • UML: A -> B (filled arrow), means A owns some number of B’s, can annotate with multiplicities

Relationship: Aggregation

  • Compare parts in a car (“owns a”) vs. car parts in a catalogue
  • A “has a” relationship (aggregation): the catalogue contains the partsm but the parts have an independent existence
  • If “A has B”, then typically:
    • B has an existence apart from its association with A
    • If A is destroyed, then B lives on
    • If A is copied, B is not (shallow copy) - copies of A share the same B
  • Implementation: Pointer fields

E.g. Parts in a catalogue, ducks in a pond; UML: Pond -> Duck (hollow arrow)

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

class Car {
  Person *driver;
}

Specialization/Generalization (Inheritance)

Suppose you want to track your collection of books

class Book {
  string title, author;
  int numPages;
public:
  Book(...); // ctor
  // other functions
};

For textbooks, we also want the topic:

class Text {
  string title, author;
  int numPages;
  string topic;
public:
  Text(...); // Text ctor
  // other functions
};

For comic books, we want the hero:

class Comic {
  string title, author;
  int numPages;
  string hero;
public:
  Comic(...); // Comic ctor
  // other functions
};

This is okay, but it doesn’t capture relationships among Book, Text, and Comic. And how do we create an array (or other collection) with a mix of these?

We could:

  1. Use a union - *BAD (subverts the type system)**
union BookTypes{Book *b; Test *t; Comic *c;};
BookTypes myBooks[20];
  1. Array of void * BAD (pointer to anything)

Rather, observe that Text and Comic are kinds of Books - Books with extra features.

C++ - model with Inheritance

// Base class (superclass)
class Book {
  string title, author;
  int numPages;
public:
  Book(...);
  // ...
};

// derived classes (or subclasses)
class Text : public Book {
  string topic;
public:
  Text(...);
  // ...
};

class Comic : public Book {
  string hero;
public:
  Comic(...);
  // ...
};

Derived classes inherit fields and methods from the base class, so Text, Comic get title, author, numPages fields. Any method that can be invoked on Book can be called on Text and Comic.

Who can see these members?

  • title, author, numPages - private in Book; Text and Comic cannot see them, even subclasses can’t see them

How do we initialize Text? Need title, author, numPages (these are needed to initialize the Book part) and topic (specific to Text)

class Text : public Book {
  string topic;
public:
  Text(string title, string author, int numPages, string topic) :
  title{title}, author{author}, numPages{numPages}, topic{topic} {}
  // WRONG!!!
};

Wrong for 2 reasons:

  • title etc are not accessible to Text
  • Once again, when an object is constructed:
    1. space is allocated
    2. superclass part is constructed (NEW!)
    3. fields constructed
    4. constructor body runs

And in this case, superclass cannot be constructed because Book has no default constructor.

Fix: invoke Book’s constructor in Text’s MIL

class Text : public Book {
  string topic;
public:
  Text(string title, string author, int numPages, string topic):
  Book{title, author, numPages}, topic{topic} {}
};

NOTE: If a superclass has no default constructor, subclass must invoke a superclass constructor in its MIL. Good reasons to keep superclass’s fields inaccessible to subclasses. If you want to give subclasses access to certain members, use protected access:

class Book {
  protected:
    string title, author;
    int numPages; // accessible to Book and its subclasses
  public:
    Book(...);
    // ...
};

// subclasses
class Text: public Book {
  // ...
  public:
    // ...
    void addAuthor(string newAuthor) {
      author += newAuthor;
    }
};

Note: Not a good idea to give subclasses unlimited access to fields; Better - make fields private, but provide protected accessors

class Book {
  string author, title;
  int numPages;
protected:
  string getTitle() const;
  void setAuthor(string newAuthor);
public:
  Book(...); // ctor
  bool isItHeavy() const;
};

Relationship among Book, Text, and Comic is called “is a”: A Text is a Book; A Comic is a Book. UML: Text->(hollow)Book<-(hollow)Comic. Implement “is a” by public inheritance.

Now consider the method isItHeavy. When is a Book heavy?

  • For ordinary Books, > 200 pages
  • For Texts, > 500 pages
  • For Comics, > 30 pages
class Book {
  // ...
public:
  // ...
  bool isItHeavy() const {
    return numPages > 200;
  }
};

class Text {
  // ...
public:
  // ...
  bool isItHeavy() const {
    return numPages > 500;
  }
};

class Comic {
  // ...
public:
  // ...
  bool isItHeavy() const {
    return numPages > 30;
  }
};

// =====================
// client
Book b {"A small book", "1Q84", 50};
Comic c {"A big comic", "Waterloo Memers", 40, "Mr Paninos"};
cout << b.isItHeavy(); // false, it's a small Book as 50 < 200
cout << c.isItHeavy; // true, it's a big comic as 40 > 30

Since public inheritance means “is a”, we can do:

Book b = Comic{"A big comic", "Balkan Chevaps", 40, "We Deliver"};

Question: Is b heavy? b.isItHeavy() returns true or false? Which isItHeavy() run, Book::isItHeavy or Comic::isItHeavy?

Answer: No, it is not heavy. Book::isItHeavy is what runs. Why? Book contains 3 fields: title, author, numPages, while Comic contains 4 fields: title, author, numPages, and hero. Thus,

Book b = Comic {...};

tries to create a Comic object when there’s only space for a Book. Comic is then sliced (“hero” field is chopped off). Comic is coerced (forced) into a Book. Basically, Book b = Comic {…} converts a Comic into a Book and Book::isItHeavy runs.

When accessing objects through pointers, slicing is unnecessary and does not occur.

Comic c {"friend5ever", "Sedra Smith", 40, "RealisticAFMStudent"};
Book *pb = &c;
Comic *pc = &c;
cout << pc->isItHeavy(); // true; 40 > 30, heavy Comic
cout << pb->isItHeavy(); // false, 40 < 200, not heavy Book
// same behaviour as the slicing example, Book::isItHeavy runs as pointer is Book

Still, Book::isItHeavy runs when we access pb->isItHeavy(). Some objects behaves differently, depending on what type of pointer points to it.


June 16, 2016 - Lecture 14

Compiler uses the type of the pointer (or type of the reference) to decide which isItHeavy to run. It does not consider the actual type of the object. So a Comic is a Comic only if a comic pointer points to it. Pointer »> Actual object.

Then, how do you make Comic act like a Comic, even when pointed at by a Book pointer? Solution: declare the method virtual.

class Book {
  // ... fields
protected:
  int numPages;
public:
  Book(...);
  virtual bool isItHeavy() const; // use of virtual here
};

class Comic : public Book {
  // ...
public:
  bool isItHeavy() const override; // override keyword in virtual function
};

// =================
// client
Comic c {"RealisticMathStudent", "UWGo", 40, "Quest God"};
Book *pb = &c;
Book *rb = c;
Comic &pc = &c;
Book b = c;

cout << pb->isItHeavy(); // true, Comic::isItHeavy
cout << rb.isItHeavy(); // true, Comic::isItHeavy
cout << pc->isItHeavy(); // true, Comic::isItHeavy
cout << b.isItHeavy(); // FALSE, Book::isItHeavy

Virtual and Polymorphism

Virtual Methods: chosen based on the actual types of the object at runtime
Dynamic Dispatch: the process of virtual methods being resolved to the correct one at runtime is known as dynamic dispatch. It is the process of chossing which method to call at runtime based on the type of a value. We use this by putting virtual in the superclass.

E.g. My book collection

Book *myBooks[20];
for (int i = 0; i < 20; i++) {
  cout << myBooks[i]->isItHeavy << endl;
  // This uses Book::isItHeavy for Books, Text::isItHeavy for Texts
  // and Comic::isItHeavy for Comics
}

It accommodates multiple types under one abstraction -> Polymorphism

Note: This is why a function

void f(istream &in);

can be passed an ifstream, because ifstream is a subclass of istream.

DANGER

class One {
  int x, y;
public:
  One(int x = 0, int y = 0): x{x}, y{y} {}
};

class Two : public One {
  int z;
public:
  Two(int x = 0, int y = 0, int z = 0): One{x, y}, z{z} {}
};

void f(One *a) {
  a[0] = {6, 7};
  a[1] = {8, 9};
}

// ===============
// clientdas
Two myArray[] = [{1, 2, 3}, {4, 5, 6}];
f(myArray);

Data Misaligned: MyArray is originally [1 2 3][4, 5, 6]; after calling f, it becomes [6 7 8][9 5 6].

Note: NEVER use arrays of objects polymorphically. If you want polymorphism, use an array of pointers

Destructor Revisited

class X {
  int *x;
public:
  X(int n): x{new int[n]} {}
  ~X() {
    delete [] x;
  }
}

class Y : public X {
  int *y;
public:
  Y(int m, int n): X{n}, y{new int[m]} {}
  ~Y() {
    delete [] y;
  }
}

// =================
// client
X *myX = new Y{5, 10};
delete myX; // LEAKS!

Why? The last line calls ~X, not ~Y, so only x, but not y, is freed.
To ensure that deletion through a superclass pointer calls the subclass destructor, declare the destructor virtual.

class X {
  // ...
public:
  // ...
  virtual ~X();
};

ALWAYS make the destructor virtual in classes that are meant to have subclasses, even if the virtual destructor does nothing. If a class is NOT meant to have subclassses, declare the destructor final.

Pure Virtual Methods and Abstract Classes

class Student { // there are 2 kinds of Students, regular and co-op
protected:
  int numCourses;
public:
  // ...
  virtual int fees() const;
};

class Regular : public Student {
public:
  int fees() const override; // virtual - override
  // regular fees
};

class Coop : public Student {
public:
  int fees() const override; // virtual - override
  // coop fees
};

What do we put for Student::fees? We don’t know, because every Student should be either regular or co-op.

We can explicitly given Student::fees NO implementation -> pure virtual method

class Student {
  // ...
public:
  virtual int fees() const = 0; // =0, NO IMPLEMENTATION
  // Called pure virtual method = no implementation
};

A class with a pure virtual method cannot be instantiated, and the class is called an abstract class. Its purpose is to organize subclasses.

Subclasses of abstract classes are abstract as well, unless they implement ALL pure virtual methods. Non-abstract classes are called concrete classes.

UML: virtual and pure virtual methods: italics; abstract class: class name in italics; protected: #

Inheritance and Copy/Move

class Book {
  // ...
public:
  // Defines all copy/move operators here
};

class Text : public Book {
  // ...
public:
  // DOES NOT define copy/move operators
};

// ===============
// client
Text t {"Algorithms", "CLRS", 500, "CS"};
Text t2 = t; // No copy ctor in Text, what happens?
// calls Book's copy ctor,
// then goes field by field (i.e. default behaviour) for the Text part
// same for other opeartors

To write your own:

// copy ctor
Text::Text(const Text &other) : Book{other}, topic{other.topic} {}

// copy assignment opor
Text &Text::operator=(const Text &other) {
  Book::operator=(other); // superclass copy assignment
  topic = other.topic; // assign field
  return *this;
}

// move ctor
Text::Text(Text &&other): Book{std::move(other)}, topic{std::move(other.topic)} {

}

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

Note: Even though other “points” at an rvalue, other itself is an lvalue. std::move(x) forces lvalue x to be treated as an rvalue, so that move versions of operators can run


June 21, 2016 - Lecture 15

Text t1{...};
Text t2{...};
Book *pb1 = &t1;
Book *pb2 = &t2;

What if we do

*pb1 = *pb2; // ?

Then Book::operator= runs, partial assignment - copies only the Book part. How do we fix this? Try making operator= virtual.

class Book {
  // ...
public:
  // ...
  virtual Book &operator=(const Book &other); // make the copy assignment opor virtual
};

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

Note: different return types, but parameter types must be the same or it’s not an override, and thus WILL NOT COMPILE.

Thus assignment of a Book object to a Text variable would be allowed.

Text t {...};
Book b {...};
Text *pt = &t;
Book *pb = &b;
*pt = *pb; // uses a book to assign to a text, BAD

// ALSO
Comic c {...};
Comic *pc = &c;
*pt = *pc; // BAD

If operator= is non-virtual -> partial assignment through base class pointers -> BAD
If operator= is virtual -> compiler allows mixed assignment -> BAD

Recommendation: All superclasses should be abstract.

class AbstractBook {
  string title, author;
  int numPages;
protected:
  AbstractBook &opeartor=(const AbsratctBook &other);
  // prevents assignment through base class pointers from compiling
  // but implementation still available to subclasses
public:
  AbsratctBook(...);
  virtual ~AbsratctBook() = 0; // "be abstract"
  // need at least one pure virtual method to make it abstract
  // if you don't have any, make dtor pure virtual
};

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

// ============
// client
*pb1 = *pb2; // DOES NOT COMPILE

Prevents mixed & partial assignment.
Note: virtual destructor must always be implemented, even if it is pure virtual.

AbsratctBook::~AbstractBook() {}

Templates

Huge topic - just the highlights here

class List {
  struct Node;
  Node *theList;
  // ...
};

struct List::Node {
  int data;
  Node *next;
  // ...
};

Question: what if you want to store something else? Whole new class? Nah.

Templates: class parameterized by a type

template <typename T> class Stack {
  int size;
  int cap;
  T *data;
public:
  // ...
};

Stack(){...}
void push(T x){...}
T top(){...}
void pop(){...}

template <typename T> class List {
  struct Node {
    T data;
    Node *next;
  };
  Node *theList;
public:
  class Iterator {
    Node *p;
    explicit Iterator(Node *p): p{p} {}
  public:
    T &operator*() {
      return p->data;
    }
    // ...
  };

  T ith(int i) {
    // ...
  }

  void addToFront(T n) {
    // ...
  }
};

// ==================
// client
List <int> l1;
List <List<int>> t2;
t1.addToFront(3);
t2.addToFront(l1);

for (List<int>::Iterator it = l1.begin(); it != l1.end(); it++) {
  // ...
}

Compiler specializes template at the source code level, before compilation begins. Refer to /string/istream/ostream templates.

The Standard Template Library (STL)

Large number of useful templates

E.g. dynamic length arrays: vectors

#include <vector>
using namespace std;

vector<int> v {4, 5}; // vector<int> v(4,5) = {5,5,5,5};
v.emplace_back(6); // {4,5,6}
v.emplace_back(7); // {4,5,6,7}

Looping over vectors:

for (int i = 0; i < v.size(); i++) {
  cout << v[i] << endl;
}

// OR
for (vector<int>::iterator i = v.begin(); i != v.end(); i++) {
  cout << *i << endl;
}

// To iterate in reverse
for (vector<int>::reverse_iterator = v.rbegin(); it != v.end(); it++) {
  // ...
}

// To remove last element
v.pop_back();

// Use iterators to remove items from inside the vector
auto it = v.erase(v.begin()); // erase element 0
it = v.erase(v.begin() + 3); // erase element 3
// returns an iterator to first item after the erase

it = v.erase(it); // erase item pointed to by it
it = v.erase(v.end() - 1); // erase last item

v[i]; // i-th element of v; unchecked: out of bounds -> undefined behaviour
v.at(i); // checked version of v[i], what happens if i is out of bounds

Question: What should happen?

Problem: Vector can detect the error, but doesn’t know whatto do about it

C Solution: function returns a status code, or set the global variable errno; encourages programmers to ignore error checks

C++ Solution: when an error condition occurs, the function raises an exception


June 23, 2016 - Lecture 16

Exceptions

What happens? By default, execution stops. But we can write handler to catch exceptions and deal with them. vector ::at throws exception out_of_range.

#include <stdexcept>
// ...
try {
  cout << v.at(1000) << endl; // statements that may raise an exception
  // go in the try block
} catch (out_of_range) {
  cerr << "range error\n";  
}

Consider:

void f() {
  throw out_of_range {"f"}; // raise an exception
}

void g() {
  f();
}

void h() {
  g();
}

int main() {
  try {
    h();
  } catch (out_of_range) {
    // ...
  }
}

What happens?

main calls h, h calls g, g calls f, f throws, g has no handler for out_of_range, control goes back through the call chain (unwinds the stack) until a handler is found. Control goes all the way back to main, main handles the exception.

If no one handles the exception, program terminates.

What is out_of_range? It’s a class.

throw out_of_range {"f"}; // invokes a ctor with arg "f" and throws it
// "f" is auxiliary information

To examine auxiliary information:

try {
  // ...
} catch (out_of_range ex) {
  cout << ex.what() << endl; // prints "f"
}

A handler might do part of the recovery job - execute some corrective code and raise another exception:

try {
  // ...
} catch (someErrorType s) {
  // ...
  throw someOtherError(...);
}

Or throw the same exception:

try {
  // ...
} catch (someErrorType s) {
  // ...
  throw;
}

The difference between throw and throw s. Throw is used when an actual type of s is retained (most cases), it rethrows the same exception object it caught; throw s: s may be a subtype of someErrorType, throw rethrows a new exception of type someErrorType.

A handler can act as a catch-all:

try {
  // ...
} catch (...) { // catches all exceptions
  // ...
}

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

Define your own classes (or use appropriate existing ones) for errors. E.g.

class BadInput();

try {
  int n;
  if (!(cin >> n)) {
    throw BadInput{};
  }
} catch (BadInput &) { // catch by ref to prevent slicing
  cerr << // ...
}

Note:

class BaseExn{};
class DerivedExn : public BaseExn{};

void f() {
  DerivedExn d;
  BaseExn &b = d; // BaseExn type
  throw b;
}

try {
  // ...
  f();
  // ...
} catch (DerivedExn &) {
  // ... DerivedExn handler
} catch (BaseExn &) {
  // ... BaseExn handler
}

Which handler runs? BaseExn handler runs, as the type of the reference (i.e. the static type of the object) determines the handler.

Some standard exceptions:

  • length_error - attempting to resize strings/vectors that are too long
  • bad-alloc - new fails
  • ios::failure - I/O streams fail; refer to lectures/c++/exceptions

NEVER NEVER NEVER let a destructor throw an exception

  • If the dtor was executed during stack unwinding while dealing with another exception, you now have two active unhandled exceptions, and the program will terminate immediately

Design Patterns (Continued)

Guiding Principle:

  • Program with interfaces not implementations
  • Abstract base classes define the interface
  • Work with pointers to an abstract base class and call their methods
  • Concrete subclasses can be swapped in and out
  • Abstracting over a variety of behaviours
class List {
  // ...
public:
  class Iterator : public AbstractIterator {
    // ...
  };
};

class Set {
  // ...
public:
  class Iterator : public AbstractIterator {
    // ...
  };
};

class AbstractIterator {
public:
  virtual int &operator*() = 0;
  virtual AbstractIterator &operator++() = 0;
  virtual bool operator==(...) = 0;
  virtual ~AbstractIterator();
};

Then you can write code that operates over iteartors:

template <typename T>
void foreach(AbstractIterator start, AbstractIterator end, T f) {
  while (start != end) {
    f(*start); // f must be a callible entity
    ++start;
  }
}
// this works over both Lists and Sets

List l;
foreach(l.begin(), l.end(), someFunction);


June 28, 2016 - Lecture 17

Observer Design Pattern

aka publish-subscribe model

Publisher/Subject - source of data, generates data; Subscribers/Observers - receive data and react to it.

Sequence of the model calls:

  1. Subject’s state is updated()
  2. Subject::notifyObservers() -> calls each observer’s notify();
  3. Each observer calls ConcreteSubject::getState() to react accordingly

E.g. horse races; subject publishes winners, observers (individual betters) declare victory when their horse wins.

class Subject {
  vector <Observers *> observers;
public:
  void attach(Observer *ob) {
    observers.emplace_back(ob); // add to observers
  }

  void detach(Observer *ob) {
    // remove
  }

  void notifyObservers() {
    for (auto &ob; observers) {
      ob->notify();
    }
  }

  virtual ~Subject() = 0; // make class abstract
};

Subject::~Subject() {} // dtor must have user-defined implementation (since declared pure virtual)

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

class Horserace : public Subject {
  ifstream in; // get data from that file
  string winner;
public:
  Horserace(string source) : in{source};
  bool race(); // true if there was a race, false if EOF
  string getState() {
    return winner;
  }
}

class Bettor : public Observer {
  Horserace *subject;
  string name, myHorse;
public:
  Bettor(...) ... {
    subject->attach(this);
  }

  void notify() {
    string winner = subject->getState();
    cout << (winner == myHorse ? "Win" : "Lose") << endl;
  }
}

// main
Horserace hr;
Bettor Larry(hr, "Larry", "Pig4");

while (hr.race()) {
  hr.notifyObservers();
}

Simplifications:

  1. If only one type of subject, could merge Subject and ConcreteSubject
  2. If state is trivial (so that just let notify tells you all you need to know), then don’t need getState()
  3. If subject = observer (e.g. cell in a grid in a spreadsheet), could merge these classes

Decorator Pattern

  • Want to add features to an object at runtime

E.g. Operating System: basic window, then add menu, then add scrollbar, and we want to change these at runtime

class component - interface - operations

You will provide

ConcreteComponent - implements the interface

Decorators all inherit from Decorator, which inherits Component. Thus every Decorator is a Component and every Decorator has a Component

A window with a scrollbar is a window, and has a pointer to the underlying plain window. Windw with scrollbar and menu is a window and has a pointer to a pointer to a window with scrollbar, which has a pointer to a plain window


June 29, 2016 - Tutorial

protected: acts like private, but subclasses can access superclass fields; within the hierarchy

struct Computer {
  void makeCall() {
    cout << "Making call" << endl;
  }
  void test() {
    cout << "Testing" << endl;
  }
};

struct Smartphone : public Computer {
  void makeCall() {
    cout << "Mobile" << endl;
  }
};

void testCall(Computer& c) {
  c.test();
  c.makeCall();
}

int main() {
  Smartphone lmao;
  testCall(lmao);
  Computer *laptop = new Smartphone;
  laptop->makeCall();
  lmao.makeCall();
  lmao.test();
}


June 30, 2016 - Lecture 18

Midterm got curved: Original average 49%, avergae after adjustment 66%

Design Pattern: Template Method Pattern

We want subclasses to override superclass behaviour, but some aspects must stay the same

  • A design pattern where we override some behaviour from a superclass, but not all of it - the superclass is used as a template for the subclass

E.g. There are red and green turtles.

// superclass
class Turtle {
public:
  void draw() { // method to draw turtle and its components
    drawHead();
    drawShell();
    drawFeet();
    // note not virtual as the class is not abstract
    // thus not open for overriding
    // subclasses cannot change the fact that draw must
    // draw head, shell, and feet
  }

private:
  void drawHead(); // not virtual, cannot override
  void drawFeet(); // not virtual, cannot override
  virtual void drawShell() = 0; // pure virtual
  // enables subclasses to override this method
  // gives subclasses a little bit of control
  // but not total control
};

// subclass
class RedTurtle {
  void drawShell() override; // virtual - override
  // draw red shell
};

class GreenTurtle {
  void drawShell() override; // draw green shell
};

Class Turtle is like a boilerplate or a template, a fill-in-the-blank form. Has absolutely nothing to do with standard template library (STL). Subclasses cannot change the way a turtle is drawn, i.e. head, shell, feet, but they can change the way the shell is drawn.

Note: In the Turtle class, drawShell() is a private virtual function, but it is perfectly legal to override, not to call. Subclasses have to call their own drawShell().

Extension: The Non-Virtual Interface (NVI) Idiom

A public virtual method is really two things:

  • public: thus an interface to the client
    • indicates provided behaviour with pre/post conditions
  • virtual: thus an interace to subclasses
    • a “hook” to insert specialized behaviour

Hard to separate these ideas if they are tied to the same function

What if you later want to separate the customizable behaviour into 2 functions, maybe with some unchanging code in between? Without changing the public interface?

How can you make sure overriding functions respect pre/post conditions?

The NVI idiom says:

  • All public methods should be non-virtual
  • All virtual methods should be private, or at least, protected
  • Exception: Destructor

Example:

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

// In NVI:
// doPlay is a pass through function
class DigitalMedia {
public:
  void play() {
    // so we can control what happens here
    doPlay();
    // and here
    // and not gonna be any slower, because the compiler will optimize as it sees fit
  }
private:
  virtual void doPlay() = 0;
};

So now we can add before and after code.

E.g. Check copyright so I don’t get sued, update play count after the function call, or add another hook: showArt() = 0;

Extends Template Method - puts EVERY virtual function inside a template method.

STL - Maps = Dictionaries

E.g. “Arrays” that map string sto ints

#include <map>

std::map<string, int> m;
m["abc"] = 1;
m["def"] = 4;
cout << m["ghi"] << endl; // prints 0
// if key not present, it is inserted
// and value is default-constructed (for ints: 0)
cout << m["abc"] << endl; // prints 1

m.erase("abc");

if (m.count("def")) { // the number is either 0 or 1
  // 0 means not found, and 1 means found
}

Iterating over a map: sorted key order

for (auto &p : m) {
  cout << p.first << ' ' << p.second << endl;
  // first is key, second is value
  // p's type is std::pair<string, int>& (<utility>)
  // also, p.first and p.second are fields, not methods
  // not private fields?
  // Because no invariant, we can just expose the fields
}

Tools: Debugger GDB

To use: compile with -g (enable debugging information)

g++14 -g myfile.cc

To run the debugger:

gdb ./a.out

Commands:

  • r (run):
    • runs the program
    • if the program crashes, it tells you the error
  • bt (backtrace): prints the chain of functions that got you here
  • l (list): lists the source surrounding the current point of execution; gives you context
  • p (print): prints the value of a variable or expression
  • q (quit)

Not all bugs are segfaults though.

Breakpoints: tell gdb to stop the program so you can see what is going on.

break f

This says break when entering function f. Or,

break myfile.cc:15

This says break on line 15.

  • s (step): runs one line
  • c (continue): runs until the next breakpoint

Design Pattern: Visitor Pattern

For implementing double dispatch.

Virtual method - chosen based on the actual type (at runtime) of the receiving object.

What if we want to choose based on two objects?

UML: Turtle -> (hollow) Enemy <-(hollow) Bullet
Stick -> (hollow) Weapon <-(hollow) Rock

We want something like virtual void(Enemy, Weapon)::strike(); (not C++ though)

class Enemy {
  virtual void beStruckBy(Weapon &w);
};

class Weapon {
  virtual void strike(Enemy &e);
};

// each of these only does half the job

Trick to get dispatch on both:

  • Combine overriding with overloading

Override the virtual beStruckBy function:

class Enemy {
public:
  virtual void beStruckBy(Weapon &w) = 0; // pure virtual
};

class Turtle : public Enemy {
public:
  void beStruckBy(Weapon &w) override {
    w.strike(*this); // compiler knows *this is a Turtle
  }
};

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

Now overload strike that takes in both Turtle ref and a Bullet ref:

class Weapon {
public:
  virtual void strike(Turtle &t) = 0;
  virtual void strike(Bullet &b) = 0;
};

class Stick : public Weapon {
public:
  void strike(Turtle &t) {
    // strike a Turtle with a Stick
  }

  void strike(Bullet &b) {
    // strike a Bullet with a Stick
  }
};

class Rock : public Weapon {
public:
  void strike(Turtle &t) {
    // strike a Turtle with a Rock
  }

  void strike(Bullet &b) {
    // strike a Turtle with a Rock
  }
};

// ===================
// client
Enemy *e = new Bullet;
Weapon *w = new Rock;
e->beStruckBy(*w); // strike a Bullet with a Rock

beStruckBy is a virtual method, so Bullet::beStruckBy() runs. That calls Weapon::strike, and *this is bullet, so Bullet version gets chosen by compiler. The virtual method resolves to Rock::strike(Bullet &).


July 5, 2016 - Lecture 19

Recall: Visitor Pattern

class Enemy {
public:
  virtual void beStruckBy(Weapon &w) = 0;
  // ...
};

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

class Weapon {
public:
  virtual void strike(Turtle &t) = 0;
  virtual void strike(Bullet &b) = 0;
};

class Stick : public Weapon {
public:
  void strike(Turtle &t) override {
    // strike Turtle with Stick
  }

  void strike(Bullet &b) override {
    // strike Bullet with Stick
  }
}

Note: Visitor can be used to add functionality to existing classes without changing or recompiling the classes themselves.

E.g. Add a visitor to the Book hierarchy

class Book {
public:
  virtual void accept(BookVisitor &bv) {
    bv.visit(*this);
  }
};

class Text : public Book {
  // ...
public:
  void accept(BookVisitor &bv) override {
    bv.visit(*this);
  }
};

class Comic : public Book {
  // ...
public:
  void accept(BookVisitor &bv) override {
    bv.visit(*this);
  }
};

// BookVisitor

class BookVisitor {
public:
  virtual void visit(Book &b) = 0;
  virtual void visit(Text &t) = 0;
  virtual void visit(Comic &c) = 0;
}

In this example, accept is beStruckBy, visit is strike, Book is Enemy, and BookVisitor is Weapon.

Application: Track how many of each kind of book I have: Books (by author), Texts (by topic), and Comics (by hero). Use a map<string, int>.

Could add virtual void updateMap(…) to each class. Valid.

Or write a visitor:

class Catalogue : public BookVisitor {
  map<string, int> theCat;
public:
  map<string, int> getCatalogue() {
    return theCat;
  }
  void visit(Book &b) override {
    ++theCat[b.getAuthor()];
  }
  void visit(Text &t) override {
    ++theCat[t.getTopic()];
  }
  void visit(Comic &b) override {
    ++theCat[c.getHero()];
  }
}

// Won't compile

Won’t compile! Why?

Book includes BookVisitor -> includes Text -> includes Book

  • Circular include dependency
  • Book has an #include guard - won’t be included
  • Text doesn’t know what Book is
  • Are these includes really needed?

Compilation Dependencies

When does a compilantion dependency exist? (i.e. when do you need an include?)

Consider:

class A {
  // ...
};

class B : public {
  // ...
};

class C {
  // ...
  A myA;
};

class D {
  // ...
  A *myA;
};

class E {
  A f(A x);
};

IMPORTANT DISCUSSION: Which of them requires an include? Which of them can get away with a forward declaration?

Answer: B and C need an include (#include “a.h”), D and E do not. Compiler needs to know how big A is to know how big B and C is (B has an A inside it, C also has an A inside it).

For B and C, there is a compilation dependency. We need to know how big A is to know how big B and C are.

For D, you can forware declare (class A;), because all pointers are the same size. The compiler knows how big D is, it does not need to know how big A is.

For E, you can forward declare (class A;). Functions don’t contribute to the size of E. The function declaration is good enough for type checking. A is just mentioned for type checking.

If there is no compilation dependency necessitated by the code, then do not create one with extra #includes.

When class A changes, only A, B, C need to recompile.

Different story when you look at .cc implementation files. In the implementations of D and E:

d.cc

#include "a.h"

void D::g() {
  myA->someMethod();
  // need to know about class A here - a true compilation dependency
  // needs to include a.h here, but not in E's header.
}

Do the #include in the .cc, not in .h, where possible. Because including .h files in .cc, there would never be a cycle, because you never include .cc files. Reduces compilation cycle errors.

Now we will fix the visitor.

Now consider the XWindow class:

class XWindow {
  Display *d;
  Window w;
  int s;
  GC gc;
  unsigned long colours[10];

  // private data above
  // Yet we can look at it
  // Do we know what it all means? Nei.
  // Do we care? Nei.

public:
  //...
};

What if I add or change a private member? Then all clients would have to recompile. That’s cumbersome! Would be better to hide these details away.

Solution: pimpl idiom (pointer to implementation): create a second class XWindowImpl.

// XWindowImpl.h
#include <X11/Xlib.h>

struct XWindowImpl {
  Display *d;
  Window w;
  int s;
  GC gc;
  unsigned long colours[10];
};


// window.h
class XWindowImpl; // forward declare the Impl class

class XWindow {
  // No need to include Xlib or X11
  XWindowImpl *pImpl; // No compilation dependency on XWindowImpl.h
  // and clients also don't depend on XWindowImpl.h
public:
  // ... no change
};


// window.cc
#include "window.h"
#include "XWindowImpl.h"

XWindow::XWindow(...) : pImpl{new XWindowImpl} {
  // MIL: need to allocate space for the pointer
  // Also need to destroy pImpl in the dtor
  // Other methods: replace fields (d, w, s, etc.) with pImpl->d, pImpl->w, pImpl->s, etc.
}

Note: If you confine all private fields to XWindowImpl, then only window.cc needs to recompile if you change XWindow’s implementation.

Generalization: What if there are several possible window implementations? Say XWindows and YWindows. Then make Impl struct a class.

Window (solid diamond) (pointer)-> WindowImpl <- (hollow diamond) XWindowImpl, YWindowImpl

pImpl idiom with hierarchy of implementations

  • called the Bridge pattern


July 7, 2016 - Lecture 20

Measure of Design Quality

  • Coupling and cohesion
  • Coupling: The degree to which distinct program modules depend on each other
  • Low: Modules communicate via function clalls with basic params/results
    • Modules pass arrays/structs back and forth
    • Modules affect each other’s control flow
    • Modules share global data
  • High: modules have access to each other’s implementation (friends)
    • High: changes to one module require greater changes to other modules
    • Harder to reuse individual modules
  • Cohesion: how closely elements of a module are related to each other
    • Low
      • arbitrary grouping of unrelated elements (e.g. )
      • Elements share a common theme, otherwise unrelated
      • Perhaps share the sane base code (e.g. )
      • Elements manipulate state over the lifetime of an object (e.g. open/read/close a file)
      • Elements pass data to each other
    • High
      • Elements cooperate to perform exactly one task
      • Perfect cohesion: put every single function in its separate module

Low cohesion -> poorly organized code -> hard to understand and maintain

Goal: Low coupling, high cohesion

Decoupling the Interface (MVC)

Your primary program classes should not be printing things

E.g.

class Chessboard {
  // ...
  // there's a line of code like this
  cout << "Your move";
  // BAD DESIGN
  // inhibits code reuse
};

What if we want to reuse ChessBoard, but not have it communicate via stdout?

One solution: give the class stream objects, where it can perform input and output (I/O)

class Chessboard {
  istream &in;
  ostrema &out;
public:
  ChessBoard(istream &in, ostream &out) :
    in{in}, out{out} {}
  // and now we will have this code instead:
  out << "Your move";
};

What if we don’t want to use streams at all?

But ChessBoard shouldn’t be talking or doing any communication at all. Its job is to play chess.

Single-Responsiblity Principle

“A class should have only one reason to change”

In the above example, game state AND communication are TWO reasons to change.

Better solution: Communication with the ChessBoard via parameters and results, and occasionally via exceptions.

Confine user communication to outside the game class.

Question: Should main do all the communication, and then call ChessBoard methods?

Answer: NO. Hard to reuse if it’s in main. Should have a class to manage interaction that is separate from the game state class

Pattern - Model - View - Controller (MVC)

  • Separate the distinct notions of the data (or state), the presentation of the data, and the controll of the data.

Example: ChessBoard

  • Model: the main data you are manipulating (e.g. game state)
  • View: how the model is displayed to the user
  • Controller: how the model is manipulated

Model -> Controller <- View

Model:

  • Can have multiple views (e.g. text and graphics, or several graphics)
  • Doesn’t need to know about their details
  • Classic observer pattern (or could communicate through controller)

Controller:

  • Mediates control flow between the model and view
  • Might encapsulate turn-taking, or full game rules
  • May communicate with user for input (or this could be the view)

By decoupling presentation and control, MVC promotes reuse.

Exception Safety

Consider:

void f() {
  MyClass *p = new MyClass;
  MyClass mc;
  g();
  delete p;
}

No leaks. But what if g raises an exception?

What is guaranteed?

  • During stack unwinding, all stack-allocated data is cleaned up - dtors run, memory reclaimed
  • Heap-allocated memory is not freed

Therefore, if g throws, *p is leaked, mc is not.

Example Revisited

void f() {
  MyClass *p = new MyClass;
  MyClass mc;
  try {
    g();
  } catch (...) {
    delete p;
    throw;
  }
  delete p;
}

Tedious, error-prone, duplication code. How else can we guarantee that something (e.g. delete p) happens no matter f exits now or exits due to an exception?

In some languages, “finally” clauses (in Java) guarantee certain final actions. NOT IN C++.

The only thing you can count on in C++ is that destructors for stack-allocated data will run.

Thus, use stack-alocated data with dtors as much as possible. Use the guarantee to your advantage.

C++ Idiom: RAII - Resource Acquisition Is Initialization

Every resource should be wrapped in a stack-allocated object whose dtor destroys it.

E.g. Files

void h() {
  ifstream f("file"); // acquiring the resource, ("file")
  // initializing the object
  // ...
}

File is guaranteed to be closed when f is popped from the stack (f’s dtor runs).

The same can be done with dynamic memory.

class std::unique.ptr<T>; // takes a T* in ctor
// dtor will free the pointer
// In-between - can dereference just like a pointer

#include <memory>

Fix f():

void f() {
  auto p = std::make_unique<class>(); // allocate MyClass on the heap
  MyClass mc;
  g();
}

This will not leak and is also safer. Also shorter.


July 12, 2016 - Lecture 21

Recall:

void f() {
  MyClass *p = new MyClass;
  MyClass mc;
  g(); // a function that may throw
  delete p; // might leak
}

To fix using RAII with unique pointer:

void f() {
  auto p = make_unique<MyClass>();
  // type is std::unique_ptr<MyClass>
  g(); // might throw
  // won't leak as stack destructor is called
}

Difficulty:

class C {
  //...
};

unique_ptr<C> p {new C {...}};
unique_ptr<C> q = p;

What happens when a unique pointer is copied?

We don’t want to delete the same pointer twice! Segmentation fault.

Instead - copying is disabled for unique_ptrs.

So the truth is: The code above WILL NOT COMPILE. Unique_ptrs can only be moved, not copied.

We can write our own unique_ptr:

template<typename T> class unique_ptr {
  T *ptr;
public:
  unique_ptr(T *p): ptr{p} {} // ctor
  ~unique_ptr() { // dtor
    delete ptr;
  }

  unique_ptr(const unique_ptr<T> &other) = delete;
  // disable copy ctor

  unique_ptr<T>&operator=(const unique_ptr<T> &other) = delete;
  // disable copy assignment

  // but move ctor and assignment should be implemented
  // just like how it is usually done
  // as they don't affect the uniqueness

  // move ctor
  unique_ptr(unique_ptr<T> &&other): ptr{other.ptr} {
    other.ptr = nullptr; // free other's data
  }

  // move assignment opor
  unique_ptr<T>&opeartor=(unique_ptr<T> &&other) {
    using std::swap;
    swap(ptr, other.ptr);
    return *this;
  }

  // dereference operator
  T &operator*() {
    return *ptr;
  }

  // operator arrow
  T *operator->() {
    return ptr;
  }
};

If you want to be able to copy pointers, use std::shared_ptr

void h() {
  auto p1 = make_shared<MyClass>();
  if (...) {
    auto p2 = p1;
  } // p2 popped, pointer is NOT deleted
} // p1 popped, pointer IS deleted

What is this magic? Shared pointers maintain a reference count (keep track among themselves the number of pointers pointing to the same object; reference count is a count of all shared_ptrs pointing at the same object). If the pointer realizes that itself is the only pointer pointing to an object, it will delete. i.e. Memory is freed when the last shared_ptr pointing at that object is freed.

Therefore, use shared_ptrs and unique_ptrs instead of raw pointers as much as possible! They solve the garbage collection problem. This means dramatically fewer opporitunities for leaks.

3 levels of exception safety for a function f:

  1. Basic guarantee - if an exception occurs, the program will be in a valid state
    • nothing is leaked, class invariants maintained
  2. Strong guarantee - if an exception is raised while executing f, the state of the program will be as if f had not been run
  3. No-throw guarantee - f will never throw or propagate an exception, because f will always succeed (it will always accomplish its task)

Example:

class A {...};
class B {...};

class C {
  A a;
  B b;
  void f() {
    a.method1(); // may throw - strong guarantee
    b.method2(); // may throw - strong guarantee
  }
};

Is the function f in class C (C::f) exception safe?

  • If a.method1() throws - nothing has happened (OK) (f does propagate method1’s exception)
  • If b.method2() throws - effects of method1 must be undone to offer the strong performance
    • Very hard or even imposible (what if method1 modified a global variable? Printed something to the screen? Launched a rocket?)
    • Hard to undo method1 if method1 has non-local side-effects

Therefore, C::f is NOT exceotion safe.

But can we make it exception safe? That will require us to make an assumption: These methods do not have non-local side-effects.

If A::method1, B::method2 do not have non-local side effects, we can use copy and swap:

class C {
  // ...
  void f() {
    // make temporary copies of a and b
    A aTemp = a;
    B bTemp = b;

    // operate on copies
    aTemp.method1(); // If these methods throw, what happens to the overall picture?
    bTemp.method2(); // a and b will still be intact

    a = aTemp; // assign back
    b = bTemp;
    // But what if copy assignment throws?
  }
}

Better if the swap was nothrow. Assigning/Copying/Moving/Swapping pointers will never and cannot throw!

So we can rephrase the code above, using the PImpl idiom.

struct CImpl {
  A a;
  B b;
};

class C {
  unique_ptr<CImpl> pImpl;
  void f() {
    auto temp = make_unique<CImpl>(*pImpl); // construct unique_ptr
    temp->a.method1(); // if it throws, original object still intact
    temp->b.method2(); // if it throws, original object still intact

    std::swap(temp, pImpl); // no throw, guaranteed
    // same if you use move assignment, in the case of using an unique_ptr
  }
};

If either A::method1 or B::method2 offers no exception safety guarantee, then neither can f. It is impossible to construct a safe function out of unsafe pieces.

Exception Safety and the STL: Vectors

How does exception safety apply to the most used thing in STL, vectors?
Vectors:

  • encapsulate a heap-allocated array
  • Follows RAII - When a stack-allocated vector goes out of scope, the internal heap-allocated memory is freed

Example:

void f() {
  vector<MyClass> v;
  // ...
  // At the end of the function, v goes out of scope
  // array is freed, MyClass dtor runs on all objects in the array
}

void g() {
  vector<MyClass *> v; // what if we have a vector of pointers?
  // ...
  // Array is freed, pointers don't have dtors
  // so any objects pointed at by pointers in v are NOT deleted
  // v doesn't know whether the pointers in the array own the objects they point at
  // e.g. ducks and pond analogy

  // note it's not hard to delete
  for (auto &x : v) {
    delete x;
  }
}

But we don’t want to do cleanup ourselves! Solution: use shared_ptrs!

void h() {
  vector<shared_ptr<MyClass>> v;
  // ...
  // array is freed, shared_ptr dtors run,
  // so objects are deleted if no other shared_ptr points at them
  // don't have to do any explicit deallocation
}

Another topic: emplace_back

  • Offers the strong guarantee
    • If the array is full (i.e. size == cap),
      • allocate new array
      • copy the objects over (copy construction using copy ctor)
        • If a copy ctor throws, destroy the new array, old array is still intact, thus we can offer strong guarantee
      • delete old array
    • But copying an array is expensive and the old data will be thrown away! What a waste!
    • Why don’t we move instead of copy?
      • allocate new array
      • move objects over (move ctor)
        • BUT! If move ctor throws, can’t offer strong guarantee, since the original is no longer intact
      • delete old array
    • Therefore, if objects have a no-throw move, emplace_back will use move, else it will use copy (which is slower)
    • So your move ops should be no-throw if possible

Example: Add keyword noexcept to tell vector that your move operators are no-throw

class MyClass {
public:
  MyClass(MyClass &&other) noexcept {
    // ...
  }

  MyClass&operator=(MyClass &&other) noexcept {
    // ...
  }
};

This is the end of the exception safety topic.


July 14, 2016 - Lecture 22

Recall: emplace_back uses move ctor and assignment operator if they are no-throw, copy ctor if it throws. So make your move ctors and assignment operators no-throw if possible.

class MyClass {
public:
  MyClass(MyClass &&other) noexcept {
    //...
    // use the "noexcept" keyword to indicate no-throw
  }

  MyClass &operator=(MyClass &&other) noexcept {
    //...
  }
};

At minimum: Moves and swaps should be noexcept (no-throw)

Casting

Some C code!

Node n;
int *ip = (int*) &n; // cast
// cast forces C++ to treat a Node* as an int*

Casting: Forcing an object to be treated as another type. C-style casts should be avoided in C++.

Advantages of C++ casts:

  1. C++ casts are easier to search and spot (C casts are hard to locate)
  2. Different categories of casts make code more readable (explicit); Also different casts have different intended usages
  3. Compiler would give warnings if you are doing something dumb (provides compiler and runtime errors, expose issues)

If you must cast, use a C++ cast. There are 4 kinds of casting:

  1. static_cast - “sensible casts”
  2. reinterpret_cast
  3. const_cast
  4. dynamic_cast

static_cast - relatively safe, sensible

E.g. static_cast: double->int

void f(double x);
void f(int x);

double d = 3.0;
f(d); // the first one runs

// now what if we want to run the second one?
f(static_cast<int>(d)); // cast the double to int

Superclass pointer -> subclass pointer

Book *b = new Text {...};
Text *t = static_cast<Text*>(b);

You are taking responsibility that b actually points at a Text.

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

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

It’s like making a bet. The only guaranteed thing: when you try to revert back to the old object, it will succeed.

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

void g(int *p); // g doesn't promise not the change *p
// but suppose g doesn't actually change *p (assumption)

void f(const int *p) { // f promises not to change *p
  // ...
  g(p); // WRONG
  g(const_cast<int*>p); // CORRECT
  // casting the constness away
}

dynamic_cast - Is it safe to convert a Book* to a Text*?

Book *pb = ...; // don't know the right side
static_cast<Text*>(*pb)->getTopic(); // safe?

Is it safe?

Depends on what pb actually points at. Better to do a tentative cast, try it and see if it succeeds.

Use dynamic_cast:

Book *pb = ...;
Text *pt = dynamic_cast<Text*>(pb);

If the cast works(i.e. pb points at a Text or a subclass of Text), then pt points at the object. If the cast fails, pt will be a nullptr. So we can check if the cast is successful by:

Book *pb = ...;
Text *pt = dynamic_cast<Text*>(pb);

if (pt) {
  cout << pt->getTopic();
} else {
  cout << "Not a Text";
}

static_cast is always faster. Sometimes static_cast costs very little, while using dynamic_cast costs a lot more during runtime.

But all of the above operates on raw pointers. We talked about smart pointers last class, should we use casts on smart pointers? Raw pointers are more integrated into the C++ type system. But the type system doesn’t know the relationship between a shared_ptr to Book and a shared_ptr to Text (these are our own classes). But smart pointers classes have their own versions.

The following cast shared_ptrs to shared_ptrs:

static_pointer_cast
const_pointer_cast
dynamic_pointer_cast

We can use dynamic casting to make decisions at runtime based on an object’s run-time type (RTTI = runtime type information)

void whatIsIt(shared_ptr<Book> b) {
  if (dynamic_pointer_cast<Text>(b)) {
    cout << "Text";
  } else if (dynamic_pointer_cast<Comic>(b)) {
    cout << "Comic";
  } else {
    cout << "Book";
  }
}

Note: dynamic casting isn’t available for everybody. It only works on classes with at least one virtual method. A superclass should always have a virtual destructor (thus a virtual method), and as dynamic casting requires to know the entire class hierarchy, it only works on classes with a virtual method.

Note: Code like this is highly coupled to the Book class hierarchy and may indicated bad design. If I invent a new class (a subclass of Book), I have to update whatIsIt. So if whenever I add a subclass to an already existing class, I need to have knowledge of its implementation, that’s bad design.

Better 1 - write a virtual method, so when we add a new subclass of Book (say, CookBook), and override the whatIsIt method.

Better 2 - if the new subclass is a rare exception (i.e. not universally applicable), write a Visitor pattern. But visitor requries knowledge of the full implementation as well.

virtual void visit(Book &b) = 0;
virtual void visit(Text &t) = 0;
virtual void visit(Comic &c) = 0;

// say if we want to add CookBook, we need to add this
virtual void visit(CookBook &cb) = 0;

So visitor is still tightly coupled, but it’s a little bit better than dynamic casting.

Dynamic casting also works on references.

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

If b “points to” a Text, then t2 is a reference to the same Text. If not, (no such thing as a null reference) raises exception bad_cast.

With dynamic reference casting, we can solve the polymorphic assignment problem (think back: a week after we introduced inheritance: what happens to the Big 5 when we have inheritance?)

*pb1 = *pb2; // when we don't have virtual methods
// we never wrote an assignment operator

Now we can write an assignment operator that takes in any Book and assign it to a Text:

Text &Text::opeartor=(const Book &other) { // virtual
  Text *textOther = dynamic_cast<Text &>(other);
  if (this == &textOther) { // check for self-assignment
    return *this;
  }
  Book::operator=(other);
  topic = other.topic;
  return *this;
}

How do I assign Text to any Book - solved.

What if other isn’t a Text? Exception bad_cast raised, the opeartion doens’t happen, the function goes back to the caller, and the caller deals with the inappropriate use.

How Virtual Methods Work

class Vec {
  int x, y;
public:
  int doSomething() {
    // ...
  }
};

class Vec2 {
  int x, y;
public:
  virtual int doSomething() {
    // ...
  }
};

The two classes are virtually the same (pun intended), the only difference is the word “virtual”. What’s the actual difference?

Vec v {1, 2};
Vec2 w {1, 2};
// Do they look the same in memory?
cout << sizeof(v) << " " << sizeof(w);
// prints
// 8 16
// v has size 8
// w has size 16

Not quite the same.


July 19, 2016 - Lecture 23

Book *pb = new {Book Text Comic};
pb->isItHeavy();

The choice of which version to run is based on the type of the actual object - not known until runtime

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

The virtual table (vtable) is a lookup table of functions used to resolve functions in a dynamic/late binding manner. The table is a static array that the compiler sets up at compile time. It contains one entry for each virtual function that can be called by objects of the class. Each entry is a function pointer that points to the most-derived function accessible by that class.

How it works:

  1. Every class that uses virtual functions (or is derived from a class that has virtual functions) is given its own vtable
  2. The compiler adds a hidden pointer to the base class, which is the vptr
class C {
  int x, y;
  virtual void f();
  virtual void g();
  void h();
  virtual ~C();
};

// ======
C c;

The vtable would have f, g, and ~C pointing out to other functions outside the vtable

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

C has x, y, and a vptr -> vtable (“C”, f, g, ~C)

E.g.

Book b;
Text t;

b has title, author, numPages, vptr (points to the vtable of Book, which contains isItHeavy pointer, which in turn points to the actual implementation of Book::isItHeavy)
t has title, author, numPages, topic, vptr (points to the vtable of Text, which contains isItHeavy pointer, which in turn points to the actual implementation of Text::isItHeavy)

Calling a virtual method (all happens at runtime):

  • follow pointer to the vtable
  • fetch pointer to actual method from table
  • follow the function pointer and call the function

Therefore, virtual function calls incur a small overhead cost.

Why isn’t destructor virtual by default? Classes not meant to be subclassed should not have virtual

C++: If you don’t need it, you don’t pay for it. Unless you actually need the functionality of virtual, it won’t give it to you.

Also: declaring at least one virtual function adds a vptr to the object. Therefore, classes with no virtual functions produce smaller objects (lower cost) than if some functions were virtual

Question: Why does dynamic casting (dynamic_cast) only work on classes with at least one virtual function? dynamic_cast needs to know what objects we actually have, and the compiler needs the vtable to figure out the type

A class that declares or inherits a virtual function is called a polymorphic class.

Concretely, how is an object laid out? It’s compiler-dependent.

g++:

A table of fields under vptr

class A {
  int a, c;
  virtual int f();
};

class B : public A {
  int b, d;
};

For A, the layout would be vptr (a, c), and for B, vptr (a, c, b, d). Vptr is on the top of the table. A B object is an A object. So you will want your B object to look like an A object AND a B object simultaneously. So a pointer to B looks like a pointer to A, if you ignore the last two fields. We will always know where vptr is (first).

Multiple Inheritance

A class can inherit from more than one class.

E.g.

class A {
  int a;
};

class B {
  int b;
};

class C : public A, public B {
  void f() {
    cout << a << ' ' << b;
    // inherit a from A, b from B
  }
};

UML:
A <- (hollow) C (hollow) -> B

Challenges:

Suppose B inherits from A. And C inherits from A.

class D : public B, public C {
public:
  int d;
};

// ============== main
D dObj;
cout << dObj.a << endl;

Compiler error: which a do you mean? You have one from virtually inheriting from B, or the one from C? “Request for ‘a’ is ambiguous”.

Need to specify:

dObj.B::a; // OR
dObj.C::a;

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

  • Should B::a and C::a be the same or different?
  • Default behaviour: two

What if we want “The Deadly Diamond”? A on the top, B and C on left and right, and D inherit from both B and C. Make A a virtual base class, employ virtual inheritance.

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

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

E.g. I/O stream hierarchy

ios_base | ios | istream (virtual inheritance) ———– | istringstream iostream (inherit from istream, ostream) —fstream, stringstream | ifstream | ostream (virtual inheritance) ———– | ostringstream | ofstream

How will this be laid out?

What does g++ do?

Multiple inheritance: initialization of the virtual base class is the responsiblity of the bottom of the class hierarchy.

Diagaram doesn’t look like all of A, B, C, D simultaneously, but slices of it do look like A, B, C, D.

Therefore pointer assignment among A, B, C, D changes the address stored in the pointer.

D *d;
A *a = d; // changes the address

static_cast, const_cast, dynamic_cast under multiple inheritance will also change the value of the pointer. BUT reinterpret_cast WILL NOT. That’s why reinterpret_cast is dangerous.

Template Functions

template<typename T> T min(T x, T y) {
  return x < y ? x : y;
}

int f() {
  int x = 1, y = 2;
  int z = min(x, y); // T is int, the compiler figures it out
}

Note: Don’t need to say min, just min is fine. C++ can infer T=int from the types of x and y. This applies to function templates only.


July 20, 2016 - Tutorial

Smart pointers are good for exception safety because they manage memory automatically, so we can avoid memory leaks when a function throws.

Exception Safety

3 Guarantees: Basic, Strong

  • Basic Guarantee: “a valid state” -> the object after the exception throws will still be valid, but with some unknown effects
  • Strong Guarantee: The state that used to be it; Undone
  • No-throw Guarantee: Will not throw an exception; difficult to get. Almost never happens unless with primitive types
try {
  o.f();
} catch(...) {
  o.g();
}
  • Basic - o is a valid object, but it might have changed after f(). The program will not crash, and you can still use o (invariants of the object are preserved and no resources are leaked)
  • Strong - it’s like you never called o.f(); “all-or-nothing”. As if the try catch block and o.f() didn’t happen

Casting

  • dynamic_cast: RTTI = Runtime type information. dynamic_cast checks if it makes sense to convert from one type to another. Only casts when the cast makes sense
A *a = new B;
  • static_cast: taking control from compiler; C-style casting; sensible
  • reinterpret_cast: here’s a piece of memory, reinterpret it to a different type. Destroying C++ built-in checks and type information. Used in system engineering
  • const_cast: const in read-only memory; if someone by mistake, forgot the const keyword; prevent the non-constness from propagating through multiple functions
operator<<(ostream &out, Student s) {
  out << s.grade();
  // not modifying s, so should be const
}

void prettyprint(const Student &s) {
  cout << "Grade: " << s.grade();
  // incompatible with <<
  // so you would const_cast s, to cast away the constness
  cout << "Grade: " << const_cast<Student &>s;
}

STL

for_each(iterator, iterator, function);
// begin, end, apply the function
// acts exactly like map


July 21, 2016 - Lecture 24

Template Fuctions

Recall:

template<typename T> T max(T x, T y) {
  return x < y ? y : x;
}

int f() {
  int x = 1, y = 2;
  int z = max(x, y); // T = int, note that we didn't need to say min<int>
  // ...
}

C++ can figure out T = int from the types of x and y, This applies to function templates only.

char w = max('a', 'c'); // T = char
auto f = max(1.0, 3.0); // T = float

For what types T can min be used? (Or, for what types T would be body compile?)

  • Any type for which operator < is defined

Recall:

void for_each(AbsratctIterator start, AbsratctIterator finish, int(*f)(int)) {
  while (start != finish) {
    f(*start); // apply function
    ++start; // update
  }
}

How does it work? It works as long as AbstractIterator supports !=, *, and ++.

f can be called as a function. Make these template arguments to make it more generalized.

New implementation:

template<typename Iter, typename Func>
void for_each(Iter start, Iter finish, Func f) {
  while (start != finish) {
    f(*start);
    ++start;
  }
}

Now Iter can be any type that supports !=, *, ++. Pointers are a type that supports these operations, yet they are not Iterators. So Iter can also be a pointer.

void f(int n) {
  cout << n << endl;
}

int a[] = {1, 2, 3, 4, 5};
for_each(a, a+5, f); // Now we can do this, this prints the array

Difference between the two implementations:

The first one requires start and finish be of AbstractIterator type, while the second one generalizes it and only requires the type to support these operations.

C++ STL Library

  • A suite of template functions, many of which work over iterators

Examples: for_each (as given above, with templates)

find: returns iterator to the first item in range [first, last) matching val, or last if val if not found

template<typename Iter, typename T>

Iter find(Iter first, Iter last, const T&val);

count: like find, but returns number of occurrences of val

template<typename Iter, typename T>

Iter count(Iter first, Iter last, const T&val);

copy: copies one container range [first, last) to another, starting at result

Note: It does not allocate memory

template<typename InIter, typename OutIter>

OutIter copy(InIter first, InIter last, OutIter result);

// ============= client
vector<int> 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}

transform: generalized copy; does not allocate memory like copy

template<typename InIter, typename OutIter, typename Func>

OutIter transform(InIter first, InIter last, OutIter result, Func f) {
  while (first != last) {
    *result = f(*first); // transforming first
    // when f is the identify function, this is just copy
    ++result;
    ++first;
  }
}

Example of transform:

int add1(int n) {
  return n + 1;
}

vector<int> 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?

  1. What can we use for Func?
  2. What can we use for InIter and OutIter?

First question: What type of thing is Func allowed to be? How is f used?

f is used like f(*first). Whatever f is, I have to be able to call it like a function. f can be anything that can be called as a function.

Can write operator() (member function, function call operator) for objects that allows you to give the object the ability to be called as a function.

class Plus1 {
public:
  int operator()(int n) {
    return n + 1;
  }
}

// how to use:
Plus1 p; // initialize a Plus1 object
p(4); // p can be called as if it were a function; produces 5
// Same as
p.operator()(4);

// SO we can write transform as:
transform(v.begin(), v.end(), w.begin(), Plus1{});
// needs to create a Plus1 object, thus use {} for constructor call
// Plus1 p will work as well

Generalize:

class Plus {
  int m;
public:
  Plus(int m) : m{m} {}
  int operator()(int n) {
    return n + m;
  }
};

// client
transform(v.begin(), v.end(), w.begin(), Plus{1});
// same as
transform(v.begin(), v.end(), w.begin(), add1);
// but we can change the value of the number added, good generalization

Instances of Plus1, Plus are called function objects or functors.

Advantage of function objects:

  • Can maintain state, unlike functions
class IncreasingPlus {
  int m = 0;
public:
  int operator()(int n) {
    return n + (m++);
  }

  void reset() {
    m = 0;
  }
};

// client
vector<int> v (5, 0); // {0, 0, 0, 0, 0}
vector<int> w (v.size());
transform(v.begin(), v.end(), w.begin(), IncreasingPlus{});
// w = {0, 1, 2, 3, 4}
// if you want to reverse the order to get 4, 3, 2, 1, 0, write
transform(v.begin(), v.end(), w.rbegin(), IncreasingPlus{});
// rbegin returns a reverse iterator, it iterates backwards
// ++ moves it toward the beginning of the container

Consider: how many ints in a vector v are even?

vector<int> v {...};
bool even (int n) {
  return n & 2 == 0;
}

int x = count_if(v.begin(), v.end(), even);

Seems a waste to explicitly create the function even. If this were Racket, we would use lambda for anonymous functions. We can do the same here:

int x = count_if(v.begin(), v.end(), [](int n) {return n % 2 == 0;}); // [] capture list

auto x = [](int n) {
  return n % 2 == 0;
};  // use auto to capture the type, since the type is a secret

// "x's type declared type, whatever it is"
decltype(x);

// typeof is a totally different thing; run-time only

Second question: Iterator abstraction: apply the notion iteration to other sources/destinations of data, for example, streams

You will need to include header . Example:

#include <iterator>

vector<int> v {1, 2, 3, 4, 5};
ostream_iterator out { cout, ", " }; // "," is delimiter string
copy(v.begin(), v.end(), out); // prints 1, 2, 3, 4, 5, (space at the end)
// prints it to cout (the screen)

Another example:

vector<int> v {1, 2, 3, 4, 5};
vector<int> w;
copy(v.begin(), v.end(), w.begin()); // WRONG!
// Wrong because copy doesn't allocate any space, and w doesn't have any space allocated to it
// SEGFAULT

Why can’t copy allocate space? copy doesn’t know what w is. Didn’t give copy w itself (instead, an iterator w.begin()). If copy doesn’t know what the data structure w has, it cannot call memory allocation function on it. It literally cannot allocate space. Copy doesn’t even know that w is a vector - it only has an iterator to an item in w.

So if copy cannot automatically allocate space, how can we get around that?

What if we had an iterator whose operator= inserts a new item?

copy(v.begin(), v.end(), back_inserter(w));
// back_inserter creates iterators
// adds v to the end of w, allocateing space


August 4, 2016 - Final Exam Review

Summaries of All Lectures

Lecture 1 (May 3)

  • Introduction, grading, assignment 0, Piazza
  • Options for working in Linux: install Linux, VM, ssh via Putty, XMing for XWindows
  • Linux shell (bash)
  • Command line vs. GUI, very briefly
  • Point out Linux command handout
  • cat, ls, hidden files, pwd
  • Ctrl-C and Ctrl-D
  • Output and input redirection
  • Difference between redirecting input and filename as argument (demonstrate with wc)
  • Wildcards and globbing.
  • Pattern *
  • Semantics of globbing (substitution performed by shell before arguments are passed to program)
  • stdin, stdout, stderr; differences between stdout and stderr
  • How to redirect stderr
  • Pipes

Lecture 2 (May 5)

  • Pipes continued
  • echo
  • $(…) notation
  • Regular expressions and egrep
  • Patterns: , [..], ?, *, ., ^, $
  • Some examples
  • Permissions: explain rwx for user, group, other, for files and directories
  • chmod command

Lecture 3 (May 10)

  • Shell scripts
  • Shell variables, ${} notation
  • Global variable PATH
  • Quotation: single vs. double
  • Shell if-statements, while loops, for loops

Lecture 4 (May 12)

  • Bash procedures
  • Testing
  • Intro to C++: Hello world
  • cin, cout, cerr, operator«, operator»
  • cin.fail() and cin.eof()

Lecture 5 (May 17)

  • Implicit conversion of streams to bool
  • Returning the stream from operator» and operator«; cascading input and output
  • cin.clear() and cin.ignore()
  • Filestreams and stringstreams
  • Strings: contrast with C strings, string operations
  • Default parameters

Lecture 6 (May 19)

  • Overloading
  • Structs and nullptr
  • Pass-by-value
  • References
  • Pass-by-reference and pass-by-const-reference
  • Dynamic memory: new and delete
  • Stack and heap
  • Returning by value, returning references/pointers
  • Begin operator overloading: + and * for a vector class

Lecture 7 (May 24)

  • Operator overloading: operator» and operator«
  • Preprocessor: include, convention for C headers, define, defining constants, if, ifdef, ifndef
  • Applications: conditional compilation for multi-platform development, debugging output, if 0 for commenting
  • Defining constants on the g++ command line
  • Separate compilation: .h and .cc files, extern for global variables, #include guards

Lecture 8 (May 26)

  • Put all header files in include guards and must never put a global using namespace std; in header files
  • Introduction to classes
  • Terminology: class, object, member function, method
  • Semantics of method call wrt this pointer
  • Introduce constructors
  • Uniform initialization syntax explained
  • Built-in default ctor, C-style initialization semantics lost when you define a ctor
  • Initialization list
  • Introduce copy constructor (replicate default behaviour)

Lecture 9 (May 31)

  • Finish copy constructor (deep copy a linked list)
  • Explicit constructors
  • Destructors
  • operator= : cascading assignment in C, checking for self-assignment, straightforward implementation
  • copy-and-swap idiom
  • Introduction to rvalues: the desire to move, rather than copy, when initializing/assigning from temporary objects.

Lecture 10 (June 2)

  • Rvalue references, move constructor, move assignment operator
  • Copy/move elision
  • Rule of 5
  • Member operators
  • Arrays of objects
  • Separate compilation for classes
  • Const objects/methods, mutable fields

Lecture 11 (June 7)

  • Static fields and methods
  • Invariants and encapsulation - public and private; fields should be private
  • switch from struct to class, and explain the difference
  • Fix linked list class to prevent “next” pointers in nodes from pointing at the stack
  • Nested classes (public and private)
  • Intro to design patterns
  • Iterator pattern applied to linked list class
  • Automatic type deduction
  • Range-based for loops

Lecture 12 (June 9)

  • Friend classes; advice to minimize friendships
  • Encapsulation: get/set methods
  • Friend functions, operator« as friend function
  • Makefiles–basic makefile, using variables, automatic build rules, -MMD, including the .d files
  • UML for standalone classes; + and - visibility
  • Composition of objects: calling field ctors in initialization list (req’d if field objects don’t have default ctors)
  • “Owns-a” relationship, modelling in UML (solid diamond)

Lecture 13 (June 14)

  • Aggregation, ptr fields, “has-a” relationship (open diamond)
  • Multiplicities
  • Inheritance (public): motivation, first example, basic semantics.
  • Visibility under inheritance - subclass can’t see superclass private members; also means subclass can’t initialize superclass fields; calling superclass ctor in init list
  • protected visibility - advice to keep fields private, provide protected accessors if subclasses need privileged access
  • “Is-a” relationship in UML.
  • Overriding methods in subclass (non-virtual)
  • Superclass object initializable with subclass object. What happens? Superclass version of methods runs. Why? Slicing means that you only have the superclass part of the object
  • Same exercise through pointers. Method call resolves the same way, though this time it’s not a technical necessity

Lecture 14 (June 16)

  • Virtual methods, example; define their behaviour
  • Polymorphism and code that utilizes polymorphism (calling a polymorphic method over an array of ptr to base objects)
  • Advice against treating arrays polymorphically
  • Virtual destructor
  • Pure virtual methods and abstract classes
  • UML for protected, static, virtual, abstract
  • Inheritance and copy/move construction/assignment: calling to superclass version
  • std::move

Lecture 15 (June 21)

  • Inheritance and copy/move construction/assignment: assigning through base class pointers is partial assignment (subclass part not copied); if you make operator= virtual, you get full assignment, but must support assignment with right-hand sides from the full inheritance hierarchy
  • Conclusion: make superclasses abstract, with a protected operator=
  • Pure virtual dtor for when you have nothing else to make pure virtual; must be implemented even though it’s pure virtual
  • Templates (just the basics)
  • STL: vectors, iterators (forward and reverse), vector methods (push_back, pop_back, operator[], size, erase)
  • C-style error-handling and why it’s bad

Lecture 16 (June 23, Midterm today)

  • Introduction to exceptions
  • Example of catching out_of_range
  • Example of writing a function that throws an exception and stack unwinding (callchain.cc)
  • What is out_of_range – a class; ctor takes a string, access to the string via .what()
  • Catching an exception and throwing another one
  • Rethrowing the same exception: throw; vs. throw s;
  • Catch-all exception handlers
  • You can throw anything
  • Recursive fib/fact throwing examples, with timings compared to straight recursion
  • Advice to catch exceptions by reference
  • Exception handler chosen based on the static type, not the dynamic type, of a pointer or reference.
  • Standard exception types: length_error, bad_alloc, ios::failure
  • Never let a destructor throw an exception
  • Design patterns continued: program to interfaces; use abstract classes
  • Iterator pattern with abstract classes; abstracting over iterators
  • Template function: foreach
  • Start Observer pattern

Lecture 17 (June 28)

  • Observer pattern
  • Decorator pattern
  • Factory method pattern

Lecture 18 (June 30)

  • Template method pattern
  • NVI idiom
  • STL: maps (operator[], erase, count, iteration), pairs
  • GDB with examples
  • Visitor pattern: as double-dispatch

Lecture 19 (July 5)

  • Visitor pattern: as a way to add functionality to a class hierarchy without adding methods
  • Visitor example won’t compile: diagnose problem (circular include dependency)
  • Compilation dependencies: when to include vs. forward declare
  • Scenarios: when do we need class A’s def’n: inheriting from A, composition, ptr field to A, methods that take/return A objects
  • Fix visitor so it compiles and run it
  • Advice to include as few .h files as possible in .h files
  • Advice to include .h files into .cc files instead of .h files, whenever possible
  • pimpl idiom – rewrite XWindow class to use pimpl
  • Generalize pimpl to Bridge pattern

Lecture 20 (July 7)

  • Measures of design quality: coupling and cohesion
  • MVC
  • Exception safety: why it is necessary
  • Guarantees about what happens during stack unwinding
  • Advice to prefer stack-allocated objects with destructors
  • RAII - example from files, unique_ptr

Lecture 21 (July 12)

  • RAII - unique_ptr copy disabled, implementation
  • shared_ptrs, advice to use smart pointers as much as possible
  • Exception safety guarantees–basic, strong, nothrow
  • Techniques for providing the strong guarantee–copy and swap, pimpl idiom, importance of no-throw swap operations
  • Exception safety and STL vectors–vector’s dtor frees aray; does not free ptrs inside the vector
  • Vectors of shared_ptrs
  • Strong guarantee of emplace_back
  • Importance of no-throw move operations; declaring functions noexcept

Lecture 22 (July 14)

  • Casting: static, reinterpret, const, dynamic
  • Casting on smart pointers
  • Examples of using dynamic cast (on ptrs/smart ptrs) to determine run-time types
  • Advice against doing this in general: prefer virtual functions or visitors
  • Dynamic casting on references
  • Solving the virtual operator= problem with a dynamic reference cast

Lecture 23 (July 19)

  • vtables and vptrs: demonstrate that having virtual methods makes your objects bigger by the size of a pointer
  • Methods not actually stored in objects; converted to ordinary functions
  • Explain in detail virtual function call resolution: diagram vptrs and vtables; conclude thatvirtual function calls slower than ordinary function calls.
  • Object layout in g++: vptr first, then fields
  • Multiple inheritance: disambiguating ambiguous references, diamond pattern, virtual vs. nonvirtual inheritance
  • Object layout under multiple inheritance
  • Pointer assignment between superclasses and subclasses does not preserve addresses
  • reinterpret_cast will preserve the address and is therefore especially dangerous under multiple inheritance (static_cast, dynamic_cast, and C-style cast OK)

Lecture 24 (July 21)

  • Template functions; type argument deduction
  • Abstracting iterator and function types into template arguments
  • STL algorithms
  • Examples: for each, count, copy, transform
  • Function objects
  • Lambdas
  • Generalized iterators: stream iterators, inserters


End of course; Final exam: 9:00 AM, August 5, 2016