Class1/2

—Input,Output
We’ll look at OOP from three perspectives:

  • Programmer’s perspective: how to structure program correctly & how to lower the risk of bugs
  • The compiler’s perspective: what does constructors actually mean & what must the compiler do to support them
  • The designer’s perspective How to use OOP tools to build systems(polymorphism, inheritance, encapsulation)

Intro to C++

Hello world in C:

1
2
3
4
5
#include<stdio.h>
int main(){
	printf("Hello world");
	return 0;
}

Hello world in C++:

1
2
3
4
5
6
import<iostream>;
using namespace std;
int main(){
	cout << "Hello world" << end;
	return 0;
}

Notes:

  • import, like #include, brings name and definition from other files, libraries, or modules into our code

  • import, was C++ new module system

  • #include<iostream> works too, but module system is preferred

    • #include is replaced by the contents of the header directly, while #import is only replaced by the contents of the header the first time that header is imported*

  • function main() MUST return int, void main(){} is not valid in C++

  • return statement return a status code to OS ($?: check last executed program’s status code)

    • can be omitted from main, default to return 0

  • cout and << are how you wish to stdout

    • this is the preferred way to do I/O in c++
    • stdio.h and printf is still available in c++

  • using namespace std

    • called a using directive
    • c++ organizes names into namespaces
    • without using namespaces std , you need to write std:: cout << "Hello world "<< std::endl"
    • std::

Input/Output

c++ comes with 3 built-in I/O streams:

  • cout: for writing to stdout
  • cerr: for writing to stderr (never buffered)
  • cin: for reading from stdin

Built-in Operators:

  • << put to, insertion operator(output)
  • >> get from extraction operator(input)
  • cout << __ << __ << __ << endl;
    • dates, expressions, literals
    • endl outputs an end of line, char and flushes the output buffer
  • cout << x operators “point” in the direction of data flow
  • cerr << x
  • cin >> x extract a value from stdin and put it into x

Example: read 2 int and print their sum

1
2
3
4
5
6
7
import <iostream>;
using namespace std;
int mian(){
	int x, y;
	cin >> x >> y;
	cout << x + y << endl;
}

Notes:

  • the >> operator tries to interpret the input data according to the type of variable
    • in this case, x as an int, so >> will expect to read chars that look like an int like 123 or -42 and assemble those chars into a value
    • it will stop reading when it sees characters that is not part of an integer(letter or space)
    • cin >>ignores leading whitespaces(spaces, tabs, newlines)
    • when reading from the keyboard, the program will pause waiting for the user input
    • pressing Enter causes the entered text to be submitted to the program (with \n)
    • Pressing ^D signals end of file, or end of input (without \n)

What if bad things happened?
- input doesn’t contain an int
- input is too large/small to fit in the variable
- input is exhausted(not enough input/data, i.e EOF) and get 2 int

The input operation fails, how can we test for this in our program?
- if read failed(for whatever reason), cin.fail() return true
- if EOF: cin:eof() will return true
- But not until attempted read fails

Example: read all int from stdin, echo to stdout, one per line, stop at EOF or bad input

1
2
3
4
5
6
7
8
int main(){
	int i;
	while(true){
		cin >> i;
		if(cin.fail()) break;  // checking for failure
		cout << i << endl; 
	}
}
1
2
3
4
5
6
7
8
9
int main(){
	int i;
	while(true){
		cin >> i;
		if(!cin) break; //cin variable is implicitly converted to a boolean value
		cout << i << endl;	
	}
	
}

cin converts to:

  • true if all good
  • false if the stream has had a read failure

Let’s take a closer look at ==>> operator:==

  • >> is C’s (and c++’s) right bitshift operator

    1
    2
    3
    4
    5
    6
    if a, b are ints, a >> b shifts a's bits to the right by b spots
    Eg:
    21 >> 3
    	= 2
    // 21 = 10101
    //2 = 10

  • the >> operator has two operants

    • cin which is a stream
    • a variable to receive the input data , in our example;

  • and it returns a result:

    • cin the same stream used as the first operand
    • it also has side effect

  • the fact that it returns a stream, is why we can chain a series of those together

    1
    2
    3
    4
    5
    cin >> x >> y >> z
    [cin >> x] -> cin
      = cin >> y >> z
       [cin >> y] -> cin
          = cin >> z
