Simple copy of fields -> only the first node is actually copied (shallow copy)
If you want a deep copy (copies the whole list), must write your own copy ctor:
Brad Lushman
Office: DC 3110
Email: bmlushma
http://www.student.cs.uwaterloo.ca/~cs246
Linux is required! Ripperino
Options:
1. Lab, computers
2. Install Linux on your machine
3. ssh into school machines (recommended) (Windows: download putty.exe, winscp for file transfer)
4. Cygwin - ewwwwwww
Also - install an xwindows server. eg. XMing
Modules:
1 - Linux Shell (2 weeks)
2 - C++ (10 weeks)
3 - Tools (interspersed)
4 - Software engineering (interspersed)
Homework: Print Linux handout from Piazza, and bring it to class
Shell - interface to OS - get the OS to do things - run programs, manage files - graphical shell (clicking with mouse/ touch interface) - command line - type commands at a prompt - more versatile
This course: bash
Make sure you are using bash! - Log in + type echo $0
- should say bash
Working with files
- cat - displays the contents of a file
- cat /usr/share/dict/words
- general format: root (top) directory/ directories (contains files)/ file
In Linux, a directory is considered a kind of file
^C to stop a program
ls : list files in current dir (non-hidden files)
ls -a : gives all files (even hidden ones)
hidden files start with a dot
pwd - prints current directory
What happens if you type cat?
- waits for input
- prints everything you type
Useful? - if we can capture input in file.
Observe:
cat > output.txt
To stop: Ctrl - D (^D) at the beginning of a line sends an end of file signal
In general: command args > file ; executes command args + captures the output in file
- called output redirection
Can also redirect input:
cat < inputfile.txt
What’s the difference?
cat inputfile.txt
passes the name inputfile.txt as an arg to cat. cat opens the file and displays it
cat < inputfile.txt
SHELL opens inputfile.txt and passes the contents to cat in place of keyboard or input
Observe:
wc output.txt
> 2 5 27 output.txt
wc < output.txt
> 2 5 27Also: cat *.txt <- globbing pattern
(* means match any sequence of chars)
- shell finds all files in the current dir that matches the pattern + substitutes on the cmd line.
(eg. cat a.txt, b.txt, c.txt - opens all 3 and displays)
More globbing patterns - Linux Sheet
Many, but not all programs accept input either on the command line or by redirection
Can do both redirections
cat < in.txt > out.txt
Every process is attached to 3 streams: stdin, stderr, stdout
stderr - never buffered - get errror msgs immediately
Use output from one program as the input of another
Example: How many words occur in the first 20 lines of myfile.txt?
Tools (sheet):
head -n filegives the first n lines of the file
wccounts words, lines, characters
wc -wgives just words
Soln: head -20 myfile.txt | wc -w
the | is a pipe
How many words occur in the first 20 lines of myfile.txt?
Sol’n head -20 myfile.txt | wc -w or cat myfile.txt | head -20 | wc -w
Eg. Suppose words1.txt, words2.txt, etc. contain lists of words, one per line. Print a duplicate-free list of all words that occur in any of these lines.
uniq - removes CONSECUTIVE duplicate entries -if entries are sorted, then it removes all duplicates
sort - sorts lines
cat words*.txt | sort | uniq
Can we use the output of one program as param of another? (yes)
echo "Today is $(date) and I am $(whoami)"
> Today is Tue Sep 13 10:13:50 EDT 2016 and I am alqiuShell executes date + whoami + substitues the result into the command line
The quotations make it into only ONE arg. Also, whitespace here is used.
echo Today is $(date) and I am $(whoami)
> Today is Tue Sep 13 10:13:50 EDT 2016 and I am alqiuHere, echo is given 7 arguments. Whitespace is ignored
Careful:
echo 'Today is $(date) and I am $(whoami)' > Today is $(date) and I am $(whoami)Single quotes does not make any substitutions.
echo *
echo '*' #outputs the same (*)
echo "*" #outputs the same (*)eg. Print every line in index.html that contains cs246.
egrep cs246 index.htmlHow many lines in index.html contain cs246 or CS246?
egrep "cs246|CS246" index.html | wc -l //the quotes are really important here since bash thinks | is a pipe otherwiseAlt soln:
egrep "(cs|CS)246" index.html | wc -lAvailable patterns - called regular expressions (different from globbing patterns)
"(c|C)(s|S)246" -also matches cS246, Cs246
"[cC][sS]246"[..] - any one char between [ and ]
[ .. ] - any one char except
Add optional space: "[cC][sS] ?246"
? = 0 or 1 of the preceding expression (0 or 1 space in this case)
* = 0 or more of preceding
"(cs)*246"
> 246, cs246, cscs246 .... = any single character
.* = anything
egrep "cs.*246" index.html"^cs246" - lines that start with 246 "^cs246$" - lines that are exactly 246 Eg lines of even length
"^(..)*$"Files in the current dir whose names contain exactly one a.
ls | egrep "[^a]*a[^a]*"All words in the global dictionary that start with e and have 5 characters
egrep "^e....$" /usr/share/dict/wordsls - l - “long form” listening
-rw-r----- 1 j2smith j2smith 25 Sep 9 15:27 abc.txt
(-)type|(rw-r-----)permissions|(1)#of links| (j2smith) owner| (j2smith) group| (25) size | (25 Sep 9 15:27) last modified | (abc.txt) name- an ordinary filed directoryrwxrwxrwx -> 1st rwx bits are “user bits”, then next 3 are “group bits”, last is “other bits” r - read bit w - write bit x - execute bit| Bit | Meaning for Ordinary Files | Meaning for directories |
|---|---|---|
| r | files contents can be read |
directory's contents can be read (eg. ls works, globbing, tab completion) |
| w | files contents can be modified |
directory's contents can be modified |
| x | file can be executed as a program |
directory can be navigated (i.e. can cd into the dir) |
dir’s exec. bit not set = no access at all to the dir, nor to any subdir, nor to any file within it.
Changing permissions:chmod mode file
Mode:
| u - user |
|
r read |
| g - group |
|
w write |
| o - other | = set perm | x execute |
| a- all |
eg.
give others read permission: chmod o+r file
make everyone’s permission rx: a = rx
give owner full control: u = rwx or u+rwx
Changing permissions - > exclusive right of the owner
files containing sequences of shell commands, executed as programs
eg. Print date, current user, current dir
#!/bin/bash //"shebang" line - executes this file as a bash script
date
whoami
pwdNote: the script does not have the execute bit turned on. Give the file execute permission:
chmod u+x myscript
Run the file:./myscript
x=1 (NO spaces)
echo $x
> 1Note: use when setting a var.
Good practice: {dir}
Some “global” vars available:
Important: PATH - list of dirs; When you type a command, the shell searches these directories in order for a program with that name
Eg. Check whether a word is in the directory
eg../isItAWord hello
#!/bin/bash
egrep "^$1$" /usr/shar/dict/wordsPrints nothing if word not found
Prints the word if found
Eg. - a good password should not be in the dictionary
answer whether a word is a good password
#!/bin/bash
egrep "^$1$" /usr/share/dict/words > /dev/null //(suppresses output)
if [ $? -eq 0 ]; then //the ; here allows you to put the then on the same line
echo Bad password
else
echo Maybe a good password
fi //ends the if?Note: every program returns a status code when finished
egrep: returns 0 if found, 1 if not found (In Linux: 0 is success, non-0 is fail)
$? = status of the most recently executed command
Verify # of args ; print error msg if wrong
#!/bin/bash
usage(){
echo "Usage: $0 password" >&2
}
if [ $# -ne 1]; then
usage
exit 1
fi
...(as before)If stmt: //comparisons + other conditions handout
if [ cond ]; then
...
elif [ cond ]; then
...
else:
...
fiPrint #’s from 1 to $1
#!/bin/bash
x=1
while [ $x -le $1]; do
echo $x
x=$x+1
doneThis gives you “1+1” literally if x=1
you want $((…)) for arithmetic instead
Looping over a list
eg. Rename all .cpp files to .cc
#!/bin/bash
for name in *.cpp; do
mv ${name} ${name%cpp}cc
donenote:
*.cpp -> glob - replaced with all matching files
name%cpp is the val of name, without the trailing cpp.
How many times does word 2?
x=0
for word in $(cat $2); do
if [ "$word" = "$1" ]; then
x=$((x+1))
fi
done
echo $xPayday is the last Friday of the month. When is this month’s payday?
2 tasks: Compute date
Report answer
#!/bin/bash
answer(){
if [ $1 -eq 31]; then
echo "This month is the 31st"
else
echo "This month: the ${1}th"
}fi
answer $(cal | awk '{print $6}' | egrep "[0-9]" | tail -1)Generalize to any month. cal October 2016 -gives Oct’s calendar
let payday October 2016 give october’s payday
ALL OF THESE ARE IN THE REPO
answer(){
if [ $2 ]; then
preamble=$2
else
preamble = "This month"
fi
if [ $1 -eq 31]; then
echo "${preamble}: the 31st"
else
echo "${preamble: the ${1}th}"
fi
}
answer $(cal $1 $2 | awk '{print #6}' | egrep "[0-9]" | tail -1)note: no such thing as scope. You can reference from anywhere. if the var doesn’t exist, you get a blank.
Human testing
Machine testing
Black/White/Grey Box Testing
Start with black box, supplement with white box
Black box:
White box:
Performance testing - is the program efficient enough?
Regression testing
//Hello world in C:
#include <stdio.h>
int main(){
printf("Hello World");
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++ (if no return in main, 0 is implied)
stdio.h , printf still available in c++I/O header <iostream>Output:
std::cout << ___ << ___ << ___ (___ is data)
std::endl = end of line
g++-5 -std=c++14 program.cc <-o program> (name of the excutable(by default, a.out))
OR
g++14 program.cc -o program
./program
3 I/O streams:
I/O operators:
operator points in the direction of information flow
#include <iostream>
using nanospace std
//above two lines are usually there even if teach doesn't write it (omit from now on)
int main(){
int x,y;
cin >> x >> y;
cout << x + y << endl;
}What if the input is exhausted before we get two ints?notes:
cin >> ignores whitespace
what if input doesn’t contain an int? -statement fails, value of var is undefined
If the read failed: cin.fail() will be true
If EOF: cin.eof() and cin.fail() will both be true
Ex: read all ints from stdin, echo them and per line to std out. Stop on any failure.
int main(){
int i;
while(true){
cin >> i;
if(cin.fail()) break;
cout << i << endl;
}
}Note: Here is an implicit conversion from cin to bool
- cin can be used as a condition - true if success, false if failed
//example v2.0
int main(){
int i;
while(true){
cin << i;
if(!cin) break;
cout << i << endl;
}
}Note: >> is c’s right bitshift operator.
a >> bshifts a’s bits to the right by b spots.
E.g. 21 >> 3 -> 21 = 10101 shifted 3 = = 2
But when LHS is cin, >> is “get from”
operator >>:
This is why we can write cin >> x >> y >> z; the >> returns cin as each >> is calculated, which allows y and z to also be read in.
//example v3.0
int main(){
int i;
while(true){
if(!(cin>>i)) break;
cout << i << endl;
}
}//example v4.0
int main(){
int i;
while(cin >> i){
cout << i << endl;
}
}Ex: Read ints + echo to stdout until EOF. Skip all non-int input
int main(){
int i;
while(true){
if(!(cin>>i)){
if(cin.eof()) break;
cin.clear(); //clears the fail bit
cin.ignore(); //skips the next char (because the char causing this to fail is still there)
}
else cout <<i << endl;
}
}type std::string (#include <string>)
int main(){
string s;
cin >> s; //skip leading whitespace (stop at whitespace)
cout << s << endl; //(therefore only reads one word)
}If we want the whitespace: getline(cin, s);
cout << 95 << endl;
What if we want to print a # in hexadecimal?
cout << hex << 95 << endl; \\prints 5f
hex : I/O manipulator - all subsequent ints printed in hex
cout << dec to go back to decimal
Other manipulators - notes #include <iomanip>
Stream abstraction applies to other sources of data
Files
File access in C:
int main(){
char s[256];
FILE *file = fopen("myfile.txt","r");
while(true){
fscanf(file, "%255s", s);
if(feof(file)) break;
printf("%s\n", s);
}
fclose(file);
}C++:
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
int main(){
ifstream file{"myfile.txt"}; // Initialization syntax. Declaring an ifstream opens the file
string s;
while(file >> s){
cout << s << endl;
} // file is closed automatically as soon as the ifstream (file) goes out of scope :o woah
}note: This is the same as reading from cin in c++ except we use file in the while loop.
Anything you can do with cin/cout, you can also do with an ifstream/ofstream.
Example - strings - attach a stream to a string var + read from/write to it
#include<sstream>
std::istringstream
std::ostringstream
//-read from/write to a string
int lo = _____, hi = _____;
ostringstream ss;
ss << "Enter a # btwn " << lo << " and " << hi;
string s = ss.str();Eg - convert string to #
int n;
while(true){
cout << "Enter a # " <<endl;
string s;
cin >> s;
(string stream ss {s}); // {s} <- initialization
if(ss >> n) break;
cout << "I said, ";
}
cout << "You entered " << n << endl;Example revisited: Echo #’s, skip non-#’s
int main(){
string s;
while(cin >> s){
istringstream ss {s};
int n;
if(ss >> n) cout << n << endl;
}
}In C:
C++ strings:
Eg: string s = “Hello”; // still a c-style string (char array with \0)
s - c++ string created from the c string on initialization
Equality - s1 == s2, s1 != s2
Comparison - s1 <= s2 (lexicographic)
Get individual chars - s[0] , s[1], … etc
Concat: s3 = s1 + s2; s3 += s4
void printWordsInFile(string name = "suite.txt"){
ifstream file {name};
string s;
while (file >> s) cout << s << endl;
}
printWordsInFile("suite2.txt");
printWordsInFile(); //uses stuite.txtNote: Optional parameters must be LAST
C:
int negInt(int n) {return -n;}bool negBool(bool b) {return !b;}C++
F’ns with different param lists can share the same name
int neg(int n) {return -n;}
bool neg(bool b) {return !b;}
Compiler uses # + type of args to decide which neg is being called
Overloads must differ in # or types of args - may not differ on just return type
struct Node {
int data;
Node *next;
};struct Node {
int data;
Node next; //what's wrong? This makes the struct have no finite size since
// this contains a node in a node in a node ... etc which has no calculable size
};const int maxGrade = 100; // must be initialized
Node n1 = {5, nullptr}; \\syntax for a null ptr. Do not say NULL or 0 in this class
const Node n2=n1
Recall:
void inc (int n){++n;}
...
int x=5;
inc(x);
cout << x << endl; //prints 5call-by-value-inc gets a copy of x, increments the copy, original unchanged
If a function needs to modify an arg - pass a ptr
void inc(int *n){(*n)++;}
...
int x=5;
inc(&x);
cout << x << endl; //prints 6Q: why cin >> x and not cin >> &x ?
A: C++ has another ptr-like type: references
int y = 10;
int &z = y; //z is an lvalue reference to y. Like a const ptr.
//similar to int *const z = &y;References are like constant ptrs with automatic de-referencing
z -> y [10]
z = 12; //(NOT *z = 12)
//(now, y == 12)
int *p = &z; // gives the address of yIn all cases, z behaves exactly like y.
z is an alias (“another name”) for y
Things you can’t do with lvalue references:
int &x = 3; X , int &x = y + z; X , int &x = y; Is okayint &*x;- for c, always start at var and then go left. So x is a pointer to a ref of an int.int *&x = ... ;int &&x = ... ; - this means something difference (we’ll talk about this later)int &r[3] = {n,n,n}; XWhat can you do? pass as f’n params:
void inc (int &n){++n;} // notice that there's no ptr deref and &n is a const. ptr to the arg.
int x = 5;
inc(x);
cout << x << endl; // 6So why does cin >> x work? - takes x by reference
istream & operator >> (istream &in, int&data)
Pass-by-value. eg: int f(int n) { ... } copies the arguement
struct Really Big { ... },int f(ReallyBig rb){ ... }; // really slow
int g(ReallyBig &rb){ ... }; // &rb is now an alias - fast. Downside is that rb can be changed by the f'n. You don't know.
int h(const ReallyBig &rb) { ... }; // really fast and param can't be changed. woahAdvice: prefer pass-by-const-ref over pass-by-value for anything larger than a ptr - unless the f’n needs to make a copy anyway. Then, maybe pass-by-value.
Also: int f(int &n) { ... } int g(const int &n) { ... }
f(5); // won't compile. can't initialize an lvalue ref (n) to a literal value. if n changes, can't change the literal 5.
g(5); //is a-OK since n can never be changed. Compiler allows this. How? compiler creates a temp location to hold the 5, so the reference n has something to point to.C:
int *p = malloc( ... *sizeof(int));
...
free(p); //DON'T USE THESE IN C++Instead: new/delete - type aware and less error-prone
Eg
struct Node {
int data;
Node *next;
};
Node *np = new Node;
...
delete np;Node *np = new Node[10];
...
delete [np];Node getMeANode(){ //return-by-value = copy. expensive?
Node n;
return n;
}
//-return by ptr(ret) instead?
Node *getMeANode(){
Node n;
return &n;
//BAD - returns a ptr to stack - allocated data which is dead on return
}
Node *getMeANode(){ //Ok - returns a ptr to Heap data - still alive - but don't forget to delete it!
return new Node;
}Give meanings to c++ operators for our own types
eg
struct Vec{
int x,y;
}Vec operator +(const Vec &v1, const Vec &v2){
Vec v={v1.x + v2.x , v1.y + v2.y};
return v;
}
Vec operator *(const int k, const Vec &v){
return {k*v.x, k*v.y} //okay since compiler knows that it's a vec based on the return type
}
// this only works when scalar is on the left (eg. k*v). To get v*k, we need to make another function.
Vec operator*(const Vec &v, const int k){
return k*v;
}Eg.
struct Grade{
int theGrade;
};
ostream &operator<<(ostream &out, const Grade &g){
out << g.theGrade << '%';
return out
}
istream &operator>>(istream &in, Grade &g){
in >> g.theGrade;
if(g.theGrade < 0) g.theGrade=0;
if(g.theGrade>100) g.theGrade=100;
return in;
}Transforms the program before the compiler sees it. # = preprocessor directive
eg.#include
Including old C headers - new naming convention
eg. Instead of #include <stdio.h>, use #include<cstdio>
#define VAR VALUE //- sets a preprocessor variable, then all occurrences of VAR in the source file are replaced with VALUE
#define MAX 10
int x[MAX] //transformed to int x[10]. Was a cheap way of const from the old days (1970s) before const was a thing
#define FLAG //sets the variable FLAG; Value is the empty stringDefined constants are useful for conditional compilation
#define IOS 1
#define BBOS 2
#define OS IOS //(or BBOS)
#if OS==IOS
short int publickey; //Removed if OS!=IOS
#elif OS==BBOS
long long int publickey; //this code is removed if OS!=BBOS
#endifSpecial Case
#if 0 //never true - all inner text is removed before it gets to the compiler
#endif
//heavy-duty "comment out"Can also define symbols via compiler arguments
int main(){
cout << x << endl;
}g++14 -DX=15 define.cc -o define#ifdef NAME //true if NAME has been defined
#ifndef NAME //true if NAME HAS NOT been defined
int main(){
#ifdef DEBUG
cout << "setting x=1" <<endl;
#endif
int x=1;
while(x<10){
++x;
#ifdef DEBUG
cout << "x is now" << endl;
#endif
}
cout << x << endl;
}gc++14 -DDEBUG debug.cc -o debug
//enables debug outputSplit program into composable modules, with
E.g. Interface (vec.h)
struct Vec{
int x,y;
}
Vec operator +(const Vec &v1, const Vec &v2);
...main.cc
#include "vec.h"
int main(){
Vec v = {1,2};
v = v+v;
...
}
//implied vec.cc
#include "vec.h" //we include vec.h here because we don't know what a vec is.
Vec operator+(const Vec &v1, const Vec &v2){
...
...
...
}Recall: an entity can be declared many times, but defined at most once
g++14 -c vec.cc
g++14 -c main.cc
-c-> means compile only, do not link, do not build the executable. Produces an object file.
g++14 vec.o main.o -o mainGlobal var: int globalNum;
vec.h
struct Vec{
int x,y;
};
extern int globalVar;
Vec operator+(const vec &v1, const Vec &v2);vec.cc
#include "vec.h"
int global Num;
Vec operator+(const Vec &v1, const Vec &v2){
...
}Let’s write a linear algebra module
linalg.h
#include "vec.h"
...linalg.cc
#include "linalg.h"
#include "vec.h"
...main.cc
#include "linalg.h"
#include "vec.h"
...The above won’t compile:
Need to prevent files from being included twice
Sol’n: “include guard:”
vec.h
#ifndef VEC_H
#define VEC_H
... file contents
#endiffirst time vec.h is included. Symbol VEC_H is not defined so file is included. After that, symbol is defined so vec.h is never included twice.
Always - put include guards in .h files
Never - include .cc files - many many different functions. Included .cc file, you defined everything again and again and again.
Never - put using namespace std in header files. This directive would be forced on any client that includes this file
- inside header files, always say std::cin, std::string etc.
eg.
struct Student{
int assns, mt, final;
float grade(){
return assns*0.4 + mt*0.2 + final*0.4;
}
};
Student s{60,70,80};
cout << s.grade() << endl;class
object
eg: Student - class, s - object, {60, 70, 80}
The function grade - called a member function (or method)
What doe assns, mt, final inside of grade ( ) {…} mean?
- they are fields of the current object upon which grade was invoked
e.g.
Student billy{60, 70, 80};
billy.grade(); \\method call uses billy's assns, mt, finalFormally: methods take a hidden extra parameter called this - ptr to the object on which the method was invoked. eg. billy.grade() <- (this) == &billy
can write
struct Student{
int assns, mt, final;
float grade(){
return this->assns *0.4 + this->mt*0.2 + this->final*0.4;
}
};Initializing Objects
Student billy {60, 70, 80}; //ok, but limitedBetter: Write a method that does initialization: a constructor (ctor)
struct Student{
int assns, mt, final;
float grade(){...}
Student(int assns, int mt, int final){
this->assns = assns;
this->mt = mt;
this->final = final;
}
}
Student billy {60, 70, 80}; //better. Even though this looks the same as above, this calls a ctor if it has been defined. IF no ctor has been defined, these initialize the individual fields of student.Head allocation:
Student xpBilly = new Student{60,70,80};Advantages of ctors: default params, overloading, sanity checks
eg:
struct Student{
...
Student(in assns = 0, int mt=0, int final=0){
this.assns = assns;
this.mt = mt;
this.final =final;
}
}Note: Every class comes with a default (ie no-arg) ctor (which just default constructs all fields that are objects).
eg.
Vec v; //default ctor (does nothing in this case, the fields aren't objects)But the built-in default ctor goes away if you provide a ctor
E.g.
struct Vec{
int x,y;
Vec(int x, int y){
this->x=x;
this->y=y;
}
}
Vec v{1,2}; OK
Vec v; XXXXWhat if a struct contains consts or refs?
struct MyStruct{
const int myConst; //these two have to be initialized
int &myRef;
};
int z;
struct MyStuct {
const int myConst = 5;
int &myRef=z;
}; //this is kind of bad since not every MyStruct wants the same val. Compiles, thoughBut does every instance of student need the same value of myConst, etc?
Eg.
struct Student{
const int id; //const (doesn't change) but not the same for all students.
}Where do we initialize? ctor body? TOO LATE!
Where do we initialize? ctor body? - too late - fields must be fully constructed by then.
What happens when an object is created:
How? - member initialization list (MIL)
struct Student{
const int id;
int assns, mt, final;
Student(int id, int assns, int mt, int final):
id{id}, assns{assns}, mt{mt}, final{final} {}
}Here: id - field, {id} - params
Note: can initialize any field this way, not just const + refs
Note: Fields initialized in the order in which they are declared in the class, even if the MIL orders them differently
Note: MIL sometimes more efficient than setting fields in the body. (o/w - run default ctor, then reassign in the body) EMBRACE THE MIL! ALL HAIL. PRAISE BE.
what if a field is initialized inline AND in the MIL?
struct Vec{
int x=0, y=0;
vec(int x); x{x} {}
};MIL takes precedence
int x = 5;
int x(5);
string s = "hello";
string s("hello");
Student billy(60,70,80);
//preferred (cs246 doesn't care which init you use though). This was updated as of a few years ago.
int x{5};
string s{"hello"};
Student billy{60,70,80};Now consider:
Student billy{60,70,80};
Student bobby = billy; //-how does this init happen? the COPY CONSTRUCTOR. For constructing one object as a copy of anotherNote: Every class comes with:
- default ctor (default constructs all fields that are objects)
- copy ctor (just copies all the fields)
- copy assignment operator
- destructor
- move ctor
- move assignment operator
Building your own copy ctor:
struct Student{
int assns,mt,final;
Student(...) {...}
Student(const Student &other): assns {assns}, mt {mt}, final {final} {}
}; //equiv. to built inWhen is the built-in copy ctor not correct?
struct Node{
int data;
Node *next
Node(int data, Node *next): data {data}, next{next} {}
...
};
Node *n = new Node {1, new Node {2, new Node {3, nullptr}}};
Node m = *n;
Node *p =new Node{*n};
Simple copy of fields -> only the first node is actually copied (shallow copy)
If you want a deep copy (copies the whole list), must write your own copy ctor:
struct Node{
...
Node(const Node &other): data{other.data}, next{ other.next? new Node (*other.next) : nullptr}{}
} //we have some sneaky recursion going on here. This recursively invokes the copy ctor + copies the rest of the listThe copy ctor is called:
Note: Careful with ctors that can take ONE parameter:
struct Node{
Node(int data): data{data}, next{nullptr}{}
};single-arg ctors create implicit conversions.
Eg:
Node n{4};
// - also I can call:
Node n =4; //- implicit conversion from int to node.
int f(Node n){...}
f(4); //works -4 is implicitly converted to NodeDanger - accidentally passing an int to a f’n expecting a Node. Compiler will not signal an error.
Good idea - disable the implicit conversion - make the ctor explicit
struct Node{
...
explicit Node(int data): data{data}, next{nullptr}{}
};
Node n{4}; //ok
Node n = 4; //errorWhen an object is destroyed (stack-allocated: goes out of scope, heap-allocated: is deleted) a method called the destructor runs. Classes comes with a dtor (just calls dtor on all fields that are objects)
When an object is destroyed:
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 (stack-allocated). The entire list is leaked.
If we say delete np; then the 2 & 3 nodes are leaked
Write a dtor to ensure the whole list is freed:
struct Node{
...
~Node(){delete next;} //<- recursively calls next's dtor - frees the whole list.
};Now - delete np; -frees the whole list
Student billy{60,70,80};
Student jane = billy; //copy ctor
Student mary; //default ctor
mary = billy; //copy, but not construction. copy assignment operator is `=` - uses compiler-supplied defaultMay need to write your own:
struct Node{
...
//So that cascading works your return itself. Eg. a=b=c=4; returns a = b = c; (c=4 now), a=b, (b=4 as well now), and then a=4;
Node &operator=(const Node &other){
data=other.data;
delete next; //the existing node might have other nodes so we need to delete those.
next=other.next? new Node{*other.next}:nullptr;
return *this;
//THIS IS 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
*p = *q;
a[i] = a[j];When writing operator=, ALWAYS be wary of self-assignment:
struct Node{
...
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;
}//if new fails, Node is still in a valid state.
Node& operators=(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
}Alternative: copy + swap idiom <3
#include <utility>
struct Node{
void swap(Node &other){
using std::swap;
swap(data,other.data);
swap(next, other.next);
}
}
Node &operator=(const Node &other){
Node tmp = other; //tmp = copy of other
swap(tmp); //me = copy of other. tmp = my old fields
return *this; //my old data deleted when tmp goes out of scope
}Recall: - an lvalue is anything with an address. -an lvalue reference (&) is like a const pointer with automatic dereferencing. -always initialized to a 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); //copy ctor. What is "other" here? Reference to what?temporary object to hold the result of plusOneNode m3 = plusOne(n); is doneVersion of the ctor that takes Node &&.
struct Node{
...
Node(Node && other): //called a move ctor
// what should the move ctor do? Should steal other's data.
data{other.data},
next{other.next} {
other.next=nullptr; //else the list is destroyed when other is destroyed. This ctor is constant time.
}
}Similarly:
Node m;
m=plusOne(n); //Assignment from temporary
//More assignment operator:
struct Node{
...
Node &operator=(Node &&other){
swap(other); //steal other's data
return *this; //destroy my old data. swap without copy
}
}If you don’t define move ctor/assignment, the copy versions will be used. If the move ctor/assignment is defined, it will replace all calls to copy ctor/assignment when the argument is a temporary (rvalue).
Vec makeAVec(){
return {0,0}; //invokes a basic ctor
}
Vec v=makeAVec(); //what runs? Not Sure! When compiled in g++, there's the basic ctor (no move/copy ctor).In some circumstances, the compiler is allowed to skip calling copy/move ctors (but doesn’t have to)
In this example: makeAVec writes it’s result ({0,0}) directly into the space occupied by v in the caller, rather than copy or move it later.
Example:
void doSomething(vec v)//<- pass-by-value copy/move ctor
{...}
doSomething(makeAVec()); //-result of makeAVec is written directly into the parameter. There is no copy or move. This is allowed even if dropping ctor calls would change the behaviour of the program. eg. if the ctors print something.You are not expected to know exactly when move/copy elision is allowed, just that it is possible.
If you need all of the ctors to run: g++14 -fno-elide-constructors runs all constructors. But this can slow down your program considerably
In Summary: Rule of 5 (Big 5)
Notice:
operator=is a member function, not a standalone function
When an operator is a member,thisis the first arguementstruct Vec{ int x,y; ... Vec operator+(const Vec&other){ return{x+other.x, y+other.y}; } Vec operator*{const int k}{ //implements v*k return {x*k, y*k}; } //How do we implement k*v? Can't be a member -first arg not Vec. -Write it as a standalone: } Vec operator*(const int k, const Vec &v){ return v*k; }
I/O operators:
struct Vec{
...
ostream &operator<<(ostream &out){
return out << x << ' ' << y;
}
};
//what's wrong? Make Vec the first arg. -> Use as vec<<cout;So define <<. >> as standalone fns.
Certain operators must be members:
Node.h
# ...
struct Node{
int data;
Node *next;
explicit Node(int data, Node*next=nullptr);
bool hasNext();
};Node.cc
#include "node.h"
Node(int data, Node *next): data{data}, next{next} {} //compiler will yell at you for this. No return type and can't use init for f'ns.
Node::Node(int data, Node *next): data{data}, next{next}{} //tells compiler that it belongs to a class
bool hasNext(){return next!=nullptr;} //will yell and say that you're using an undeclared variable
bool Node::hasNext(){return next!=nullptr;}//better:: - scope resolution operator
Node:: ____ means ____ within class node
:: like . where LHS is a class or namespace, not an object
struct Vec{
int x,y;
Vec(int x, int y): x{x}, y{y} {}
};
Vec *vp = new Vec[5]; // X
Vec moreVecs[3]; // X
//there want to call the default ctor on each item. Can't init array elements - no default ctor.Options
Vec moreVecs[] = {{0,0}, {1,3}, {2,4}};Vec **vp = new Vec*[5];
vp[0]=new Vec {0,0};
vp[1]=new Vec[1,3];
...
for(int i=0; i<5;++i){
delete vp[i];
}
delete[] vp;Const objects arise often
int f(const Node &n) {...}What is a const object? Can’t change fields
Question: Can we call methods on a const object?
Issue:
The method may modify fields, violate const
Answer: Yes - we can call methods that promise not to change fields
struct Student{
int assns, mt, final;
float grade() const; //this method will not change fields
};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 objects
struct Student{
...
int numMethodCalls=0;
float grade() const{
++numMethodcalls; //method isn't const anymore. If you take const out, can't call grade on const students
return ...
}
};But mutating numMethodCalls affects only the physical constness of student objects, not the logical constness
Want to be able to update numMethodCalls, even if the object is const - declare the field mutable
struct Student{
float grade() const{
++numMethodCalls;
return ...;
}
};mutable fields can be changed, even if the object is const.
numMethodCalls tracked # of method calls for each particular Student
What if we want to track method calls over all Students?
Or what if we want to know how many Students were created?
Static members - associated with the class itself, not with any specified instance (object).
struct Student{
...
static int numInstances;
Student(int assns, int mt, int final): assns{assns}, mt{mt}, final{final} {
++numInstances;
}
};
int Student::numInstances=0; //in .cc filestatic fields must be defined, external to the class
this param)struct Student{
...
static int numInstance;
...
static void printNumInstances(){
cout << numInstances << endl;
}
};
Student billy{60,70,80};
Student jane{70,80,90};
Student::printNumInstances(); //2struct Node{
int data;
Node *next;
Node(int data, Node*next);
...
~Node(){delete next;}
};
Node n1 {1, newNode {2, nullptr}};
Node n2 {3, nullptr};
Node n3 {4, &n2};What happens when these go out of scope?
Class Node relies on an assumption for its proper operation - next is either nullptr or allocated by new.
This is an invariant - statement that holds true, upon which Node relies.
But we can’t guarantee this invariant - can’t trust the user to use Node properly.
Can’t enforce any invariants - user can interfere with our data.
Eg. - Stack : Invariant -> last item pushed is first item popped.
but not if the client can rearrange the underlying data.
Hard to reason about programs if you can’t rely on invariants.
To enforce invariants - we introduce encapsulation - we can’t clients to treat our objects as black boxes - capsules.
Eg
strut Vec{
Vec(int x, int y); //public by default
private:
int x,y;//can't be accessed outside the struct Vec.
public:
Vec operator+(...);//anyone can access
...
};In general: want fields to be private - only methods should be public.
Better to have default visibility to be private.
Switch from struct to class.
THIS IS THE ONLY DIFFERENCE BETWEEN STRUCT AND CLASS -> default visibility. Public in struct. Private in class.
class Vec{
int x,y;
Vec(int x,y);
Vec operator+(...);
...
};Summary: Rvalues & Lvalues
Move Copy/Assignment
Rule of Five
Member Operators
struct Node{
int value;
Node *next;
};
Node add(Node n, int inc){ //copy ctor runs
for(Node *m=&n; m != nullptr; m = m->next){
m->value += inc;
}
return n;
}
Node n1{1,3};
Node n2 = add(n1,3); //move ctor
n2 = add(n1, 4); //move assign
Node(Node &&other): //impl of the move ctor
value{other.value}, next{other.next} {
other.next = nullptr;
}Node &operator=(Node &&other){
swap(value, other.value);
swap(next, other.next);
return *this;
}
lvalue -> with address
rvalue -> without address
Recall:
class Vec{
int x,y;
public:
Vec (int x, int y);
Vec operator+(...);
...
};Fix our linked list class:
list.h
class List{
struct Node; //private nested class. Only accessible within list.
Node *theList = nullptr;
public:
void addToFront(int n);
int ith(int n) const;
~List(){delete theList;}
};list.cc
#include "list.h"
struct List::Node{ // Nested class
int data;
Node *next;
Node(...): ... {}
~Node() {delete next;}
};
void List::addToFront(int n){
theList = new Node {n, theList};
}
int List::ith(int i)const{
Node *cur = theList;
for(int n=0; n < i && cur; ++n; curr=cur->next);
return cur-> data;
}Only List can create/manipulate Node objects
Can guarantee the invariant that next is either nullptr or allocated by new.
pause
But - Now we can’t traverse the list from front node to node, as would a linked list.
Repeatedly calling ith - time.
But we can’t expose the nodes, or we lose encapsulation
Book Rec: Design Patterns (by the gang of four)
resume
Solution: Create a class that manages access to nodes
- Create a class that manages access to nodes
- abstraction of a ptr
- walk the list without exposing the actual ptrs.
Inspiration:
for(int *p=a; p! = a+n ; ++p){
... *p ...
}class List{
struct Node;
Node *theList;
public:
class Iterator{
Node *p;
public:
explicit Iterator(Node *p):p{p}{}
int &operator*(){return p->data;} // returns p->data ITSELF. allows the user to update it themselves. (eg. Iterator it ... ; *it = 7;)
Iterator &operator++(){p=p->next; return *this;}
bool operator==(const Iterator &other){ return p==other.p;}
bool operator!=(const Iterator &other){
return !(*this==other);
}
};
Iterator begin(){return Iterator{theList};}
Iterator end(){return Iterator{nullptr};}
...//other methods like ith
...
};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;
}
}Shortcut: automatic type deduction -
auto x = y;.autoautomatically gives x the same type as y.
for(auto it = l.begin(); it!=l.end(); ++it){
cout << *it << endl;
}Shorter cut: range-based for loop
for(auto n:l){
cout << n << endl;
}Available for any class with:
If you want to modify the list items (or save copying):
for(auto &n: l){
++n;
}Iterators shall return later.
Encapsulation ctd.
List Client can create iterators directly :o
auto it = List::Iterator{nullptr}; //well, they only can make a nullptr iterator. But still. Bad form.We could make Iterator’s ctor private. Then client can’t call List::Iterator(...) . But then neither can List.
Solution: Give List privileged access to Iterator. Make it a friend.
class List{
...
public:
class Iterator{
Node *p;
explicit Iterator(Node *p); //private
public:
...
friend clas List; // List has access to all members of Iterator.
};
...
};Now List can still create iterators, but client can only create them by calling begin() and end().
Advice: give your classes as few friends as possible. weakens encapsulation.
Once again: keep fields private. What if you want to give access to fields? use accessor + mutator methods.
class Vec{
int x,y;
public:
int getX()const {return x;} //accessor
void setY(int newY){y=newY;} //mutator
};what about operator << - needs x+y, can’t be a member
If no getX, getY - make operator << a friend function
class Vec{
...
public:
...
friend std::ostream &operator<<(std::ostream &out, const Vec &v);
}
//.cc
ostream &operator<<(ostream &out, const Vec &v){
return out << v.x << ' ' << v.y;
}Separate compilation: g++14 -c list.cc , g++14 -c node.cc, g++14 -c iter.cc, g++14 -c main.cc, g++14 list.o node.o iter.o main.o -o myprog
Why do we do this? So we don’t have to recompile files that haven’t changed.
How do you keep track of what’s changed?
Let Linux help you - with make.
Create a Makefile that says which files depend on which other files.
myprog: main.o list.o node.o iter.o //myprog depends on these
[ ] (MUST be a TAB) g++-5 -std=c++14 main.o list.o node.o iter.o -o myprog (<- how to rebuild)
myprog: main.o list.o iter.o node.o
g++-5 -std==++14 main.o list.o iter.o node.o -o myprog
list.o: list.cc list.h node.h
g++-5 -std=c++14 -c list.cc
etcWhat does myprogram depend on?
- Recursively build these, if necessary
iter.cc changes: - now newer than iter.o (by last modified date). rebuilt iter.o
- now iter.o newer than myprogram. rebuild myprogram
- To do a full rebuild, make clean, make
Generalize with variables
CXX = g++-5 //compiler's name
CXXFLAGS = -std=c++14 -Wall //(Wall turns on warnings)eg.
iter.o: iter.cc iter.h
${CXX} ${CXXFLAGS} -c iter.ccShortcut: for any rule of the form
x.o: x.cc a.h b.h-can leave out the build command
- make guesses that you want
${CXX} ${CXXFLAGS} -c x.cc -o x.oBiggest problem with writing Makefiles
-working out dependencies
and maintaining them if they change.
Can get help from g++
g++14 -MMD -c iter.cc-creates iter.o and iter.d
iter.d
iter.o: iter.cc list.h node.hNow just include this in the Makefile
CXXFLAGS= -std=c++14 -Wall -MMD
...
OBJECTS = main.o list.o iter.o node.o
DEPENDS = ${OBJECTS: .o=.d}
...-include ${DEPENDS}
building an 00 system:
- identify abstractions
- formalize relationships among them
Helpful to map these out
popular standard: UML (Unified Modelling Language)
Modelling a Class
| Name | Vec |
|---|---|
| Fields(optional) | -x:Integer, -y:Integer |
| Methods(optional) | +getx: Integer, +getY:Integer |
Visibility: - -> private, + -> public
Relationship: Composition of Classes
class Vec{
int x,y;
public:
Vec(int x,int y);
};
//Two vecs define a basis
class Basis{
Vec v1,v2;
};
Basis b; //XXX can't initialize v1, v2 - no default ctor for Vec.class Basis{
Vec v1, v2;
public:
Basis(): v1{1,0}, v2 {0,1} {}
};Embedding one obj.(Vec) inside another (Basis) called Composition
Relationship between Basis + Vec is called “owns-a” - A Basis “owns” the two Vec objects.
If A “owns-a” B then typically -
Implement: usually as composition of classes
Modelling
More details: links on course website
Compare car parts in a car (“owns a”) vs car parts in a catalogue.
The catalogue contains parts, but the parts exists on their own. “has-a” relationship (aggregation)
If A “has a” B, then typically
e.g.: Ducks in a pond
Typical Implementation
class Pond {
Duck *ducks[maxDucks];
};Suppose you want to track your collection of books
class Book{
string title, author;
int numPages;
...
};
class Text{
string title, author;
int numPages;
string topic;
...
};
class Comic{
string title, author;
int numPages;
string hero;
...
};-Doesn’t affress relationship among these classes.
-How would we create an array or list containing a mixture of these?
Observe that Texts + comics are KINDS of books. Books with extra features
In c++ - inheritance
class Book{ //Base class or superclass
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 + methods from the base class.
So Text, Comic have title author, numPages.
Any method that can be called on Book can be called on Text, Comic.
Who can see these members?
title, author, numPages are private in Book. - outsiders can’t see them.
Can Text, Comic see them?
No. Even subclasses can’t see them!
How do we initialize 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. DOESN'T WORK HAHA
};Wrong for 2 reasons:
int * const p; //read right to left. p is a constant pointer to an int.
const int *p; //p is a pointer to an int that is constantclass Text: public Book{
...
public:
Text(string title, string author, int numPages, string topic): Book {title, author, numPages}, topic{topic}{}
};If the superclass has no default ctor, the subclass MUST invoke a superclass ctor in its Member Initialization List.
If you want to give the subclass access to certain superclass members, use protected visibility.
class Book{
protected:
string title, author;
int numPages;
...
};
class Topic: public Book{
string topic;
public:
...
void addAuthor(string auth) {author+=auth;} //ok since we protected author
};Not a good idea to give subclasses unlimited access to fields. Breaks encapsulation and invariant. -> eg. if you really don’t want Book to have the author Robert Munch, but you can’t guarantee that all subclasses will follow that rule and since they can change fields, breaks invariant.
Better: make fields private and provide protected access.
class Book{
string title, author;
int numPages;
protected:
string getTitle() const;
void setAuthor(string auth);
...
public:
Book (...);
bool isItHeavy() const;
...
};Relationship among Text, Comic, Book is called “is-a”
- a Text is a Book
- a Comic is a Book
- protected: #
Method isItHeavy - when is a book heavy?
- for ordinary Books - > 200 pgs
- for Text - > 500 pages
- for Comics - > 30 pages
class Book{
...
protected:
int numPages;
public:
...
bool isItHeavy() const {return numPages > 200;}
};
class Comic: public Book{
...
public:
...
bool isItHeavy() const {return numPages > 30;}
};
class Text: public Book{
...
public:
...
bool isItHeavy() const {return numPages > 500;}
};
Book b{"A small book", "...", 50};
Comic c{"A big comic", "...", 40};
cout << b.isItHeavy() //false
<< c.isItHeavy() //trueSince a Comic “is a” Book, we can do this:
Book b = Comic{"A big comic", "...", 40};Q: Is b heavy?
Which isItHeavy runs: Book::isItHeavy, or Comic:isItHeavy ?
A: NO - b is not heavy. Book::isItHeavy runs.
Why?
Since I’ve allocated only enough space for a Book and Comic is bigger, I must treat b as a book no matter what.
Book b = Comic{...};
//tries to fit a Comic object where there is only space for a Book object. What happens? - slicing occurs - c++ makes comic fit by chopping off bits. Hero field is chopped off so comic is coerced into a Book.So this converts the comic into a Book and Book::isItHeavy runs.
When accessing objects through ptrs, slicing is unnecessary and doesn’t happen.
Comic c {...,...,40,...};
Book *pb = &c;
Comic *pc = &c;
cout << pc -> isItHeavy(); //true
<< pb -> isItHeavy(); //not heavystill Book:isItHeavy runs when we access pb->isItHeavy().
Same object behaves differently, depending on what kind of ptr points at it.
Compiler uses the type of the pointer (or reference) to determine which isItHeavy to run. - does not consider the actual type of the object
Means a comic is only a comic when pointed at by a comic ptr -proabably not what we want.
How do we make comic act like a Comic, even when pointed at by a Book ptr?
Declare the method virtual
class Book{
...
public:
Book (...);
virtual bool isItHeavy() const {...};
...
};
class Comic: public Book{
...
public:
Comic(...);
bool isItHeavy() const override{...}
...
};
Comic c {...,...,40,...};
Book *pb = &c;
Book &rb = c;
Comic *pc = &;
cout << pc->isItHeavy() //true
cout << pb->isItHeavy() //true
cout << rb.isItHeavy() //trueE.g.
My Book Collection:
Book *myBooks[20];
...
for(int i = 0; i < 20 ; ++i){
cout << myBooks[i] ->isItHeavy() << endl; // uses the right isItHeavy for corresponding types. :D
}Accommadates multiple types under one abstraction
-polymorphism (“many forms”)
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};
};You don’t have to delete X. X’s dtor will run after Y automatically since it’s the superclass.
X *myX = new Y{10, 20};
delete myX; //- leaks, why? X's dtor ran, but myX points to a Y. Y's dtor never runs here.So only x, but not y is freed.
How can we ensure that deletion through superclass ptr will call subclass dtor?
- declare the dtor virtual
class X{
...
public:
...
virtual ~X(){
delete x;
}
};ALWAYS - make the dtor virtual in classes that are meant to have subclasses
-even if the dtor doesn’t do anything
If a subclass is NOT meant to have subclasses, declare it final:
class Y final: public X{
...
};class Student{
protected:
int numCourses;
public:
virtual int fees();
};2 Kinds of Student: Regular + Co-op
class Regular: public Student{
public:
int fees() override; //reg student fees
};
class Coop: public Student{
public:
int fees() override; //coop student fees
};What should we put for Student fees?
Not sure - every student should be regular or co-op
Can explicitly give NO implementation to Student::fees()
class Student{
public:
virtual int fees()=0; //this syntactically tells that this method has no implementation(***). no, 1,2,3 ... etc doesn't work. Called a pure virtual method
}A class with pure virtual methods cannot be instantiated.
Student s; X-called an abstract class
Purpose of an abstract class is to organize subclasses.
Subclasses of an abstract class are also abstract unless they implement the pure virtual methods.
If a class is not abstract, then it is concrete
class List{
struct Node;
Node *theList;
...
}
struct List::Node{
int data;
Node *next;
...
}What if you want to store something else?
Whole new class?
OR a template : A class parameterized by a type
template <typename T> class Stack{
int size;
int cap;
T *contents;
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>> l2;
l1.addToFront(3);
l2.addToFront(l1);
for(List<int>::Iterator it=l1.begin();it!=l1.end();++it){
cout << *it << endl;
}or indeed:
for(auto n:l1){
cout << n << endl;
}Large # of useful templates:
Eg: dynamic-length arrays : vectors
#include<vector>
using namespace std;
vector <int> v{4,5}; // [4, 5]
vector <int> v1(4,5); // [5, 5, 5, 5]
//oh no!
v.emplace-back(6);
vemplace.back(7); //4,5,6,7Looping:
for(int i=0;i<v.size();++i){
cout <<v[i]<<endl;
}
//CAN REPLACE vector<int>::reverse.iterator WITH AUTO FOR ALL OCCURRENCES
for(vector<int>::iterator it=v.begin();it!=v.end();++it){
cout << *it <<endl;
}
//OR
for(auto n:v){
cout << n << endl;
}
//To iterate in revers:
for(vector<int>::reverse.iterator it=v.rbegin(); it!=v.rend(); ++it){
cout << *it << endl;
}
v.pop.back() //remove last elementuse iterators to remove from inside a vector
auto it = v.erase(v.begin()); //erases the first element
auto it = v.erase(v.begin()+3); //erases item 3
auto it = v.erase(it); //erases item pointed at by it. returns an iterator to item past the item just removed.
auto it = v.erase(v.end()-1);
v[i] //- returns ith element of v; it's unchecked so if you go out of bounds.
// it's undefined behaviour.
v.at(i) //- checked version of v[i] . What happens when you go out of bounds?What should happen?
But we can write handlers to catch ex’ns + deal with them.
vector<T>::at raises the exn std::out_of_range when it fails
We can handle it as follows:
#include <stdexcept>
...
try{
cout << v.at(1000) <<endl; //out of range
}
catch(out_of_range r){
cerr <<"Range error " << r.what() <<endl;
}From midterm
int x = 5;
int y{x};
y+x;
cin << x;
//here, {x}, {x, x}, {x, y}, {cin, x, cin<<x} are lvalues.
// y+x is rvalue;Now consider:
void f(){
throw out_of_range{"f"}; //raise an exception. "f" is displayed in .what()
}
void g() {f();}
void h() {g();}
int main(){
try{
h();
}
catch (out_of_range r){...}
}What is out_of_range? - A class.
throw out_of_range{"f"} //ctor call, create an out_of_range object and throw itA handler can do part of the recovery job - execute some corrective code + raise another exn:
try{...}
catch(SomeErrorType s){
...
throw SomeOtherError{"..."};
}or throw the same ex’n
try{...}
catch(SomeErrorType s){
...
throw;
}throw; vs throw s;
throw s;
Throw s; -> s may be a subtype of SomeErrorType. throws a new exn of type SomeErrorType
throw;
actual type of s is retained
A handler can act as a catch-all:
try{...}
catch(...){ //here, we LITERALLY PUT "..." to catch ALL exceptions
...
}You can throw anything you want - don’t have to throw objects
Define your own exception classes (or use appropriate existing ones) for your errors:
eg.
class BadInput{};
try{
int n;
if(!(cin >> n)) throw BadInput{};
}
catch(BadInput &s){ //in general: catch by reference
cerr << "input not well-formed" <<endl;
}Much more on exns later
Guiding Principle: Program to the interface, not the implementation
eg. Iterator Pattern
class AbstractIterator{
public:
virtual int&operator*()=0;
virtual AbstractIterator &operator++()=0;
virtual bool operator!=(const AbstractIterator &other)=0;
virtual ~AbstractIterator();
};
class List{
struct Node;
...
public:
class Iterator: public AbstractIterator{
...
};
...
};
class Set{
...
public:
class Iterator: public AbstractIterator{
...
};
...
};Then you can write code that operates over Iterators:
void foreach(AbstractIterator start, AbstractIterator end, void(*f)(int)){
while(start!=end){
f(*start);
++start;
} //-works over Lists and Sets.
}Eg: Publisher = spreadsheet cells. Observers = graphs. When cells change, graphs update.
Can have many different observer objects.
- subject should not need to know all the details.
Observer pattern:
Sequence of method calls:
Example: Horse races
Subject - publishes winners
Observers - individual bettors
class Subject{
vector<Observer *> observers;
public:
Subject();
bool attach(Observer *o){observers.emplace.back(o);}
void detach(Observer *o){observers.remove(o);}
void notifyObservers(){
for(auto &ob:observers) ob->notify();
}
virtual ~Subject()=0;
};
//IMPORTANT
Subject::~Subject(){}
/*
virtual destructor must ALWAYS be implemented, even if it is pure virtual.
*/
From last class
class Subject{
vector<Observer *> observers;
public:
Subject();
bool attach(Observer *o){observers.emplace.back(o);}
void detach(Observer *o){observers.remove(o);}
void notifyObservers(){
for(auto &ob:observers) ob->notify();
}
virtual ~Subject()=0;
};
Subject::~Subject(){}class Observer{
public:
virtual void notify()=0;
virtual ~Observer();
};
Observer::~Observer(){}
class Horserace: public Subject{
ifstream in; //source of data
string lastwinner;
public:
HorseRace(const string &source): in{source}{}
bool runRace(); //set lastwinner. Returns false if no winners left
string getState() {return lastwinner;}
};
class Bettor: public Observer{
HorseRace *subject;
string name, myHorse;
public:
Bettor(...)...{
subject->attach(this);
}
~Bettor(){subject->detach(this);}
void notify(){
string winner = subject->getState();
if(winner == myHorse){
cout << "Yay!" << endl;
}
else{
cout << "Double or nothing" << endl;
}
}
};
//main.cc
HorseRace hr;
Bettor Larry(&hr, "Larry", "RunsLikeACow");
...
while(hr.runRace()){
hr.notifyObservers();
}Want to enhance an object at run-time-add functionality/features
E.g. Windowing system: -start with a basic window. -add scrollbar. -add menu.
Want to choose these enhancements at runtime.
Therefore, Every Decorator IS a component, AND every Decorator HAS a component
E.g. Window with scrollbar is a kind of window, and has a pointer to the underlying plain window
Window with scrollbar + menu IS a window, has a ptr to window w/ scrollbar, which has a ptr to a plain window.
All inherit from Abstract Window class, so window methods can be used polymorphically on all of them.
E.g Pizza
Basic Pizza is crust and sauce
class Pizza{
public:
virtual float price()const=0;
virtual string desc()const=0;
virtual~Pizza();
};
class CrustAndSauce:public Pizza{
public:
float price() const override{return 5.99;}
string desc() const override{return "Pizza";}
};
class Decorator: public Pizza{
protected:
Pizza *component;
public:
Decorator(Pizza *p): component{p}{}
virtual ~Decorator{delete component;} //what happens in delete component here is the whole pizza is thrown away. Uh, this is the choice we made to keep things simple
};
class StuffedCrust: public Decorator{
public:
StuffedCrust(Pizza *p): Decorator {p}{}
float price() const override{
return component->price() + 2.69;
}
string desc() const override{
return component->desc() + " with stuffed crust";
}
};Use:
Pizza *p1= new CrustAndSauce;
p1 = new Topping ("Cheese", p1);
p1 = new Topping("Jelly Beans", p1);
p1 = new StuffedCrust(p1);
cout << p1->desc() << " " << p1->price();
delete p1;class Book{
//Defines copy/move ctor, copy/move operator=
};
class Text: public Book{
...
public:
//does not define copy/move operations
};
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 (ie default behaviour) for Text part
-same for other operations
To write your own operations:
Text::Text(const Text &other): Book{other},topic{other.topic}{}
Text &Text::operator=(const Text &other){
Book::operator=(&other);
topic=other.topic;
return *this;
}
//other points at an rvalue, but IS ITSELF an lvalue
Text::Text(Text &&other):Book{other}, topic{other.topic}{}
//HERE, Book{other} is a copy ctor because other is an lvalue. It exists and has a name within this function
//Better but still not correct: move treats other as an rvalue.
Text::Text(Text &&other):Book{std::move(other)}, topic{other.topic}{}
//HERE, other.topic is ALSO an lvalue.
//Final:
Text::Text(Text &&other):Book{std::move(other)}, topic{std::move(other.topic)}{}
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 (so is other.topic).
std::move(x) forces an lvalue x to be treated as an rvaluem so that “move” versions of the operations run. What we did above is equivalent to DEFAULT behaviour
Text t1 {...}, t2{...};
Book *pb1=&t1, *pb2=&t2;What if we do *pb1 = *pb2;
Partial assignment - copies only the Book part.
- only Book::operator= ran.
How can we fix this? Try making operator= virtual.
class Book{
...
public:
virtual Book &operator=(const Book &other){...}
};
class Text:public Book{
...
public:
Text &operator=(const Text &other) override {...}
//this WONT WORK. Parameters don't match
};
//better
class Text:public Book{
...
public:
Text &operator=(const Book &other) override {...}
//Note: Different return types OK. (as long as you return a subtype by reference) but the parameter types must be the same or it's not an override and won't compile.
};Params not matching => violates is-a
Assignment of a book object to a text variable would be allowed
Allowed:
Text t{...};
Book b{...};
Text *pt=&t;
Book *pb=&b;
*pt=*pb; //- uses a Book to assign a Text BAD (but it compiles).
//Also
Comic c{...};
Comic *pc=&c;
*pt=*pc; // REALLY BAD, but compilesIf operator= is non-virtual. -partial assignment through base class ptrs.
If it is virtual, then the compiler allows mixed assignment
Recommendation - All superclasses should be ABSTRACT
Rewrite Book hierarchy:
class AbstractBook{
string title, author;
int numPages;
protected: //prevents assignments through base class ptrs from compiling but still makes the implementation available to subclasses.
AbstractBook &operator=(const AbstractBook &other);
public:
AbstractBook(...);
virtual ~AbstractBook()=0;
};
class NormalBook: public AbstractBook{
public:
NormalBook(...);
~NormalBook();
NormalBook &operator=(const NormalBook &other){
AbstractBook::operator=(other);
return *this;
}
};
//other classes - exercise-Operator= is not virtual therefore no mixed assignment
NormalBook n1{...}, n1{...}
Abstract *pa1 = &n1, *pa2=&n2;
*pa1 = *pa2 //won't compile. AbstractBook::operator= here is protected so client can't call it. No partial assignment-Write a video game with two kinds of enemies: turtles and bullets
- system randomly sends turtles and bullets, but bullets become more frequent closer to the end
UML
Never know exactly which enemy comes next, so can’t call turtle/bullet ctors directly.
Instead, put a factory method in level that creates enemies.
class Level{
public:
virtual Enemy *createEnemy()=0;
...
};
class NormalLevel: public Level{
public:
Enemy *createEnemy() override{
//create mostly turtles
}
};
class castle: public Level{
public:
Enemy *createEnemy() override{
//mostly bullets
}
};
Level *l = new NormalLevel;
Enemy *e = l->createEnemy();Want subclasses to override superclass behaviour, but some aspects must stay the same.
E.g. There are red turtles + green turtles
class Turtle{
public:
void draw(){
drawHead();
drawShell();
drawFeet();
}
private:
void drawHead();
void drawFeet();
virtual void drawShell()=0;
};
class RedTurtle:public Turtle{
void drawShell()override{/*draw red shell */}
};
class GreenTurtle: public Turtle{
void drawShell()override{/*draw green shell */}
};subclasses can’t change what it means to draw a turtle (ie. head, then shell, then feet)
but CAN change the way the shell is drawn
Extension: The Non-Virtual Interface (NVI) idiom.
A public virtual method is really two things:
an interface to subclasses
-a”hook” to insert specialized behaviour
Hard to separate these ideas if they are tied to the same f’n
What if you later want to separate the customizale behaviour into 2 f’ns with some unchanging code inbetween, while still providing clients the same interface?
The NVI idiom says:
Example:
class DigitalMedia{
public:
virtual void play()=0;
};
//instead, do this:
class DigitalMedia{
public:
void play(){doPlay();} //can add before/after code. eg check copyright before. Update play count after.
private:
virtual void doPlay()=0;
};Extends Template Method
-put every virtual method inside a template method
E.g. “arrays” that map string to int
#include <map>
map <string, int>m;
m["abc"] = 1;
m["def"] = 4;
cout << m["ghi"] << endl; //if key is not present, it is inserted and the value is default constructed (for ints, 0)
m.erase("abc");
if(m.count("def")) ... //0 if found, 1 if not foundRecall: <map>
map<string, int> m;
Iterating over a map: sorted key order
for(auto &p:m){
cout << p.first << " " << p.second << endl;
}p’s type is std::pair<string,int>& (<utility>)
For implementation, double dispatch
e.g
-effect depends on type of Enemy and type of weapon
Want something like: virtual void(Enemy, Weapon)::strike(); which is impossible
If we put this method in Enemy - choose based on enemy but not on the weapon.
If we put it in weapon - choose based on weapon but not enemy.
To get dispatch based on both (double dispatch):
-combine overriding with overloading
class Enemy{
virtual void beStruckBy(Weapon &w)=0;
};
class Turtle: public Enemy{
void beStruckBy(Weapon &w) override{
w.strike(*this);
}
};
class Bullet:public Enemy{
void beStruckBy(Weapon &w) override{
w.Strike(*this);
}
};
class Weapon{
virtual void strike(Turtle &t)=0;
virtual void strike(Bullet &b)=0;
};
class Stick: public Weapon{
void strike(Turtle &t) override{
//strike Turtle with stick
}
void strike(Bullet &b) override{
//bullet with stick
}
};
Enemy* e = new Bullet{...};
Weapon*w = new Rock{...};
e->beStruckBy(*w); //what happens?
//virtual mthd of Enemy. Bullet::beStruckBy calls Weapon::strike
//chosen at compile-time - virtual
//resolves to Rock::Strike(Bullet &) Visitor can be used to add functionality to existing classes, without changing or recompiling the classes themselves
Eg. add a visitor to the Book hierarchy:
class Book{
public:
virtual void accept(BookVisitor &v){v.visit(*this);}
};
class Text: public Book{
public:
void accept(Book Visitor &v) override{
v.visit(*this);
}
};
class BookVisitor{
virtual void visit(Book &b) = 0;
virtual void visit(Text&b) = 0;
virtual void visit(Comic &b) = 0;
};Application:
Track how many of each type of book we have:
Books - by author
Texts - by topic
Comics - by hero
Use a map <string, int>
Could add virtual updateMap (…) to each class or write a visitor
class Catalogue: public BookVisitor{
map<string, int> theCatalogue;
public:
map<string,int> getCatalogue(){return theCatalogue;}
void visit(Book &b) override{
++theCatalogue[b.getAuthor()];
};
void visit(Text &b) override{
++theCatalogue[b.getTopic()];
};
void visit(Comic &b) override{
++theCatalogue[b.getHero()];
};
};but it won’t compile! why?
main -> includes book - includes Book Visitor -> inclodes both Text and Book
-circular include dependency
Text doesn’t know what Book is
How many of these includes are really needed?
Compilation Dependencies - include vs forward declare
Consider class A{...};
//B needs #includes A
class B: public A{
...
};
//C needs #include A
class C{A my A;};
//D doesn't need to know how big A is therefore doesn't need #include
//can get away with just `class A`;
class D{A *myAp;};
//E needs #include A
class E{
A f(A x)
};Don’t introduce unnecessary compilation dependencies with unneeded includes
When A changes - only A,B,C need recompilation
Now, in the implementations of D,E;
//d.cc
#include "A.h"
void D::f(){
myAp->someMethod(); //Need to know about class A here
}Do the #include in the .cc file instead of the .h file. (will never get an include cycle because .cc is never included) where possible.
Now consider the XWindow class
class XWindow{
//this is private data here. Yet we must look at it. Do we know what it means? Do we care?
Display *d;
Window w;
int s;
GC gc;
unsigned long colours[10];
public:
...
};If we add or change a private member, all clients must recompile. May be better to hide these details away.
Sol’n:
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
//No need to include Xlib.h. Forward declare the impl. class
class XWindowImpl;
class XWindow{
XWindowImpl *pImpl;
public:
...
//no change
};No compilation dependency on XWindowImpl. Clients also don’t depend on XWindowImpl.h
//Window.cc
#include "window.h"
#include "XWindowImpl.h"
XWindow::XWindow(...): pImpl{newXWindowImpl{...}}{}Other methods: replace fields d,w,s, etc.
with pImpl->d, pImpl->w etc
If all private fields are in XWindowImpl, then only window.cc needs recompiling if they change.
Generalization - Several possible window implementations
e.g. XWindows YWindows - Then Impl struct could be a superclass
Bridge Pattern
<utility>)<algorithm> High coupling: changes to one module require greater changes to other modules.
- harder to reuse individual modules
Low cohesion: poorly organized code. Hard to understand/maintain.
Goal: low coupling, high cohesion
Your primary program classes should not be printing things
Eg.
class ChessBoard{
...
cou << "Your move" << endl;
};Bad design - inhibits code reuse
What if you want to reuse ChessBoard, but not have it communicate via stdout?
One solution: give the class stream objects where it can send it’s input/output
class ChessBoard{
std::istream ∈
std::ostream &out;
public:
ChessBoard(std::istream &in, std::ostream &out): in{in}, out{out} {...}
...
out << "Your move" <<endl;
};Better - but what if we don’t want to use streams at all? Your chessboard class should not be doing any communication at all.
“A class should have only one reason to change.”
Better - Communicate with the chessboard via params/results
Q: Should main do all of the communication and then call chessboard methods?
A: No - hard to reuse code if it’s in main. Should have a class to manage interaction that is separate from the game state class.
Separate the distinct notions of the data (state), its presentation, and the control of the data.
Model: the data (game state)
View: how the model is displayed
Controller: how the model is manipulated
Model :
Controller
By decoupling presentation + control, MVC promotes reuse
Consider:
void f(){
MyClass *p = new MyClass;
MyClass mc;
g();
delete p;
}No leaks - but what if g raises an exception?
What is guaranteed
So if g throws, p is leaked.
void f(){
MyClass *p = new MyClass;
MyClass mc;
try {
g();
}
catch(..){
delete p;
throw;
}
delete p;
}This is tedious, error-prone and code duplication
How else can we guarantee that something like delete p will happen no matter how we exit f? (normally or exn?)
In some languages - “finally” clauses that guarantee final actions - not in c++
Only thing you can count on in C++
- dtors for stack-allocated data will run
Use stack-allocated data with dtors as much as possible
Use this guarantee to your advantage
Every resources should be wrapped in a stack-allocated object whose dtor frees it.
E.g. files:
ifstream f{"name"}; //Acquiring the resource ("name") = initializing the object (f). File is guaranteed to be freed when f is popped from the stack because f's dtor runs.This can be done with dynamic memory
class std::unique_ptr<T>
//- Takes a T* in the ctor
//- The dtor will delete the ptr.A better f()
void f(){
auto p = std::make_unique<MyClass>();
// instead of auto, could also type, std::unique_ptr<MyClass>
// ctor arges for myClass in ();
MyClass mc;
g();
//no leaks, guaranteed
};Get 4/10 bonus marks if your program doesn’t leak and doesn’t call delete
Recall:
void f(){
auto p=std::make_unique<MyClass>();
MyClass mc;
g();
//No leaks
}Difficulty:
class c {...};
unique_ptr<C> p {new C{...}};
unique_ptr<C> q=p; //what happens here? when q/p is popped, may delete something twice :'(. XWhat happens when a unique_ptr is copied - don’t want to delete the same ptr twice!
Instead - copying is disabled for unique_ptrs
They can only be moved.
//Sample implementation (repository)
template <typename T> class unique_ptr{
T *ptr;
public:
unique_ptr(T *p): ptr{p}{}
~unique_ptr() {delete ptr;}
unique_ptr(const unique_ptr<T> &other)=delete;
unique_ptr<T> &operator=(const unique_ptr<T> &other)=delete;
unique_ptr(unique_ptr<T>&&other):ptr{other.ptr}{other.ptr=nullptr;}
unique_ptr<T> &operator=(unique_ptr<T>&&other){
using std::swap;
swap(ptr, other.ptr);
return *this;
}
T &operator*(){return *ptr;}
};If you need to copy ptrs + can’t distinguish an owner - std::shared_ptr
{auto p1=std::make_shared<MyClass> ();
if(...){
auto p2=p1;
} //p2 is popped, ptr is not deleted
}//p1 is popped, ptr is deletedShared ptrs maintain a reference count
(define l1(cons 1 (cons 2 (cons 3 empty))))
(define l2(cons 4 (rest l1)))Use shared + unique ptrs as much as possible
Dramatically fewer opportunities for leaks
NEVER let the dtor emit an exception
- if the dtor was executed during stack unwinding while dealing with another exn, you now have TWO active, unhandled exns and the program will abort immediately
3 levels of exception safety for a f’n f:
1. Basic guarantee - if an exn occurs, the program will be in a valid state. Nothing leaked, nothing corrupted, class invariants maintained
2. Strong guarantee - if an exn is raised while executing f, the state of the program will be as it was before f was called.
3. No-throw guarantee - f will never throw an ex’n and 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 C::f exn safe?.
- if a.method1 throws, nothing has happened yet. OK
- if b.method2 throws, effects of method1 would have to be undone to offer the strong guarantee. Very hard or impossible if method 1 has non-local side effects.
- So no, probably not exn safe.
If A’s method1 and B’s method2 do NOT have non-local side effects, can use COPY + SWAP.
class C{
...
void f(){
A atemp=a; // if these throws, f throws. Original A and B are still intact.
B btemp=b;
atemp.method1();
btemp.method2();
a=atemp;
b=btemp;
//If these throw, f throws, but original a + b still intact. HOWEVER, what if copy assignment throws?
}
};Better if the swap was nothrow. Copying ptrs can’t throw
Sol’n. Use the pImpl idiom:
struct CImpl{
A a;
B b;
};
class C{
unique_ptr<CImpl> pImpl;
...
void f(){
auto temp = make_unique<CImpl>(*pImpl);
temp->a.method1();
temp->b.method2();
std::swap(pImpl. temp); //no-throw
}
};If either A::method1 or B::method2 offer no exn safety guarantee, then neither can f.
Vectors - encapsulate a heap-allocated array
-follow RAII - when a stack-allocated vector goes out of scope, the internal heap-allocated array is freed
void f(){
vector <MyClass> v;
...
} //v goes out of scope - array is freed, MyClass dtor runs on all objects in the vector.But:
void g(){
vector<MyClass *> v;
...
}//array is freed but pointers don't have dtors so any objects pointed to by the pointers are not deleted (potential to leak)for(auto x:v) delete x;But:
void h(){
vector<shared_ptr<MyClass>> v;
...
//array is freed, shared_ptr dtors run. So the objs ARE deleted if no other shared ptr points at them. NO explicit deallocation.
}vector<T>::emplace_backBut:
BUT:
If the move ctor offers the nothrow guarantee, emplace_back will use the move ctor; else it will use the copy ctor, which is slower. So your move ops should provide the no-throw guarantee, and you should indicate that they do:
class MyClass{
public:
MyClass(MyClass &other) noexcept{...}
MyClass &operator=(MyClass &&other) noexcept;
};If you know a function will never throw or propagate an exception, declare it noexcept. This facilitates optimization.
At minimum: moves + swaps should be noexcept
In C:
Node n;
int *ip=(int *) &n; //cast - forces c++ to treat a Node * as an int*C-style casts should be avoided in C++
If you must cast, use a C++-style cast:
4 Kinds:
void f(int i);
void f(double d);
f(static_cast<int>(d));superclass ptr->subclass ptrBook *b = new Text{...};
Text *t = static_cast<Text *>(b);Student s;
Turtle *t = reinterpret_cast<Turtle *> (&s);The only C++ cast that can cast away const
//Won't compile if you just call g(p) since g doesn't guarantee p stays the same
void g(int *p); //given to you
void f(const int *p){ // say you know that g will not modify *p - just not reflected in g's signature
...
g(const_cast<int *>(p));
...
}Book *pb;
...
static_cast<Text *> (pb)->getTopic(); //safe? dependsDepends on what pb actually points at. Better to do a tentative cast - try it + see if it succeeds.
Book *pb = ...;
Text *pt = dynamic_cast <Text *> (pb);If the cast works (pb REALLY points at a Text, or at a subclass of Text), now pt points at that object.
If the cast fails - pt will be nullptr
if(pt) cout << pt->getTopic();
else cout << "Not a text";Should be using smart ptrs - can we do the same on them?
Yes - static_pointer_cast, const_pointer_cast, dynamic_pointer_cast
Cast shared_ptrs to shared_ptrs
can use dynamic casting to make decisions based on an object’s RTTI(run time type information)
void whatIsIt(shared_ptr<Book> b){
if(dynamic_pointer_cast <Comic>(b)) cout << "Comic";
else if(dynamic_pointer_cast <Text>(b)) cout << "Text";
else cout << "Normal Book";
}Code like this is highly coupled to the book class hierarchy and may indicate bad design. Better - use virtual methods or write a visitor.
Note: dynamic casting only works on classes with at least one virtual method
The one I missed. Uhhh refer to pdf.
Distance to base class not always the same!
Diagram doesn’t look like A,BmCmD simultaneously - but slices of it do look like A,B,C,D
D d;
A*a = &d;//shifts the addressTherefore ptr assignment among A,B,C,D changes the address stored in the ptr.
template <typename T> T min(T x, T y){
return x<y? x: y;
}
int x=1, y=2;
int z=min(x,y); //T=int - Don't need to say min<int> because C++ can infer that T=int from the types of X and Y (Does not apply to template classes)If C++ cannot determine T, you can tell it: min<int>(x,y);
char w = min ('a','c'); //T = char
auto f = min(1.0,2.0); //T= floatfor what types T can min be used?
Recall:
void for_each(AbstractIterator start, AbstractIterator finish, int(*f)(int)){
while(start!=finish){
f(* start);
++start;
}
}Works as long as AbstractIterator supports !=, *, ++
f can be called as a f’n
Make these template arguments:
template<typename Iter, typename Func>
void for_each(Iter start, Iter finish, Func f){
while(start!= finish){
f(*start);
++start;
}
}Now Iter can by ANY type supporting !=, *, ++ (including raw pointers)
void f(int n){cout << n << endl;}
int a[] = {1,2,3,4,5};
for_each(a, a+5, f); //- prints the array<algorithm> librarytemplate<typename Iter, typename T>
Iter find(Iter first, Iter last, const T &val){
// returns iterator to first item in [first, last) matching T.
//or last, if not found;
}count - like find, but returns # of occurrences of val
template<typename InIter, typename OutIter>
OutIter copy(InIter first, InIter last, OutIter result){
// copies one container range [first, last)
//to another, starting at result
}
// Note: does not allocate new memory
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}
template<typename InIter, typename OutIter, typename Func>
OutIter transform(InIter first, InIter last, OutIter result, Func f){
while(first != last){
*result = f(*first);
++first;
++result;
}
return result;
}Eg:
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(), addI);
// w={3,4,6,8,12}How general is this code?
1. what can we use for Func?
2. what can we use for InIter/OutIter?
class Plus1{public: int operator()(int n){return n+1;}};Plus1 p;p(4); //produces 5transform(v.begin(), v.end(), w.begin(), Plus1());
//Generalize:
class Plus{
int m;
public:
Plus(int m): m{m}{}
int operator()(int n) {return n+m;}
};
transform(v.begin(), v.end(), w.begin(), Plus{1});Plus1, Plus - called function objects
Advantage of f’n objects - can maintain state
class IncreasingPlus{
int m=0;
public:
int operator()(int n){return n+(m++);}
void reset() {m=0;}
};
vector<int> v(5,0);
vector<int> w(v.size());
transform(v.begin(), v.end(),w.begin(), IncreasingPlus());
// w = {0, 1, 2, 3, 4}Consider: How many ints in 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 f’n even. If this were Racket, we’d use lambda.
Do the same here:
int x=count_if(v.begin(),v.end(),[](int n){return n%2==0;});
auto even = [](int n){return n%2==0;}
int f(decltype(even)){...} //whatever even's type is2 - Iterators -
Apply the notion of iteration to other data sources. eg. streams
#include <iterator>
vector <int>v{1,2,3,4,5};
ostream_iterator <int> out {cout, ","};
copy(v.begin(),v.end(),out); //prints 1,2,3,4,5,
vector<int> v{1,2,3,4,5};
vector<int>w;
copy(v.begin(),v.end(),w.begin()); //X won't work. Seg faultRemember - copy doesn’t allocate space in w. It can’t - it doesn’t even know that w’s iterating over a vector!
But what if we had an iterator whose assignment operator inserts a new item?
copy(v.begin(), v.end(), back_inserter(w));copies v to w, allocates space if necessary
The end.