1
2
3
4
5
6
7
8
//Example 3: getting input and output to the screen 
int main(){
	int i;
	while(true) {
		if(!(cin >> i)) break; //reading int i and checking for failure
		cout << i << endl;
	}
}
1
2
3
4
5
6
7
8
// Example 4: 
int main(){
  int i;
  while(cin >> i){ // if we cannot get anymore input, then cin >> i is false
    cout << i << endl;
  }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Example 5: Read all from stdin, echo to stdout until EOF, skip non-integer input 
Version 1:
int main() {
	int i;
	while(true) {
		if (cin >> i) {
			cout << i << endl; // will be default printed as a decimal
			continue;
		}
		if (cin.eof()) break; // Done - EOF
		cin.clear(); // Read the stream's failure flag.The stream will not  function after failure until it do so 
		cin.ignore(); // Removes the offending character from the stream
	}


Version2:
int main() {
	int i;
	while(true){ 
		// if false, then something bad happened -> EOF, bad input
		if (!(cin >> i)){
			if (cin.eof()) break;
			cin.clear();
			cin.ignore();
		}else{
		cout << i << endl;
		}
	}
}

Notes:

  • clear() must come before ignore(). Called ignore() on a failed stream does nothing.
  • ignore() removes 1 char from the stream
  • ignore(count) removes count chars from stream
  • ignore(count '\n') removes count chars or everything up to and including newline character, whatever comes first

Formatted Output

1
2
3
4
cout << 95 << endl; //default print in decimal
cout << hex << 95 << endl; //print 95 as a hex (manipulator)

cout << 15 << endl; // gets printed out in hex until you set it back to decimal cout << dec << 15 << endl;

hex: I/O manipulator, put the stream into “hex mode”, all subsequent ints are printed in hex

1
cout << dec; //switch stream back to decimal mode

Example: print a dollar amount 

1
2
3
4
5
6
7
import <iostream>;
import <iomanip>;
int main() {
	double m = 10.9;
	//cout << setprecision(5) << 10.356278 << endl;
	cout << setw(10) << setfill('*') << right << fixed << setprecision(2) << m << endl;
}

Prints: xxxxx10.90(10 characters)
fixed : output fixed character of decimal places
Note:

  • use import <iomanip>

Class2

—string, file access

String

C strings: An array of char (char * or char[] ) terminated by a null char \0

  • must explicitly manage memory - allocate memory as strings get bigger
  • easy to overwrite the \0 at the end
  • one of the biggest sources of security vulnerability

C++ strings: built-in string data type

  • import <string>
  • intuitive, easy-to-use
  • string grow as needed(no need to explicitly manage memory)
  • safer to manipulate
1
2
3
string s1 = "Hello";
string s2 = "World";
string s3 = s1 + " " + s2; //concat, s3 needs to be defined already

String operations:

  • equality/inequality: == != s1 == s2 | s1 != s2
    • –> comparing strings NOT memory addresses
  • comparisons: < <= > etc. (lexicographic by default)
  • length: s.length() note this is O(1) –> string structure stores string length
  • concat:
    s3 = s1 + s2;
    s3 += s4;
  • individual char:
    s[0] // first character
    s[1] // second character
  • mutable:
    • s[0] = 'h';

Example:

1
2
string s;
cin >> s; // skip leading whitespaces, stop at reading white space.

what if we want the white space?

1
2
3
4
5
6
7
8
string s;
getline(cin, s); // getline(stream, stringvariable name) 

char c;
cin.get(c);
while(cin.get(c)){
	cout << c;
}
  • getine(cin, s)Read from current position, up to the next new line character \n into s, excluding \n
  • stream is a abstraction

File Streams:

  • read/write from/to a file instead of stdin/stdout
  • std::ifstream: a file stream for reading
  • std::ofstream: a file stream for writing
  • must import <fstream>

File access in C:

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
int main(){
	FILE *f = fopen("file.text", "r");
	char s[256];
	while(1) {
		fscan(f, "%255s", s);
		if(feof(f)) break;
		printf("%s\n", s);
	}
	fclose(f);
}

File access in C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import <iostream>;
import <fstream>;
import <string>;
using namespace std;

int main() {
    //Declare and initialize the file variable f, and opens the file
	ifstream f {"file.txt"};
	string s;
	while(f >> s){
		cout << s << endl;
	}
}
//file is closed automatically when the f variable goes out of space

Class 3

—string stream, overload, struct

Recall

1
2
3
4
5
6
7
8
9
10
11
12
13
import <iostream>;
import <fstream>;
import <string>;
using namespace std;

int main(){
	// Declaring + Initializing the istream variable f opens the file
	ifstream f {"file.txt"}; 
	string s;
	while (f >> s) {
		cout << s << endl;
	}
} // file is closed when f goes out of scope
  • where does the OS open and close file happen?
    • Declaring + Initializing the istream variable f opens the file ifstream f {"file.txt"};
    • variable has scope, so file is closed when f goes out of scope
  • Anything you can do with cin and cout, you can do with an ifstream and ofstream

String Stream

  • Extract data from chars in a string: std::istringstream
  • Send data to string as chars: std::ostringstream
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //Example1: convert # to string
    //easiest way to convert # to string is to print the # into string
    import <sstream>;
    string intToString (int n) {
    	ostringstream sock; //stream that writes to a string
    	sock << n;
    	return sock.str(); //extract the string

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//Example2: convert string to #
int main(){
	int n;
	while(true) {
		cout << "Enter a number" << endl;
		string s;
		cin >> s;
		// scope the isstringstream variable sock in if()
		if(istringstream sock {s}; sock >> n) break;
		cout << "I said, ";
	}
	cout << "You entered" << n << endl;
}

1
2
3
4
5
6
7
8
9
10
//Example revisited: Echo all #'s, skip all non-#'s
int main(){
	string s;
	while(cin >> s){
		int n;
		if(isstringstream sock{s}; sock >> n) cout << n << endl;
	}

}

Note:

  • if(isstringstream sock{s}; sock >> n) , here sock >> n could fail, but we don’t have to do the sock.clear() and sock.ignore(), we don’t have to worry about renewing it here cuz it is under the scope of if(), every loop the stream is a new one

  • abc123 456def789

Application: processing the command line

To accept cmd line args in C or C++, always give main the following parameters

1
2
3
4
5
6
7
int main(int argc, char *argv[]){...}
//argc: # of command line arguments(>=1 cuz it includes the program name itself)
//argv: array of c-style strings
	arg[0] = program name
	arg[1] = first arg
	...
	arg[argc] = null(the null terminator)
1
2
3
4
5
6
7
8
9
10
eg.:
./myprogram abc 123
args = 3
argv = 
|.|/|m|y|p|r|o|g|r|a|m|\0|
|a|b|c|\0|
|1|2|3|\0|
|\|

//these are C-Style Strings!!

Recommendations : convert to C++ style strings before processing
Example:

1
2
3
4
5
int main(int argc, char * argv[]){
	for(int i = 1; i <argc; i++){
		string arg = argc[i];
	}
}

Example: print the sum of all numeric args on the cmd line

1
2
3
4
5
6
7
8
9
10
int main (int argc, char * argv[]){
	int sum = 0;
	for (int i = 1; i < argc; i++){
		string arg = argv[i];
		int n;
		if(istringstream sock{arg}; sock >> n) sum += n;
		//echo # only
	}
	cout << sum << endl;
}

Default Function Parameters

1
2
3
4
5
6
7
8
void printFile(string name = "file.txt"){// default value is file.txt
	ifstream f{name};
	for(string s; f >> s) cout << s << endl;

}
// run program by writing: 
printFile(); //print from file.txt
printFile("myfile.txt"); // will be executed with myfile.txt

Note:

  • optional parameters must be last
  • int f(int n = 2, int y = 3, int z = 4) { }
    • f(0) → f(0, 3, 4)
    • f(1, 2) → f(1, 2, 4)
    • f() → f(2, 3, 4)
  • The missing parameter is supplied by the caller, not the function
    • Why?
      • The caller passes parameters by pushing them onto the stack
      • The function fetches the parameters by reading them from the stack from where they are expected to be
      • If an argument is missing, the function has no way of knowing that (cuz it fetches from the stack position) —> so the function would interpret whatever is in that position of the stack as the arg
    • So the caller must supply the extra parameter if it is missing
    • –> When you write printFile(); the compiler replaces with printFile("file.txt");
  • For the above reason, default arguments are part of a function’s interface, rather than its implementation
  • If you are doing separate compilation, defaults go in the interface file, not the implementation file

Overloading

Think of negate in C, apply negate to int, bool, needs two different functions
C:

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

whereas,
C++:
Functions with different parameter lists can share the same name(different # of parameters / different types)

1
2
3
//called overloading
int neg(int n) {return -n};
bool neg(bool b) {return !b};
  • Compiler chooses the correct version of neg for each function call based on # and type of args in the function call -> done at compile time
  • overloads must differ in # or types of arguments –> just different in the return type is not enough

We’ve seen this already:

  • >> , << + are overloaded
  • behaviour depends on types of args

structs

1
2
3
4
5
6
7
8
struct Node {
	int data;
	Node *next; 
	//in C it has to say struct Node *next
	//in C++ we don't have to say struct Node *next
};
//Don't forget the semicolon
//we got this from the designer of C

we are allowed to do

1
2
3
4
struct Node{
...
} n1, n2, n3; //n1 n2 n3 is in local scope
//we can create variables with struct, that's the purpose of the semi-colon

Why is this wrong?

1
2
3
4
struct Node{
	int data;
	Node next;
};

This says every node has a node in it

Constants

const int passingGrade = 50; const must be initialized

  • Declare as many constants as you can - it helps catch errors

Node n {5, nullptr}; -nullptr is syntax for null pointer in C++

  • Do not say NULL or 0 in this class!

Class 4

—constant, parameter passing, reference, dynamic memory

Constants

1
Node n {5, nullptr}, // Do not say NULL, use nullptr instead in C++
  • why?
    • imagine overload void f(int n) void f(int *p)
    • what does f(NULL) mean then?
    • So we have nullptr that is never a number in C++

const Node n2 = n \\ immutable copy of n

Parameter Passing

1
2
3
4
5
6
void inc (int n){ ++n;} 
int x = 5;
inc(x);
cout << x << endl; // We get 5 here
//Pass-by-value
//inc gets a copy of x, mutates the copy doesn't chang the original

Solution:
If a function needs to mutate an arg, pass a ptr

1
2
3
4
void inc(int *n){++*n;}
int x = 5;
inc(&x); //x's address
cout << x << endl; //6 --visible to the caller

Reference

Q: Why cin >> x and not cin >> &x ?
A: C++ has another ptr-like type — references
References - important 

1
2
3
4
5
6
int y = 10;
int &z = y; 

// z is an lvalue reference to y
// like a const ptr - similar to int *const z = &y
//z is pointing at y in a way that it can't point anywhere else (constant ptr)

Refs are like const ptrs with automatic dereferencing 

1
2
z = 12 (NOT *z = 12) // Now y = 12 !!(mutated)
int *p = &z --> gives the address of y

In all cases, z behaves exactly like y, z is an alias (“another name”) for y

Q: How can we tell when & means “reference” and when it means “address of” ?
A:Whenever & occurs as part of a type (eg. int &z), it always means reference
When & occurs in an expression, it means “address of” (or bitewise-end).

Things you can’t do with lvalue refs:
lvalue:
x=y, on the right hand side we care about the value(rvalue), on the left hand side we are interested in the location(lvalue); const can be considered lvalue to0; lvalue has to be something that denotes an address;

Things can’t do:

  • leave them uninitialized (e.g. int &x)
    must be initialized with something that has an address(an lvalue) since refs are ptrs
    int &x = 3; //doesn't work, it doesn't have an address
    int &x = y + z;
    int &x = y;
  • create a ptr to a reference:
    • int &*p;// p is a ptr to the reference to an int, illgeal
    • ref to ptr OK: int *& p; //legal
  • create a ref to a ref: int &&r = ... //ilegall
    • this means sth different (later)
  • create an array of refs : int &r[]={_,_,_}; //illegal

What you can do:

Pass as function parameters:

1
2
3
4
5
6
void inc(int &n) {++n; //no ptr dereference}
//&n is a const ptr to the arg (x), thus change will affect x

int x = 5;
inc(x);
cout << x << endl; //6

Why does cin >> x work?
Take x as a reference
istream & operator >> (istream &in, int &x);
Q: Why is the stream being taken of returned as a ref? And what does returning by ref mean?
A: Need a better understanding of the cost of parameter passing

Pass-by-value
eg: int f(int n){...} copies the arg, if the arg is big, copy is expensive

1
2
3
4
5
eg:
struct ReallyBig{...};
int f(ReallyBig rb){...} //This is a copy---slow 
int g(ReallyBig &rb){...} //an alias, fast, But could change rb in the caller
int n(const ReallyBig &rb){...} //-fast -no copy -param cannot be change

Pick reference over pointers:

  • Const - can’t change where the reference points to
  • Reference can never be NULL - no need to worry

What if a function does want to make changes to rb locally, but does not want these changes visible to the caller?

  • Then the function must make a local copy of rb:
    1
    2
    3
    4
    int k (const ReallyBig &rb){
    	ReallyBig rb2 = rb;
    	//mutate rb2;
    }
  • But if you have to make a copy anyway, it’s better to just use pass-by-value and have the compiler make it for you –maybe it can optimize something
  • Advice:
  • Prefer pass-by-const-ref over pass-by-value for anything larger than a ptr, unless the function needs to make a copy anyway–then use pass-by-value
  • Also:
    1
    2
    3
    4
    5
    6
    7
    8
    int f(int &n);   int g(const int &n);

    f(5); //illegal
    //can't initialize an lvalue ref(n) to a literal value (non-lvalue)
    //if n changes, can't change the literal 5

    g(5); //OK
    //since ref(n) can never be changed, the compiler allows this
    How? (important):
  • for as long as g is running, 5 is in stack, there is a place to point at
  • the 5 is stored in a temporary location(stack)
  • ref has something to point to
    –> so, putting const makes function more applicable

So, in the case of
istream &operator >> (istream &in, int &x);
the istream is passed and returned by reference to save copying;
This is important, because stream variables are not allowed to be copied

Dynamic Memory

C:

1
2
3
int *p = malloc(__* sizeof(int));
...
free (p);

Don’t use these in C++!!
Instead: new/delete
new/delete

  • type-aware
  • less error-prone
  • eg:
    1
    2
    3
    4
    struct Node{...};
    Node *np = new Node;
    ...
    delete np;
1
2
3
4
5
All local variables reside on the stack
- variables deallocates when they got out of the scope(stack is popped)
- Allocated memory resides on the heap
- remains allocated until delete is called
	- if don't delete all manually --> Memory Leak

Class 5

—return value, operator overload

Dynamic Memory Recall:

Dynamic memory allocation:
C:

1
2
3
4
5
int *p = malloc(10*sizeof(int));
p[0]=10;
p[1]=20;
free(p); //dangling pointer
p = NUll; //clear p so it doesn't have a value anymore

C++:
using new / delete 

1
2
3
4
5
int *p = new int; //create an int obejct on the heap, return a pointer to it
//for pointer
*p = 10;
delete p; //deallocate the memory of the int, p is still a "dangling pointer"
p = nullptr;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node *np = new Node; //create a node object on the heap and return a pointer
//np is stored in the stack and the node np points to is in the heap
np->data = 42;
(*np).data = 42;
delete np; //Deallocate the memory, np is a dangling pointer

main memory:
----------------------
operating syestem
and other programs
----------------------
your program                   
----------------------            
memory available to      
the prorgam                         
----------------------
  • All local variables are function parameters reside on the stack
    • variables deallocates automatically when they got out of the scope(stack is popped)
    • if they are pointers, the memory they point to is not deallocated automatically
  • Memory allocated with new resides on the heap
    • remains allocated until you call delete
    • if you don’t delete all allocated memory –> memory leak(this is an incorrect program)
  • Calling delete on the same pointer more than once is an error
    • program will crash: SEGV
  • Calling delete on a nullptr is harmless - safe and acceptable
  • Never call delete on a stack-allocated object –> program
    • will crash
1
2
3
4
5
6
ex:
Node n;
...
Node *p = &n;
...
delete p; //this causes a crash

Returning Values From Functions

Bad ways:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Return by value:
	Node getMeANode(){                    
		Node n;      ---> stack for getMeANode()
		...
		return n;           
	}
	----
	copy
	----
	Node n1 = getMeANode(); ----> stack for the calling function

Return by pointer:
Node *getMeANode(){
  Node n;
  ...
  return &n;
}
Node &n1 = getMeANode();
//BAD! We are returning a pointer to stack-allocated data, which is dead on return 

Return by Reference:
Node &getMeANode(){
	Node n;
	...
	return n;
}
Node &n1 = getMeANode(); //Also Bad
stack:
n1: n: | __ |

reference doesn’t have a value on its on, just an alias to an object
HOWEVER:

1
2
3
4
5
6
7
8
9
Recall the >> operator 
istream & operator >> (istream &in, int &n){
	...
	//Reads chars from input stream, inteprets them as an integer, and puts
	//the value into n
	...
	return in;
}

  • Why is it okay to return a reference here? istream &operator>>(istream &in, int &n)
    • main: cin >> n
    • the argument istream &in was already available to the caller of operator >> so returning a reference back to it is okay
    • cin and n are in main so when you return the istream, you are returning it in main, not out of scope when istream is finished

Correct Way

Return by Pointer(fixed):

1
2
3
4
5
6
Node *getMeANode(){
  Node *np = new Node;
  ...
  return np;
}
Node *n1 = getMeANode();

This version transfers ownership of that allocated memory to the caller of the function. The caller is responsible for calling delete (or transfer ownership to some other function).

Operator Overloading:

Allows us to use the built-in C++ operators with user-defined types we create:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct Vec{
	int x,y;
};

Vec operator+(const Vec &v1, const Vec &v2) { 
	// function won't change the values of the thing you are pointing to and 
	// can't change what it is pointing to because of &v1 
	Vec v{v1.x + v2.x, v1.y + v2.y}; 
	return v; 
}


Vec operator*(const Vec &v1, const int k){
	return {v1.x * k, v1.y * k}; //Alternate syntax
	//compiler knows it's a Vec because of the return type
}

Vec v1 = {1,2};
Vec v2 = {3,4}; 
Vec v3 = v1 + v2;  //uses the operator + function
Vec v4 = v1 * 10;  //uses the operator * function
Vec v5 = 10 * v1; //Does NOT work YET!  (i)
Vec v6 = (v1 + v2) * 10; //works, changing them together
//can't change the precedence of how the operation takes place
//without paratheses v2 * 10 will be operated first 
//ORDER MATTERS


fix (i)
Vec operator*(const int k, const Vec v){
	return v * k;  //Reusing a function already defined 
}


Vec v3 = operator + (v1,v2); //This works too

We can also overload >> and << operators:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//to output a vector
cout << v1; //(1,2) desired output format
ostream & operator << (ostream &out, const Vec &v){
	out << '(' << v.x << ',' << v.y << ')'; //endl means newline
	return out;
}


//to read a vector
istream & operator >> (istream &in, Vec &v){ //can't be const, need to update &v
	char p1, c, p2; //the format of vector we're gonna read
	int x, y;
	in >> p1 >> x >> c >> y >> p2;
	//check the data was formatted correctly
	if(!in.fail() && p1=='(' && c==',' && p2==')'){
		v.x = x;
		v.y = y; //update our vector parameter
	}
}

int main(){
	Vec v;
	cin >> v;
	cout << v;
}

Class 6

—modules, classes, methods, MIL

Modules and Separate Compilation

we can split programs into multiple modules, where each module provides both:

  • an interface:
    • type definition
    • prototype for functions
    • similar to .h class
  • an implementation:
    • full definitions for every provided function
    • similar to .cc class

File 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Example using Vec class from last class:
//interface(vector.cc)

export module vector;  //indicates that this is THE module interface file(can only be one,one per module)

export struct Vec{ //anything marked export is available for the client of the module to use
	int x;
	int y;
};

export Vec operator + (const Vec &v1, const Vec &v2); //function prototypes
export Vec operator * (const Vec &v, const int k);
export ...

File 2:

1
2
3
4
5
6
7
//implementation(vector-imple.cc)

module vector; //This file is part of module vector
//can have multiple implementation files per module

Vec operator + (...){...} //function implementations
Vec operator * (...){...}

File 3:

1
2
3
4
5
6
7
8
//client(main.cc)
import vector; //import the module; Note no <> (this is a user module, not a system module)

int main (){
	Vec v1{1,2};
	v1 = v1 + v1;
	...
}

Notes:

  • interface file start with export module ___
  • implementation file start with module ___
  • client file use import___
  • These lines must be the first lines(can only be precedence by comments)

compiled separately and is dependency order
g++20 -c vector.cc // complied module interface -> gcm.cache
g++20 -c vector-impl.cc // implementations can be compiled in either order
g++20 -c main.cc //

-c = compile only, do not link, do not create an executable, produces an object file(.o)

Link and create executable:
g++20 vector-impl.o main.o -o main //omit vector.o, the compiler goes to gcm.cache to find the details
Notes:

  • must compile in dependency order
  • build tool support for compiling in dependency order(e.g. make)-is still a work in progress
  • must compile the interface file(unlike header file, you will never ever compile header file)
  • must always compile system libraries/modules first

Example of modules with multiple implementation files in: …/lectures/05-separate

A –> B means A depends on B. If we were compiling we would need to compile B first

Benefits of modules over header files:

  • faster compilation
  • if a module A imports module B to use as part of its implementations, the module B constants are not exported to the clients of module A
  • modules can be imported in any order
  • you can use modules and header files together(often happens when upgrading a large system incrementally)

Classes

C++ allows you to put functions inside structs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Student{
	int assns, mt, final;
	float grade(){ //function inside a struct 
		return assns * 0.4 + mt * 0.2 + final * 0.4;
		//the fucntion can get the variables in the struct
	}
};

int main(){
	Student s1{60,70,80};
	Student s1{90,76,65};
	cout << s1.grade() << endl;
	cout << s2.grade() << endl;
}

Terminology:

  • class
    • A struct type that contains one or more functions.
    • The functions give the struct some behaviour
  • object
    • an instance of a class
    • Student is the class, s1 is the object {60, 70, 80} is the initialization
  • The function grade is called a member function or method
  • assns mt and final are called data members, or member fields(or field) or member variables

Sometimes the function body is written separately from the class definition:

1
2
3
4
5
6
7
8
9
10
11
12
struct Student{
	int assns, mid, final;
	float grade();
};

float Student::grade(){
	return assns * 0.4 + mid * 0.2 + final * 0.4;
}

int main(){
	...
}

the Student after float qualifies the function name
you can just export struct Student, no need to export grade function, cuz it belongs to the struct

Notes:

  • :: // called the scope resolution operator. Student :: grade means grade in the context of the class Student

  • The fields assns mt final are fields of the receiver objects - the objects upon which the grade method was called

    1
    s1.grade(); //method call; uses s1's data members

  • Formally, every method has a hidden extra parameter called this , which is a pointer (not a reference) to the receiver objects

We write:

1
2
3
4
5
6

float grade(){ //function inside a struct 
	return assns * 0.4 + mt * 0.2 + final * 0.4;
	//the fucntion can get the variables in the struct
}
cout << s1.grade();

The compiler rewrites our code as:

1
2
3
4
float grade(Student *this){
	return this->assns * 0.4 + this->mt * 0.2 + this->final * 0.4;
}
cout << s1.grade();

We can actually refer to this inside our function body:

1
2
3
4
5
6
struct Student {
	...
	float grade(){
		return this->assns ...;
	}
};

Special-Purpose Class Methods(Big 5):

These are methods you may need to implement in your classes:

  • constructors(ctor)
  • copy constructors(cctor, copy ctor)
  • destructors(dtor)
  • copy assignment operators
  • move constructors
  • move assignment operator

Constructors(initial objects)

Studnet s1{60, 70, 80}; //OK but limited
Student s2{-100, 1000}; //valid but doesn't create a valid student

  • No validation - negative numbers, numbers larger than 100
  • don’t have to specify a value for each field
  • puts the burden on the user of your class to initiate it correctly

A better approach is to write a method that initialize the object properly.
We call such a method a constructor(ctor for short)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct Student {
	int assns, mid, final;
	float grade(); //regular method
	Student{int assns, int mid, int final}; //constructor
};


struct Student::Student(int assns, int mid, int final) {
	this->assns = assns;
	this->mid = mid;
	this->final = final;
	   |             |
	//field      //parameter

//Recall this is a pointer to the reciever object Student *this
//if the parameter name different from field name, we don't need to use this
}

//The following are equivalent[stack allocated]
Student s {60, 70, 80};  //This causes the ctor to run
Student s = {60, 70 ,80};
Student s = Student {60, 70, 80};
Student s = Student (60, 70, 80);

//The following are equivalent[heap allocated]
Student *p = new Student{60, 70, 80};
Student *p = new Student(60, 70, 80);

A constructor method

  • has the same name as the class
  • has no return type(not even void)
  • can be defined with 0 or more parameters
  • the values in the {...} are passed as arguments to the constructor(ctor)
  • can have multiple constructors with different parameter list(i.e. real number, complex number)

Advantages of constructors

  • they’re functions
  • you can write initialization code that creates valid object that are ready to use
  • validate parameters
  • have default parameters
  • overloading –> multiple ctors with different sets of parameters

Default Values

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Student {
	...
	Student(int assns = 0, int mid = 0, int final = 0){ //Defaults
		this->assns;
		...
	}
};


Student s1 {60,70};  //60,70,0
Student s2 {60};  //60,0,0
Student s3 {};  //0,0,0
Student s4;  //same as s3

Every time calls the ctor. Whenever an object is created, a ctor is always called. If you don’t write your own ctor, the class automatically gets a default(i.e. a zero-argument) ctor. The default constructor, in turn, default-construct all of the fields that are objects(using the default ctor for each field)

1
Vec v; //default constructor is called

But the built-in default ctor goes away if you write any ctor

1
2
3
4
5
6
7
8
9
10
Student Vec{
	int x, y;
	Vec(int x, int y){
		this->x = x;
		this->y = y;
 	}
};

Vec v; //This is no 0-arg constructor anymore 
Vec v{1,2}; //OK

Now consider:

1
2
3
4
5
6
struct Basis{
	Vec v1, v2;
};
Basis b; //won't compile

//default ctor for Basis attempts to default-construct the field inside Basis that are objects. But the Vec class doesn't have a default ctor.

// Can we write our own? 

1
2
3
4
5
6
7
Struct Basis { 
	Vec v1, v2; 
	Basis () { 
		v1 = Vec{1,0}; 
		v2 = Vec{0,1);
	}
}; //this does not work

Member Initialization Lists (MIL)

Object Creation Steps
When an object is created:

  1. space is allocated
  2. fields are constructed in declaration order(the order in which they appear in class)
    1. Built-in types(int char bool etc.) are not initialized
    2. Class run for fields that are objects
  3. ctor body runs

Initialization of v1 and v2 needs to happen in step 2, not step 3. How?

MIL
We have to change our ctor to use a member initialization list

1
Basis::Basis():v1{1,0}, v2{0,1} {...}
  • MIL can only appear in a ctor
  • MIL appears between the parameter list and the ctor body
  • starts with a colon and is a comma-separated list of field initialization
  • must be in the ctor implementation(not prototypes)
  • can be used to initialize any types of fields (not just objects)
  • fields are initialized in declaration order, even if the MIL orders them differently
    • compiler warning
  • often the MIL does all the initialization and the ctor body can be empty

Using the default object values and the MIL together:

1
2
3
4
5
6
7
struct Basis{
	//if MIL doesn't supply a value for the field, these value will be used
	Vec v1{1,0}, v2{0,1}; 
	Basis () {} // uses defaults above
	Basis (const Vec &v1, const Vec &v2): v1{v1}, v2{v2}, {}
	//uses the parameters to initialize v1 and v2 if 2 vectors are given
}

Using MIL is sometimes more efficient than setting fields in the ctor body

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Student{
	int assns, mid, final; //not objects
	string name; //object
	Student (int a, ..., const string &n) {
		assns = a;
		...
		name = n; 
		// gets executed in step 3, must have done step 2
		// in step 2 it default constructed a string to empty 
		// in step 3 it reassigned name
		//(name is default constructed to an empty string in step2 and reassigned here)
	} 
	
	OR
	USE MIL:
	Student (int a, ..., const string &n): assigns{assns}, ... name{n} {} 
	// all the work is done in step 2 
	// name is assigned in initialization only once


}

MIL must be used:
- for fields that are objects with no default ctors(Vec example with Basis)
- fields that are const or references(because these cannot be re-assigned; must be initialized in step2)
—> MIL should be used as much as possible!

Class 7

—copy ctor, conversion, dtor

Copy Constructors

Consider:

1
2
3
Student s{60, 70, 80};
Student s2 = s;
Student s3 = {s}; //equivalent

How does this initialization happen?

  • the copy constructor
  • for constructing one object as an copy of another

Note: Every class comes with:

  • default ctor
    • lost if you write any custom constructor
  • copy ctor
  • copy assignment operator
  • destructor
  • move ctor
  • move assignment operator

Custome copy ctor

Building your own copy ctor:

1
2
3
4
5
6
struct Student{
	...
	//const Student, doesn't have to be const but good to do so
	Student (const Student &other): assns{other.assns}, mid(other.mid), final{other.final} {}
		
}; //equivalent to the defualt ctor we get for free

Deep Copy

When is the built-in copy ctor incorrect?
Consider:

1
2
3
4
5
6
7
8
9
struct Node{
	int data;
	Node *next;
};
//linked list
Node *n = new Node{1, new Node{2, new Node {3, nullptr}}};
Node m = *n;
Node *p = new Node{*n}; //p should be a pointer in the stack
//last two are copy ctor

Simple copy of fields->only the first node is actually copied(shallow copy)
If you want a deep copy (copied the whole list), must write your own copy ctor

1
2
3
4
5
6
7
8
9
10
11
12
struct Node{
	...
	Node (const Node &other):
		data{other.data}, 
		next{other.next? new Node {*other.next}: nullptr} {}
		//calls our copy ctor here at 'new Node{*other.next}'
		//recursively copies from the rest of the list
		//'new Node' allocate memory in heap and return a pointer, type Node*
		//so we need to do *other.next as a Node to be copied
		
	
}

The copy ctor is called:

  1. when an object is initialized by another object of the same type
  2. when an object is passed by value
  3. when an object is returned by value

The truth is more nuanced as we’ll se

Q: Why is this wrong?

1
2
3
4
sturct Node{
	Node (Node other): ....{...}
}
//this is passed by value, before you go to the copy ctor you have to go to the copy stor

A: Taking “other” by value implies that “other” is being copied, which means the copy ctor must be called before we can begin executing the copy ctor(infinity recursion).

Conversion constructor

Note: Careful with ctors that take one arg

1
2
3
4
5
6
7
8
9
10
11
12
Node{int data}:...
or
Node(int data, Node *next = nullptr): data{data}, next{next} {}
	
The single-argument ctor are called conversion constructors andn they create implicit conversions:
	int x;
	...
	Node n = x; //implicit conversion from int to Node

eg.
Node n{4};
-but also  Node n = 4; //equivalent

When have we seen this before?

1
2
3
4
string s = "Hello";
	  |           |
string object  const char*(c-style string)
-implicit conversion via single-arg ctor

What’s the problem?

1
2
void f(Node n),;
f(4); //works, 4 implicitly conversion to Node

Danger:

  • accidentally passing an int to a function expecting Node
  • silent conversion
  • compiler does not signal an error
  • potential errors not caught
    Don’t do things that limit your compiler’s ability to help you!
    Disable the implicit conversion - make the ctor explicit
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    struct Node{
    	...
    	explicit Node(int data, Node *next = nullptr): data{data}, next{next} {}
    	
    };

    Node n = 4; //now these implicit conversion give compiler errors
    f(4); //no

    //But these explicit conversion are okay
    Node n{4};

    f(Node{4}); //OK //this is saying that you want to pass by int
    Advice: Always use the explicit keyword on ctors that can be called with a single argument

Destructors

When an object is destroyed:

  • stack-allocated: goes out of scope
  • heap-allocated: is deleted

A method called the destructor runs

Classes come with a default dtor (just calls dtor for all the fields that are objects)
Object destruction steps:
When an object is destroyed, 3 steps happen
-in reverse declaration order(for fields that are objects)

  1. Dtor body runs
  2. fields that are objects - their dtors run in reverse declaration order
  3. space is deallocated

When do we need to write a dtor?
Node *np = new Node {1, new Node{2, new Node {3, nullptr}}};
If np goes out of scope:

  • the ptr is reclaimed(stack-allocated)
  • the nodes are leaked
    If we say delete *np
  • calls *np‘s dtor, which doesn’t do anything
  • The default destructor destroys the member variables. If the member variables have user defined destructors, they are called. If they are fundamental types, nothing happens.

Write a dtor to ensure the whole list is freed:

1
2
3
4
5
6
struct Node {
	...
	 ~Node(){delete next;} 
	//recursively calls *next's dtor; whole list is freed
};
delete np; //frees the whole list

What happens when you reach the nullptr at the end of the list

  • Deleting a nullptr is guaranteed to be safe(and do nothing). The recursion stops.

To declare a dtor:

  • start with a ~
  • same name as class
  • no return type
  • no parameters
  • can have only one dtor in class

if you write the dtor outside the struct:

1
2
3
Node::~Node(){ //make sure `Node::` is in the right spot
	delete next;
}

Dtors have an important role in C++ programs: they are guaranteed to run when an object is destroyed. Dtor often clean up or release resources their objects are holding onto.

Caution:

  • if you use the exit() function, dtors will not run
  • Valgrind will report memory leak

Class 8

—copy assignment operator, Rvalue, move assignment operator

Copy Assignment Operator

The goal of the copy assignment operator is to replace the data in an object with a copy of the data from another object of the same type , without introducing memory leaks.

1
2
3
4
5
6
7
Student s1{6,7,8};
Student s2 = s1;//copy ctor
Student s3; //default ctor
...
s3 = s1; //copy, but not construction
//`=` is copy assignment operator - uses ompiler-supplied default
//calls the copy assignment operator, s1's data is copied into s2(s2's old data is overwritten). s1 should be unchanged

The compiler provides a default copy assignment operator for every class.

Note: assignment NOT equal to construction
(cuz we have “old stuff” that we gotta deal with first)
may need to write your own

Node
Example:

1
2
3
4
5
6
7
8
9
10
Struct Node{
	...
	Node &operator=(const Node &other){
		data = other.data;
		delete next;
		next = other.next? new Node{*other.next}:nullptr;
		return *this;
	} //DANGEROUS!!

};

The above is DANGEROUS!!
Why?

1
2
3
4
Node n {1, new Node{2, new Node {3, nullptr}}};
n = n;
//delete n and tries to copy n to n
//undefined behaviour

When writing operator = , always make sure it works well in the case of self-assignment.
Revised:

1
2
3
4
5
6
7
8
9
10
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;
	} 
};

Student
For Student it would look like this: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Student {
	...
	Student &operator = (const Student &other){
		if (this == &other) return *this; 
		//protecting against self-assignment(i.e: s1 = s1)
		//`this` is a pointer to the recieving object
		//this == &other,  `this` and `other` points to the same object
		
		//copy member fields
		assns = other.assns;
		mid = other.mid;
		final = other.final;

		return *this; //return a reference to ourself 
	}
}

Q&A
Q: How big of a deal is self-assignment? How likely am I to write n = n?
A: Not that likely. But consider *p = *q if p $\neq$ q point to the same location. Or a[i] = a[j]if i, j happen to be equal(say in a loop). Because of aliasing, it is a big deal.

Q: What’s wrong with if(*this == other) as a check for self-assignment?
A: Exercise

Critiques of the revised version?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
	} 
};

//if malloc fail, it returns a null pointer
//but if new Node fail, the copy assignment operator would fail
//but the delete next has been executed

An even better implementation:
(want to do the copy before we do the delete)

1
2
3
4
5
6
7
8
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 temp;
		return *this;
	} //if new fails, we still have the old list

Alternative: copy-and-swap idiom

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import <utility>;
struct Node{
	...
	void swap(Node &other){
		std::swap(data, other.data);
		std::swap(next, other.next);
	}
	Node& operator=(const node &other){
		Node temp = other; //copy ctor
		swap(temp);
		return *this;
	}

};//dtor and ctor need to be defined for this method

Rvalues & Rvalues References

Recall:

  • an lvalue is anything with a address
  • an lvalue reference (&) is like a const ptr with auto-dereference - always initialized to an lvalue

Now consider:

1
2
3
4
5
6
7
8
9
10
11
12
13
Node OddsOrEvens(){
	Node odds {1, new Node{3, new Node {5, nullptr}}};
	Node evens {2, new Node{4, new Node {6, nullptr}}};
	char c;
	cin >> c;
	if (c == `0`) return evens;
	else return odds;
}


Node n = OddsOrEvens(); //this is a copy ctor
//copy ctor takes an `&other`
//what is the `other` here? reference to what?
  • compiler takes a temporary object to hold the result of OddsOrEvens()
  • other is a reference to this temporary
    • copy ctor deep copies the data from this temporary

BUT, the temporary is just gonna be discarded anyway, as soon as the statement Node n = OddsOrEvens(); is done.

  • wasteful to have to copy the data from the temporary
  • why not just steal it instead? and save the cost of a copy(“steal dying object stuff”)

What could possibly go wrong? - if the object is not “dying”:

  • Node n = OddsOrEvens(); vs Node n = m;
  • need to be able to tell whether other is a temporary object(which stealing would work), or a standard object(which we would have to copy)

C++ -11 introduced rvalue reference

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

Version of the ctor that takes a Node&&

1
2
3
4
5
6
7
8
9
struct Node {
	...
	Node(Node &&other): //called a move ctor //steal other's data
		data{other.data}; //integer assignment 
		next{other.next}; //pointer assignment 
	{
	other.next = nullptr;}

};

Similarly,

1
2
Node m;
m = OddsOrEvens(); //assignment from temporary

Move Assignment Operator:

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node{
	...
	Node &operator=(Node&& other){
	//steal other's data
	//destroy my old data
	//Easy swap without copy
		std::swap(data, other.data);
		std::swap(next, other.next);
		return *this;
	//temporary will be destroyed and take our old data with it
	}

};

If you don’t write a move ctor/assignment, the copying version of these operations will be used instead

Summary: Rule of 5(Big 5)

If you need to write any one of the Big 5(destructor, copy constructor, copy assignment operator, move constructor, move assignment operator), then you usually need to write all 5.

recall three important indicative understanding of CS246

  1. reference
  2. stack/heap
  3. ownership

But note that many classes don’t need any of these

  • the default implementation are fine
    What characterizes classes that need the big 5, typically?
  • ownership
    • these classes are usually tasked with managing something
    • often memory, but there are other things that need managing(resources)

Class 9

—copy/move elision, member/IO OPERATOR, array of/const/compare OBJECTS

Copy/Move Elision

1
2
3
4
5
6
7
8
9
Vec MakeAVec(){
	int x, y;
	cin >> x >> y;
	Vec v{x,y};
	return Vec v{x,y}; 
}

Vec v1 = makeAVec(); //What runs? copy ctor? move ctor?
//try it

Under the covers, the compiler makes v and alias(or a reference) to v1 so that they point to the same object. when v is constructed, it is directly constructed into th ememory where v1 lives. And when MakeAVec returns, no copying or moving is needed.

Answer:

  • just the basic ctor
  • no copy ctor, no move ctor
  • in certain cases, the compiler is required to skip calling copy ctor, move ctor
    In this example, MakeAVec writes its result ({0,0}) directly into the space occupied by v in the caller in main itself, instead of making a vec in MakeAVec() and moving it to main. This is called Copy/Move Elision

Another example:

1
2
3
4
5
6
e.g:

void doSomething(Vec v); // pass-by-value, copy or move ctor

doSomething(MakeAVec()); //result of MakeAVec written directly into the parameter v
//there is no copy or move involved

This behaviour is called copy/move elision, it’s an optimization technique that the compiler uses to eliminate unnecessary copying of object. This happens, even if eliminating the copy/move ctors changes the behaviour of the program(rg. if ctors print something)
You are not expected to know when exactly elision happens, just that it does happen

Member Operators

When an operator function is declared as a member function, then this object plays the role of the first operand(x * k not k * x).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Vec{
	...
	//v1+v2 ----[return new Vec objects]
	Vec operator+(const Vec&rhs) const{
		//Note the const designates that the method 
		//does not change the reciever object(leave the member data alone).
		
		return{x+rhs.x, y+rhs.y};//return by value
		
		//memebr functions automatically have access to member fields
	}
	//v * k ----[return new Vec objects]
	Vec operator *(const int k) const{
		return {x * k, y * k}; //return by value
	}

	//v1 += v2 ----[return updated Vec objects]
	Vec &operator += (const Vec &rhs){ //Note: not const
		x += rhs.x;
		y += rhs.y;
		return *this; //return by reference(main stack allocated,updated Vec obj)
	}
	
};

Note we did not implement k*v above, why? can’t be a member function because the first operand is not a Vec , so must be a standalone function.

Notes:
operator = is a member function of the class(method)
previous operators like operator+()we have written have been standalone functions

When an operator is declared as a member function, *this plays the role of the first(left) operand

1
2
3
4
5
6
7
8
9
10
11
12
e.g. of member function declaration

struct Vec{
	int x, y;
	...
	Vec operator+(const Vec &other){
		return{x + other.x, y + other.y};
	}
	Vec operator*(int k){
		return{x * k, y * k};  //this only works for v * k, not k * v
	}
};

How do we implement k * v ? Can’t be a member function, cuz first argument is not Vec, must b external:

1
2
3
Vec &operator*(const int k, const Vec &v){
	return v*k; //use the previous implemented member function
}

Advice: If you overload arithmetic operators, overload the assignment versions of these as well, and implement the former in terms of the latter.

I/O operators:

1
2
3
4
5
6
struct Vec {
	...
	ostream &operator << (ostream &out){
		return out << x << ' ' << y;
	}
};

What’s wrong with this?

  • NEED to make Vec the FIRST operand, not the second
  • SO Use as v << cout, but this is Confusing
  • w << (v << cout))

So defined <<, >> as standalone
Certain operators must be members:

1
2
3
4
5
operator=
operator[]
operator->
operator()
operator T (where T is a type)

Arrays of Objects

1
2
3
4
5
6
7
8
struct Vec{
	int x, y;
	Vec(int x, int y): x{x} y{y} {} //custome ctor, removes the defualt ctor 
};

Vec *vp = new Vec[10]; //heap allocated
Vec moveVecs[10];  //stack allocated 
//WRONG!!

These want to call the default constructor on each item(objects need to be initialized). If no default ctor(customized already)- can’t initialize the array items—error(objects in C++ need to be initialized)

Options:

  1. provide a default ctor
    1. this is not a good idea unless it makes sense for the class to have a default ctor
  2. For stack arrays(provide an initialization list to init each object)
    1. Vec moveVecs[3] = {{0,0}, {1,1}, {2,2}};
  3. For heap arrays - array of pointers
    1
    2
    3
    4
    5
    6
    Vec **vp = new Vec* [5];
    vp[0] = new Vec{...};
    vp[1] = new Vec{...};
    ...
    for (int i = 0; i < 5; ++i) delete vp[i];
    delete[] vp;
1
2
3
4
5
Vec **vp = new Vec[capacity]{nullptr};
//intialize the first object to nullptr and
//automatically initializes the rest of the array objects to 0
//and 0 is equivalent to nullptr
//nullptr is ONLY used to initialized the FIRST object

Const Objects

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

  • const objects arise often, especially as function parameters
    What is a const object?
  • an object where the fields cannot be mutated
    Can we call methods on const objects?
  • issue: the method may change fields, violate const
  • answer: YES, we can call methods that promise not to modify fields
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    eg:
    struct Student{
    	int assns, mid, final;
    	float grade() const; 
    	//this doesn't modify fields of objects called,
    	//so declare it const, this is a [const method]
    };

    floas Student::grade()const {
    	//the `const`suffix must appear 
    	//in both interface and implementation files
    	return ...;
    }
  • the constsuffix must appear in both interface and implementation files
  • compiler checks that const methods don’t modify fields
  • only const methods can be called on const objects

You get a compiler error if:

  • you write a const method on a non-const object
  • the code inside a const method tries to modify any fields

Advice: Any method that doesn’t update the object’s fields should be a const method(add the const key word) Then you can invoke those methods on const objects

One can mark certain fields as mutable:

1
2
3
4
5
6
7
struct Student{
	mutable int numMethodCalls = 0;
	fload grade()const{
		++numMethodCalls;
		return ...;
	}
};

mutable fields can be updated even if from a const method
But updating numMethodCalls affect only the physical constness of the object, not the logical constness

  • physical constness: whether the actual bits that make up the object have changed.
  • logical constness: whether the externally visible state of the object has changed.
  • use mutable to indicate that a field does not contribute to the logical constness of the object.

Comparing Objects

Comparing strings in C:

1
2
3
4
int result = strcmp(s1, s2); //char *s1, *s2
result = 0 if s1 == s2
	   > 0 if s1 < s2
	   < 0 if s2 < s1

String comparison in C++:

1
2
3
4
s1 == s2
s1 < s2
s1 > s2
s1 != s2

C++ version is easier to read, but you might need to do multiple comparisons

1
2
3
4
5
6
7
if (s1 == s2){  //compare 
	...
}else if (s1 < s2){ //compare 
	...
}else{
	...
}

C++ has a three-way comparison operator : <=>(a.k.a the spaceship operator)
s1 <=> s2 //returns a special value indicating less than, equal to, or greater than

Example:

1
2
3
4
5
6
import <compare>; //must import this

std::str0ng_ordering result = s1 <=> s2;
	
//note the return type std::strong_ordeirng

1
2
3
4
5
results:
std::strong_ordering::equal
std::strong_ordering::less
std::strong_ordering::greater
std::strong_ordering::equivalent (same as equal)

can also compare against 0 but only 0:

1
2
3
4
5
6
7
if(result == 0){ //s1 == s2
	...
}else if (result < 0){ //s1 < s2
	...
}else{ //s1 > s2
	...
}

Class 10

—compare objects, encapsulation, design pattern(iterator)

Side Note
C++ allows you to declare variables and function return types with the auto keyword:
auto result = s1 <=> s2;
//called automatic type declaration
In general:
auto x = expr; //declares x to have the type matching the value of expression

Comparing Objects(continued)

One can add support for <=> to our own classes:

1
2
3
4
5
6
7
8
student Vec{
	int x,y;
	auto operator<=>(const Vec& other)const{
		auto n = x <=> other.x;
		if (n != 0) return n;
		return y <=> other.y; 
	}
};

so now we can say:

1
2
3
Vec v1, v2;
...
auto result = v1 <=> v2;

By writing operator <=> we get the 6 relational operators, ==, !=, < <= > >= for free:
v1 <= v2 <=> (v1<=>v2) <= 0

We can sometimes also get operator<=> for free, well almost!
auto operator <=> (const Vec &other) const = default;

This automatically generates a default implementation which just compares the fields one-by-one using <=>, same as what we wrote above.

FOR Node

1
2
3
4
5
6
7
8
9
auto operator <=> (const Node &other)const{
	auto n = data <=> other.data;
	if (n != 0) return n;
	if (next == nullptr && other.next == nullptr) return n;
	if (next == nullptr) return std::strong::ordering less;
	if (other.next == nullptr) return std::strong::ordering greater;
	return *next <=> *other.next; //Recursively check next pair 
}

Invariants and Encapsulation

Consider:

1
2
3
4
5
6
7
8
9
10
struct Node{
	int data;
	Node *next;
	...
	~Node(){delete next;}
};

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

What happens when these variables go out of scope?
n2‘s dtor will try to delete n3 , which is an the stack undefined behaviour(UB)
e.g.: stack invariant:

  • last item pushed is the first item popped
  • but not if the client can rearrange the underlying data

Class Node relies on an assumption for its proper behaviour that next is either nullptr or points to a Node on the heap.

This assumption is an example of an invariant - a statement that must be true - upon which Noderelies.

But by expressing the next field, we allow clients to manipulate it directly, so we can’t guranteed the invariant.

It’s hard to reason about programs if you can’t rely on invariants.
To enforce invariants, we introduce encapsulation , so needed because we want clients to treat our objects as black boxes(or capsules).

That creates abstractions, in which implementation details are hidden. When we design our classes, we choose which details we want to expose to clients and hide the internal implementation details.

  • seal away implementations
  • only interact via provided methods
  • regains control over our objects

How do we hide implementation details? we made certain members(fields and methods) private?:

1
2
3
4
5
6
7
8
struct Vec{
	private:
		int x, y; //can't be accessed outside of struct Vec
	public:
		Vec(int x, int y); //default visibility is public
		Vec operator+(...)...
		...
};

C++ also lets us define a struct using the class keyword:

1
2
3
4
5
6
7
class Vec{
	int x,y;
	public:
		Vec (int x, int y);
		Vec operator+(const Vec&other);
		...
};

Both classes and structs can be used to define classes. The only difference:

  • in a struct, members are public by default
  • in a class, members are private by default

In general, we want our class members(in particular data members) to be private, we want default visibility to be private –> switch from struct to class

Let’s fix our linked list example by using encapsulation. The key is to create a wrapper class List that uses Node internally. The Node class won’t be exposed to users of our class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//list.cc(interface)
export class List{
	//only accessible within List
	struct Node; //Forward deel of Node struct. Node is a private nested class.
	Node *theList = nullptr; //head of list
	int list_size = 0; //size of list

public:
	void addToFront(int n); //"cons"
	int size()const;
	int &operator[](int i)const; //int &ith (int i)
	~List();
	...also need big 5...
};
  • private nested class, we can do class BinaryTree->class struct Node too
  • int &ith(int i):
    • returning an int refe, cuz you may want to mutate the element of the list
    • this is not a copy of the element, it is THE element
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//list-impl.cc
struct List::Node { //same node we used before.
	int data;
	Node *next;
	...big 5
	~Node{delete next;}
};

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

int List::size() const {return list_size;}
int &operator[](int i) const{
	Node *cur = theList;
	while(i > 0){cur = cur->next; i--;}
	return cur->data; //count i step of the list & return the data field
}
List::~List(){delete next;} //recursion, take stack space cuz recursion happens only if reach the last case(nullptr), iterative can do it by order

Client code:

1
2
3
4
List list;
int i;
while(cin >> i) list.addToFront(i); //we are the only one adding them
for (int i = 0; i < list.size(); i++) cout << list[i] << '-';
  • This node actually has a time complexity of O(n^2) where n is size of list.
  • only List can create/manipulate Node objects
  • can guarantee the invariant is always either nullptr or allocated by new

NOTES:

  • <=> comparing objects, if node nullptr, can’t work, but now that we have list as a class, and node nested class, node nullptr is now a object

  • we can place big 5(~List()) in list.cc instead of list-impl.cc(become iterative not recursive, saving stack space)

  • HOW CAN WE TRAVERSE THE LIST FROM NODE TO NODE AS WE WANT A LINKED LIST?

  • Repeatedly calling ith to access the whole list = O(n^2) time

  • BUT we can’t expose the node or we lose encapsulation

Introduction to Design Pattern

Certain programming challenges arise often. As developers, we should keep track of good solutions to these problems and reuse and adapt them.(《the book Deign Pattern》)

Essence of Design Pattern - if you have this situation, then this programming technique may solve it.

Iterator Pattern:

We don’t want to give client access to node, we don’t wanna give the client the pointer directly, but we can give them a class that contains the pointer.

  • create a class that manages access to nodes
  • abstraction of a ptr
  • walk the list without exposing the actual list

C++ has a standard of how iteration generally work. The basic idea behind the iterator pattern, is that we will create a new class called iterator that give us access to the nodes;

  • is an abstraction of a pointer
  • let us walk the list without expressing the actual pointers

RECALL CS136

1
2
for (int *p = arr; p != arrsize; ++p)
	printf("%d", *p);

Not use index to iterate, but pointer
iterator class we implement *, ++, !=

Using Iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(){
	List list;
	...populate the list...
	Node *theList
	//print the list
	List::iterator it = list.begin(); 
	//create an iterator object pass the frist item

	while(it != list.end()){
		cout << *it << `-`;
		++it;
	}
}

Implementing Iterator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class List {
	...
	public:
	...
	class iterator{ //nested class
		node *p; //fields to 'convert' node
		public:
			iterator(Node *p): p{p}{} //ctor
			int &operator*()const {
				return p->data;
			}
			iterator &operator++(){
				p = p->next;
				return *this;
			}
			bool operator != (const iterator &other)const{
				return p != other.p; 
				//not equal if the iterator points to different things
			}
	};
	//method of the list
	iterator begin()const{return iterator{theList};}
	iterator end()const{return iterator{nullptr};} 
	...
};
  • class iterator doesn’t have access to List theList
  • the only field class iterator has is a pointer, i want the iterator to point at theList
  • end() means one pass the end (arrsize that p compares with)
    • if it is a linked list, it is a nullptr
    • if it is an array, it is an address

Client

1
2
3
4
5
6
7
8
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:
range-based for loop:

1
2
3
for (auto n:l){
	cout << n << endl;
}

Available for any class with

  • methods begin and end that produce iterators
  • the iterators must support !=, prefix++, unary *
  • (postfix require a little more work)

If you want to mutate list items(or save copying)

1
2
3
for (auto &n : l){
	++n;
}

Will revisit iterators later

Encapsulation Continued

List clients can create iterators directly:
`auto it = List::iterator(){nullptr};’
this violates encapsulation, the client should be using begin() and end()
(cuz what if we don’t want the end to be nullptr anymore)

We could make the iterator ctor private

  • then the client can’t call List::iterator{--}
  • but then neither can List class

Sol:

  • give List privileged access to iterator
  • make it a friend
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class List{
    	...
    	public:
    		class iterator{
    			Node *p;
    			iterator(Node *p);
    			public:
    			...
    			//List has access to all members of iterator
    			friend class List;
    		};
    };

Class 11

Encapsulation continued

Recall:

1
2
3
4
5
6
7
8
9
10
11
class List{
	...
	public:
		class Iterator {
			Node *p;
			Iterator (Node *);
			public:
			...
			friend class List; // List has access to all members of Iterator
		}
};

Now list can still create Iterator, but client can only create Iterator by calling begin/end.
Give your classes as few friends as possible.

  • cuz this weakens encapsulation

Providing access to private fields:
accessor/mutator methods

  • invariants is protected
  • the methods are gatekeeper, make sure the client follow the rules
    1
    2
    3
    4
    5
    6
    7
    class Vec{
    	int x, y;
    	public:
    	...
    	int getX()const{return x;}
    	void setY(int z){ y = z;}
    };

What about operator <<, which need x and y but can’t be a member(you would have to put cout second to make it a member)?

  • If getX(), getY() defined, we are fine
  • If not, make operator << a friend function
1
2
3
4
5
6
7
8
class Vec{
	...
	friend ostream & operator<< (ostream &out, const Vec &v);
};

ostream& operator << (ostream &out, const Vec &v){
	return out << v.x << '' << v.y << endl;
} //can access vec field

Equality Revisited

Suppose we want to add a length() method to List , how should we implement it?
Options:

  1. loop through the nodes and count them (like strlen)—O(n)
  2. store the length as a field of List and keep it up to date—O(1) length with negligible additional cost. This is generally preferred.

Now consider again the spaceship operator <=> in the special case of equality checking:
l1 == l2translates to (l1 <=> l2) == 0
What is the cost of spaceship on 2 lists?

  • O(n), which n is the length of the shorter list.
  • BUT, in the special case of equality checking, we are missing out the shortcut: lists with different lengths can’t be equal. In that case, could answer “not equal” in O(1) time
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class List{
	...
	Node *theList();
	public:
	auto operator<=>(const List &other)const {
		if(!theList && !other.theList) return std::strong::ordering:: equal;
		if(!theList) return std::strong::ordering:: less;
		if (!other.theList) return std::strong::ordering:: greater;
		
		return theList <=> other.theList; //inappropriate, comparing ptrs
		return *theList <=> *other.theList;
	}
	//Different from previous implementation of `<=>`, 
	//cuz now we have empty list still an object.

	bool operator == (const List &other) const{
	if (length != other.length) return false;
	return (*this <=> other) == 0;
	}
};

Operator <=> automatically implements all 6 rational operators, but if you write operator == separately, the compiler will use that for == and != instead of <=>, which lets you optimize equality classes, if possible.

System Modelling

We’re gonna talk about how to describe the systems we are writing.
Visualize the structure of the system(abstractions + relationships among them) to aid design implementations.

Modelling classes:
Name: Vec
Fields(optional) :
x: integer
y: integer
Methods(optional):
+getX: integer
+getY: integer

(Visibility:
-private
+public)

Relationship: Composition of Classes
Recall 

1
2
3
class Basis{
	Vec v1, v2;
};
  • Embedding one class(Vec) inside another(Basis) is called composition.
  • A Basis is composed of 2 vecs. They are part of a basis and that is their only purpose.
  • Relationship: A Basis owns a Vec(in fact, it owns 2 of them). OWNERSHIP

If A owns a B, then typically,

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

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

  • destroy the car -> destroy the engine
  • copy the car -> copy the engine
    Implementation - usually as composition of classes: owns-a relationship

Modelling:
Aggregation: has-a relationship
similar to composition, except instead of one class being embedded in another, it’s rather linked to the other.
A has a B:

  • B exists apart from its association with A
  • If A is destroyed, B lives on
  • If A is copied, B is not (Shallow copy)
    • copies of A might share the same B

Typical implementation:
pointer fields.

1
2
3
4
5
class Ponds {
	Duck *ducks[MaxDucks];
	...
}