This work by Anthony Zhang is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright 2013-2017 Anthony Zhang.
Object-oriented development.
Instructor: Nomair Naeem
Office: DC 3548 (lab, by appointment), room B
Email: nanaeem@uwaterloo.ca
Website: https://www.student.cs.uwaterloo.ca/~cs246/
TA: Richard Wallace, cs246@student.cs.uwaterloo.caFive assignments, final assignment is worth more. Each assignment has two due dates - the first one we submit test cases, and the second is a week later and we submit code.
This course focuses on object oriented programming and the tools and techniques of software development, with a specific focus on C++.
The shell is an interface to the computer. The two main categories are graphical or command-line.
Graphical interfaces are easy to use, but makes it difficult to do complex tasks. They are available on almost every OS.
The command line accepts commands that are typed at the prompt. Windows has a DOS shell, while UNIX has a command line shell. It is possible to do more complex tasks with a command prompt, but it also has poor discoverability and a steep learning curve.
The first shell is Bourne shell, and then Cshell (and its descendent, Turbo shell) and Korn shell came along. Finally, there is Bourne Again Shell, or BASH. Bash is what we use in this course.
We can tell if a shell is Bash by the presence of the $ before the input prompt. echo $0 should print out the type of prompt, like "bash" or "sh".
The Linux filesystem consists of programs, code, and data.
There are files and directories. Directories can contain other directories and files. The filesystem is similar to a tree. However, directories are simply another type of file.
Within a directory, filenames must be unique. Filenames are case sensitive. For example, we can have /bin and /usr/bin.
The filesystem is often thought of as a tree, where nodes represent files. A standard Linux installation will usually have the following structure:
/
bin
bashls...etc
shells...home
ahzhang
USER_FILES_GO_HEREOTHER_USERS_GO_HEREusr
binincludeshare/ is always the root directory. All paths must be relative to some reference path.
When we have a path relative to a fixed directory such as / or /home, this is an absolute path. For example, /home/ahzhang/DropBox/School/Schedule.png, or ~/DropBox/School/Schedule.png.
Any other path is a relative path. What it actually is the path to depends on what it is relative to. For example, bin/bash could represent /bin or /usr/bin. How the path is resolved depends on the current/working directory.
The current/working directory is always available, and is the directory that all relative paths are relative to. For example, if the current working directory is /home/ahzhang/DropBox/School, then the relative path Schedule.png will resolve to /home/ahzhang/DropBox/School/Schedule.png.
The pwd (present working directory) command will display the current directory.
The cd DIRECTORY_GOES_HERE (change directory) command will change the current directory to DIRECTORY_GOES_HERE.
. is a special directory that always represents the current directory.
For example, cd . changes the current directory to the current directory, which does nothing.
.. is a special directory that always represents the parent of the current directory.
For example, to change the current directory to the grandparent of the current directoy, we can use cd ../...
~ is a special directory that always represents the current user's home directory, like /home/ahzhang. This is an absolute path because it does not depend on the current directory.
For example, cd ~ will change the current directory to the home directory. In fact, this is used so often that cd by itself will do the same as cd ~.
Also, cd - will change the current directory back to the last current directory - to the directory before we changed it with cd DIRECTORY_GOES_HERE.
~USER_ID_GOES_HERE is a special directory that always represents the home directory of the user USER_ID_GOES_HERE. This works as long as the referenced user has given permission to access it. This is an absolute path because it does not depend on the current directory.
Linux does not enforce the concept of file extensions. It is still followed by convention, however, since it is convenient.
The ls PATTERN_GOES_HERE command will list the contents of PATTERN_GOES_HERE, or if not specified, then it lists the contents of the current directory.
It simply shows a list of information about the files in the directory.
This command does not show certain files - dotfiles. These are simply files/directories that have names that begin with a .. This is a convention that allows for somewhat hidden files, which are useful for things like configuration.
To show these files anyways, we can use ls -a PATTERN_GOES_HERE, which works the same way but also shows dotfiles.
The parameter given to ls does not have to simply be a path. It also supports wildcards. Wildcard patterns are known as globbing patterns or globs. In globs, * means match any one file or directory name, and ? means match any one character of a file or directory name.
For example, ls *.txt lists all the text files in the current directory, and ls pictures-??-??-??-* matches all files of the form pictures-TWO_DIGIT_NUMBER-TWO_DIGIT_NUMBER-TWO_DIGIT_NUMBER-ANYTHING.
When we have a globbing pattern, the shell itself actually does the matching, not the command (like ls). The shell matches all the files, then passes all the matched files on the command line. The advantage of this approach is that each command does not have to implement globbing itself.
Globs are matched relative to the current directory.
Also, rm PATTERN_GOES_HERE removes all files matching PATTERN_GOES_HERE.
We can even do things like echo *.txt, which will print out all the text files in the current directory. Hwoever, to literally print *.txt, we simply use quotes, like echo '*.txt' or echo "*.txt".
Also, globbing patterns do not work inside quotes - they must appear directly.
Also, if a command is taking too long, then we can use Ctrl + C to kill it. This is often written as ^C. There is also Ctrl + D, which sends the end-of-file symbol to the program, which allows it to gracefully terminate.
The cat PATTERN_GOES_HERE (concatenate) command is an extremely commonly used command that simply prints out the contents of all given files.
If the pattern is not specified when we use cat, then the input is taken from the standard input. If we type some words, they will be printed out again at the standard output. This continues until we stop the command using ^D or similar. This mode is useful if we can capture the output somewhere.
All files given to cat are concatenated together. Running cat A.txt B.txt outputs the value of both files right after one another.
The COMMAND>FILE operator redirects the standard output of COMMAND into the file FILE, overwriting any existing contents of the file. For example, cat > entered_text.txt allows the user to type in some text and have it saved to entered_text.txt
The COMMAND<FILE operator redirects the standard input of COMMAND to the file FILE, so it is almost as if it was typed directly as input. For example, cat < input.txt will display the contents of input.txt on the screen.
cat FILE is exactly equivalent to cat < FILE.
The wc FILE command counts the number of lines, words, or characters in a given file, or in the standard output if not specified. For example, wc test.txt gives LINE_COUNT WORD_COUNT CHARACTER_COUNT FILE.
However, wc < FILE gives LINE_COUNT WORD_COUNT CHARACTER_COUNT - there is no FILE in the output since it is simply given from the standard input.
Every process has a standard input (stdin) and output (stdout) - the default place to get input and print output. The standard input is usually connected to the keyboard and the standard output is usually connected to the screen.
Input redirection changes stdin, and output redirection changed stdout.
Standard output is buffered - characters to be sent to the output are stored up until there is a large enough amount to send to the screen. This sending process is known as flushing the buffer.
Every process also has a standard error (stderr) - the default place to print out errors. This is intended to avoid cluttering the output. Also, stderr is not buffered - all errors will show up right away, not whenever the buffers are flushed.
We can redirect stderr using 2>, in a way similar to >.
We can also do all types of redirection at the same time: cat < input.txt > output.txt 2> error.txt reads the contents of input.txt and then writes it to output.txt, and any errors are written to error.txt.
There are also pipes, which allow the output of one program to become the input of another. COMMAND_A|COMMAND_B connects the stdout of COMMAND_A to the stdin of COMMAND_B.
The head -NUMBER_OF_LINES FILE command will read the first NUMBER_OF_LINES lines from FILE. If FILE is not specified, the lines are read from stdin.
So if we wanted to get the number of words in the first 20 lines of sample.txt, we might use cat sample.txt | head -20 | wc -w or simply head -20 sample.txt | wc -w.
The uniq command removes duplicate lines, but only if they occur next to each other - only adjacent duplicates are removed. It is therefore often used together with the sort command, which sorts its input by lines.
It is also possible to send the output of a program as a parameter to another program, using the backquotes/backticks notation. For example, echo "Today is ``date`` and I am ``whoami``" might display something like Today is Tue May 13 08:50:24 EDT 2014 and I am Anthony.
The shell will first evaluate the command in the backquotes, substitute its output for it, and then execute the original command. This works even if the parameter is inside quotes, as in the example above. An alternative syntax is $(COMMAND) instead of COMMAND, which is slightly easier to read. This is often used to format strings.
We now want to search inside text files. For this we can use grep PATTERN FILE or egrep PATTERN FILE (recommended, equivalent to grep -E). This prints out every line in FILE that contains PATTERN. Here, PATTERN is an extended regular expression. If FILE is not specified, input is taken from the standard input.
Also, alias something=something_else aliases something to something_else. So for the rest of the session, when we type something as a command, it runs something_else instead.
Regular expressions are concise ways to express a set of strings, which may possibly be arbitrarily large. For example, a?b?c? denotes the set containing the strings "", "c", "b", "bc", "a", "ac", "ab", and "abc".
Regular expressions consist of characters and operators. Characters like "e" and "5" simply denote themselves in the set. Operators like * modify strings with operations like "zero or more of the preceding".
For example, a* matches zero or more "a" instances, like "" and "aaaaaaaaaaaaaaaaaaaaaaaaa". It denotes the set of all strings consisting entirely of "a" and the empty string.
So to match either "CS246" or "cs246", we might use egrep "CS246|cs246" (the quotes are necessary because otherwise it is a pipe), or simply egrep "(CS|cs)246". Alternatively, to do it without case sensitivity we might use egrep [cC][sS]246. The [...] operation is called a character class, and matches one of the characters inside it. Also, the [^...] matches anything that is not one of the characters inside it.
? means "zero or one of the preceding". So egrep (abc)?d? matches "", "abc", "d", and "abcd". * means "zero or more of the preceding", while + means "one or more of the preceding".
{A, B} means "between A and B inclusive of the preceding". If B is blank, then it is assumed to be infinity. Clearly, ? is equivalent to {0, 1} and + is equivalent to {1,}.
. means "any character". For example, egrep ... will match any three characters. ^ matches the beginning of a line, and $ matches the end.
For example, to list all files in the current directory with exactly one "a", we might use ls | egrep "^[^a]*a[^a]*$".
ls -l displays more information about files, such as the owner and permissions.
For example, ls -l might give -rwxr--r-- 1 nanaeem staff 11K 2014-05-12 20:27 index.shtml.
2014-05-12 20:27 is the last date/time the file was modified. 11K is the file size, staff is the group, nanaeem is the owner, 1 (the first one) is the number of links, rwxr--r-- is the permissions, and - (the first one) is the file type (d for directory, - for file).
Groups facilitate sharing of files. Every file belongs to one group, and users can belong to multiple groups (this can be listed using the groups command). To share files, all involved users must be in the same group.
The permissions are simply 3 groups of 3 letters, with 9 letters in total. Each letter is either - or an alphabetical character, and represents a binary bit. The groups are:
The first letter (bit) of each group is the read bit, and is r if set, or - otherwise. If set, we would be able to read the file, or if it is a directory, we can list its contents.
The second letter (bit) of each group is the write bit, and is w if set, or - otherwise. If set, we would be able to modify the file contents, or if it is a directory, we can add or remove files.
The third letter (bit) of each group is the execute bit, and is x if set, or - otherwise. If set, we would be able to execute the file like a program, or if it is a directory, we can navigate into it, like with cd.
We can also specify permissions as a 3 digit octal number. Each digit represents a permission group, and we add up all the permissions that we want for that permission group, where r is 1, w is 2, and x is 4. So 700 represents all permissions for the owner, but none for anyone else.
So if a file has execute but not read permissions, then we could go into it but not list its contents. But if we happen to know one of the file paths, we can still access that file by path.
Only the owner of a file can change its permissions. It is not possible to give this ability to anyone else, and it is always possible for the owner to change permissions.
We do this using the chmod MODE FILE. MODE is a string of the form OWNERSHIP_CLASS OPERATOR PERMISSIONS, with no spaces.
OWNERSHIP_CLASS is the set of bits to apply the operations to. This value can be u for the user/owner bits, g for the group bits, o for the other bits, and a for all bits.
OPERATOR is an operation to perform with the permissions. This value can be + for adding a permission, - for removing a permission, or = to clear all the permissions and add the new one (set the permissions exactly).
PERMISSIONS is simply the permissions to be modified. This value is a string consisting of the characters r for read, w for write, and x for execute, or the octal equivalent.
FILE is the file that the permission changes should apply to.
For example chmod u+rw sample.txt gives the owner permission to read and write sample.txt.
In Bash, we can set variables using things like x=1 or x=" a b c ". It is important that there are no spaces around the equal sign. If there are, the shell would interpret the x as a command.
We can display the value of the variable using something like echo $x.
When we want to set a variable's value, we simply write the variable name.
When we want to get the value of the variable, we prefix it with a $, like $x. It is good practice to enclose the name with curly brackets: ${x}. This can be useful when inserting variable values into strings.
Variables are expanded by the shell before the current command is executed. Variables are expanded when they appear directly, or inside double quotes. Inside single quotes, variables are not expanded. For example, echo $VAR and echo "$VAR" print out the value of VAR, but echo '$VAR' will literally print out, "$VAR".
One of the most commonly used shell variables is PATH. This variable is a colon-separated list of paths that are searched in order when trying to execute a file. For example, if we execute ls, the shell will go through the paths specified in PATH one by one, looking for the ls program. If found, it stops searching, and otherwise an error is raised. This is essentially the list of places we should search for when we try to run a program specified by a relative path.
Bash scripts are files that contain a sequence of Bash commands that can be executed as a program.
For example, if we want to print out the date, current user, and current directory, we might write in the script file:
#!/bin/bash
date
whoami
pwdThe #!/bin/bash specifies that this file should be run with the /bin/bash program. # is often called "hash" and ! is often called "bang", so this type of line is often called the hashbang or shebang. This must be the first line and should not have any spaces before it.
Single-line comments are begun with #, which causes the rest of the line to be ignored. Therefore, the shebang line is actually just a comment to Bash.
Often the current directory is not in the PATH variable. That means that if we try to run script Bash will not find it in PATH and will not run the script. Instead, we often specify a full path using ./script, which is a fully given path - there is no need to search through PATH to resolve it because it is explicitly stated to be in the current directory. It is also possible to add . to the PATH variable to be able to directly run programs from the current directory.
A shell script must have execute permissions to be run. This can be done using something like chmod a+x script
Shell scripts can read command line arguments using the special shell variables $1, $2, and etc., where $0 contains the command line itself, "script".
For example, a shell script that checks if a word is in a dictionary can be written with a hashbang and egrep "^$1$" /usr/share/dict/words.
/dev/null is a file that can be written to, but simply discards whatever is written. Redirecting output to /dev/null means we are discarding the output.
If we want to check something like whether egrep matched something, we can use the exit code. The exit code is the value that we returned from the main function in C programs.
By convention, 0 indicates success, and a non-zero value indicates some sort of failure. In Bash, the last exit code given by a program is stored in the special shell variable $?.
In the above example, egrep gives exit code 1 if no matches were found and 0 otherwise:
egrep "^$1$" /usr/share/dict/words
if [ $? -eq 0 ]; then
echo Not a good password
else
echo Maybe a good password
fiThe spaces between [, $?, -eq, 0, and ] are all required. The body must be on its own line.
$# is another special shell variable, which always contains the number of command line arguments passed in. It is 0 if none were given - the $0 variable does not count.
if is a Bash construct that takes the form if PROGRAM; then BODY else BODY fi. The first body is executed if the status code is 0, and otherwise the second one is executed.
In our example, the status code is compared against 0, and a different message is displayed depending on whether the comparison succeeded. We could also use if egrep "^$1$" /usr/share/dict/words; then instead since the exit code follows the right pattern.
The general pattern is as follows, with zero or any number of elif statements:
if [ CONDITION ]; then
BODY
elif [ CONDITION ]; then
BODY
else
BODY
fiWhen we used it in the form above, we actually executed the [ program with the value of $?, -eq, and 0, which sets the exit code to 0 if the expression evaluates to true ($? is equal to 0), or 1 otherwise. This happens to work very well with the if construct.
[ supports various other options, like -w FILE for checking if a file is writeable, -x FILE to check if a file is executable, and -r FILE to check if a file is readable.
-eq is an operator for comparing integers. To compare strings, we can use == or =.
We can have as many elif statements as we need.
A while loop statement has a similar form to an if statement. The following prints out all the numbers from 1 to its first command line argument, inclusive:
x=1
while [ $x -le $1 ]; do
echo $x
x=$((x+1))
done$((...)) performs arithmetic by evaluating ... as an expression.
Functions in Bash have the following form:
usage() {
echo "Usage: $0 [[password]]"
}We often want to validate user input to ensure that we are working with valid data. We can do that by having something like the following near the beginning of the script:
if [ $# -ne 1 ]; then
usage
exit 1
fiA for loop statement iterates over a given series. It has the following form:
for name in *.cpp; do
mv $name ${name%cpp}cc
doneHere, name is the name of the variable to store the current item in the series. The *.cpp is a globbing pattern that gets expanded into a series. ${name%cpp} means the ending cpp should be removed.
The basic form is for x in a b c ...; do statements; done. This executes statements for each value of a b c ..., where x stores the current value.
To iterate over words in a file, we can use for word in $(cat $file).
When we have a variable with a space in it, like x="a b c", when we do something like cat $x we are actually passing in 3 arguments, a, b, and c. When we want to handle user input, it is usually a good idea to put the input variables in double quotes. In the above example, we change it to cat "$x" and it will attempt to read the file "a b c".
The goal of testing is to improve code quality. Testing is the process of trying various inputs on a program to catch errors in the output and verify seemingly correct programs are actually correct.
It is recommended that we write tests before beginning the coding process.
Guidelines for functional testing (testing the functionality of a program):
Regression testing is testing used to detect regressions - old bugs reintroduced into the code. We basically rerun all the old test cases again on the new code to ensure the new code does not break the old code.
Invented by Bjarne Stroustrup (Byarne Stroostrup) in the 1980s, intended to bring some object oriented features into C.
C++ is based in C first and foremost. Many valid C programs are also valid C++ programs. This course will assume a level of proficiency developed with C over the course of CS136.
The current standard is C++11, which was introduced in 2011 and added many sophisticated language constructs like anonymous functions. However, support is not perfect, and C++03 is still widely used.
C++ source files often have the *.cc or *.cpp extension.
A basic C++ program might look like the following:
#include <iostream> // we do not have to specify the .h extension for header files
using namespace std; // this puts the std namespace into the global namespace, so std::cout is the same as cout; without this line we have to use std::cout and std::endl
int main() { // the main function must be declared to return an integer, and for this function only it is not required to actually use a `return` statement (defaults to `return 0`)
cout << "Hello, world!" << endl;
}The syntax is similar to C. cout is the standard output stream, and endl is a constant representing the end of line (a newline on Linux, and a carriage return with a newline on Windows).
The iostream library has 3 main input/output (I/O) objects: cout representing standard output, cerr representing standard error, and cin representing standard input.
The << is an output operator - the "put to" operator. It sends the right operand to the stream specified by the left operand, producing the stream again. For example, cout << x puts x to stdout.
The >> is an input operator - the "get from" operator. It reads data from the stream specified by the left operand into the right operand, producing the stream again. For example, cin >> x gets x from stdin.
stdio.h and such are still available, but should not be used because C++ has its own equivalent functionality and libraries. Marmoset will be forbidding these libraries from being used.
We will be using g++, the equivalent of GCC for C++. A typical invocation might look like g++ myprogram.cpp -o output, where myprogram.cpp is the name of the source file and output is the executable (if not specified, defaults to a.out).
The following is a program that takes two numbers and adds them:
#include <iostream>
int main() {
int x, y;
cin >> x >> y;
cout << x + y << endl;
}Note that cin waits for an integer because the right side is an integer. This is an example of overloading. cin will always ignore whitespace and newlines when doing this.
The syntax is g++ OPTIONS FILE.
If we type in some invalid input like 4 potato to the above program or give an EOF, the variables are either uninitialized or set to 0 or other undefined behaviour.
How do we check if the input given was invalid - if the read was successful? cin.fail() is true if and only if the most recent read failed (invalid or EOF). Likewise, cin.eof() is true if and only if the most recent read got to the end of the input.
We must attempt to do the reading, and if it fails, then we handle the error condition. Also, if there is an error, the failure flag stays set until we acknowledge it, and until then all subsequent reads do nothing. Upon error, the stream is not advanced and a second read will try to read the same thing.
Program that reads integers and prints them until a non-integer or EOF is encountered:
#include <iostream>
using namespace std;
int main() {
int i;
while (true) {
cin >> i;
if (cin.fail()) break;
cout << i << endl;
}
}When we say if (!cin), cin is implicitly converted into a void*, and is truthy if the last read was successful and falsy otherwise. if (cin) is equivalent to if (!cin.fail()).
Also, std::cin >> i evaluates to std::cin, which allows us to do things like cin >> x >> y. This technique is known as cascading. The same thing works with the << operator as well, which we saw in the cout << i << endl line.
Note that a >> b is also the right bit-shift operator, equivalent to \floor{\frac a {2^b}}. This operator behaes differently depending on its operands. If the left side is an IStream such as std::cin, it acts as the input operator, and if the left side is an int, it acts as a right bit-shift.
With this in mind, we can have the following shorter version:
#include <iostream>
using namespace std;
int main() {
int i;
while (cin >> i) cout << i << endl;
}Another one that ignores non-integers and echos integers until encountering EOF:
// the `#include <iostream>` and `using namespace std;` are implicit for brevity
int main() {
int i;
while (true) {
if (cin >> i) cout << i << endl;
else {
if (cin.eof()) break;
cin.clear(); // acknowedge that the previous read failed and reset cin so we can read again
cin.ignore(); // ignore the next input (character) so we don't read the same invalid value over and over again
}
}
}In C++, strings are significantly easier to use than in C. We use the type std::string, and literals are denoted with double quotes ("string"):
int main() {
std::string s;
std::cin >> s;
std::cout << s << endl;
}When we try to read a string from stdin, it first ignores all leading whitespace, stores non-whitespace characters in the variable, and stops at the first whitespace character encountered. As a result, it will only read one word at a time.
To actually get the entire line, we can use getline(cin, s). The type of data and the exact reading/writing behavior of cin or cout depends on the type of the right operand of >>.
However, if we wanted to use format specifiers (like those accepted by printf in C), like printing out integers in hexadecimal or octal, we can I/O Manipulators.
I/O Manipulators look like std::cout << std::hex. This does not print anything, but it changes the behaviour of cout so that it prints integers out in hexadecimal. Likewise, std::cout << std::dec changes cout to print integers out in decimal again. There are many other manipulators but these are one of the most common ones.
The advantage of using streams for things like cin and cout is that it abstracts more than just stdin and stdout. All the behaviour associated with stdin and stdout can also be used to other stream-like data such as a file or even on a network connection.
To use file streams, we must have #include <fstream> to have the file stream functionality. It provides ifstream for input file streams and ofstream for output file streams. The following prompts the user for a word and writes it to a file:
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream f("test.txt"); // declare an `ifstream` initialized with "test.txt"
string s;
f << "Word: " << endl;
cin >> s;
f << s << endl;
}Note that we didn't have to close the file - C++ automatically closes it after we are done using it.
Also, str.length() gets the length of the string str.
In C++, when we have a function that accepts arguments, we can also make an argument optional, and give it a default value when none is specified:
// default values can be given in the declaration or definition
void printSuiteFile(int max, string filename = "suite.txt") { // arbitrary numbers of optional parameters can appear after the required parameters
ifstream suite(filename.c_str()); // we have to convert it to a C style string because that's the only thing `ifstream` accepts
}
int main() {
printSuiteFile(5); // no argument specified, default value used
printSuiteFile(3, "something.txt"); // "something.txt" specified, default value ignored
}Function overloading allows us to have functions with multiple definitions, each with unique signatures. C++ will look at the different signatures, and match each function call with the right definition:
int negate(int a) { return -a; }
bool negate(bool a) { return !a; }
negate(5); // calls the first one
negate(true); // calls the second oneThe signatures are matched based on the function name, the number of arguments, and the type of the arguments. There can only be one definition for a given combination of function name and argument types. Notice that the signature does not include the return type - a signature is something like f(int x), not int f(int x).
It is also possible to do operator overloading. For example, cin >> INTEGER_VAR reads an integer while cin >> STRING_VAR reads a string - the >> operator is overloaded to read input from streams, as well as the right bit shift operator on integers.
A declaration asserts the existance of an entity. A definition is the actual implementation of an entity. A definition must necessarily require a declaration. Declarations can be repeated as many times as we want, but there can only be one definition per entity.
We can also do I/O on strings using streams, using the sstream library:
#include <sstream>
int main() {
std::string value = "2 5";
stringstream input(value); // string reader
stringstream output; // string writer
output << "Enter a number between " << low << " and " << high;
int low, high; input >> low, input >> high;
std::string result = output.str();
}Note that we didn't have to use clear on the output stream, because although the failure flag was raised, we are simply making new streams every iteration of the loop.
The string writer is useful for formatting text and converting numbers to strings. The string reader is useful for converting strings to numbers. When using string readers, it is important that we handle EOF.
In C, strings were 0-terminated char arrays that we had to do memory management on manually and were prone to buffer overruns. In C++, strings are part of the standard library, manage their own memory, and are much less prone to buffer overruns.
Consider string s = "hello";. "hello" is simply a char array with a 0 terminator, while string is a C++ string. C++ implicitly converts C-style strings into C++ strings (instances of std::string).
However, C++ strings are not implicitly converted into C style strings. This becomes necessary for things like ifstream, which only accepts a C string for the file name. We can explicitly convert the C++ string into C style using s.c_str().
In C, we used strcmp(a, b) to compare strings, while a == b only compared pointers. In C++, we can simply use a == b or a != b to compare strings.
We can also still use the s[i] notation that we can use in C. To concatenate two strings, we can use a + b instead of strcat(a, b).
The reason structure declarations need a semicolon at the end is because we can actually declare variables right after:
struct Node {
int data;
Node *next; // the `struct` is not necessary
// ...
} node_var1, node_var2, *pointer_to_node;
// now `node_var1`, `node_var2`, and `pointer_to_node` are defined
Node node_var3;In C++, we can also simply write Node instead of struct Node in all contexts, except the declaration itself.
When we read type declarations, we start from the identifier and work outwards. For example, int * const p is a constant pointer to an integer, and const int *p is a pointer to a constant integer.
When we use an operator like A << B, this is calling a function called operator<< with two arguments A and B.
void inc1(int n) { n ++; }
void inc2(int *n) { (*n) ++; }
void inc3(int &n) { n ++; } // here, `n` is a reference to `x`, because `x` is now being passed by reference
int main() {
int x = 5;
inc1(x); // this does nothing because the argument is passed by value
inc2(&x); // this works because we are passing an address by value, but requires special syntax
inc3(x); // now we are passing a reference to `x` rather than the value
cout << x << endl;
}C++ also has another pointer-like type, the reference:
int y = 10;
int &z = y;This means that "z is a reference to y". This means that z is a constant pointer to y, but with automatic dereferencing. So whenever we write z, it actually means "the value pointed to by z", so y in this case. Therefore, writing z is equivalent to writing y - it has no identity of its own.
So int *p = &z makes p point to y and z = 5 sets y to 5. Also, sizeof(z) is simply the size of y. References are more or less exactly the same as writing the variable itself - they are aliases.
References cannot be left uninitialized because they are actually constant pointers. Also, they must be initialized to something that has an address (an lvalue), so we can't do int &z = 5.
We cannot create a pointer to a reference itself (int &*p = ...;), only the lvalue it refers to (int *p = &z), but we can create a reference to a pointer (int *&p = q; after int *q;). However, we cannot create a reference to an array (int &x[] = {1, 2, 3}).
cin actually uses references to support things like cin >> x: istream &operator>>(istream &in, int &data). Here, istream in is cin and data is a reference to x. Both are being taken by reference because both are modified by reading. We return a reference because we don't want to copy the istream instances we returned.
References are often used for arguments and return values in order to avoid copies (when copying is an expensive operation, like copying a big struct, or simply not possible, like an istream) and allow modification of the lvalue they refer to.
When we have int f(int x) { ... } and we run f(n), a copy of n is created and in f, x refers to that copy (this is why n is not modified).
An array is a set of homogenous values.
Arguments in C++ are passed by value, but we can fake passing by reference by using reference types.
Functions in C++ accept arrays in much the same way as in C: int f(int a[]).
The main function has two possible prototypes:
int main(); // note that we didn't need to use void
int main(int argc, char *argv[] );If we use the second form, argc is the length of argv, and argv is an array of strings representing each command line argument. argc is always non-zero, since there is always at least one argument.
The first element of argv is the name of the current program that is running. For example, ./a.out.
;wip: heap stuff, maybe check the course outline
Stack memory is automatically freed when the variables using the stack memory go out of scope. Heap memory keeps being used until we explicitly use delete on it.
The preprocessor changes the code before it actually gets to the compiler. It can do several types of manipulations to source code files.
The preprocessor can be used for many possible things, but is mainly used for substitution, file inclusion, and conditional inclusion.
The preprocessor is controlled via preprocessor directives. These are just lines that start with #NAME_OF_DIRECTIVE with no preceding whitespace, and are followed by the arguments to the directive.
The #define VARIABLE ... directive replaces all instances of VARIABLE with ..., where ... can be anything. To represent multiple lines, use a backslash at the end of the line.
The -DVARIABLE="..." command line flag to g++ accomplishes the same purpose without having to modify the source - these are defines that are processed before the preprocessor looks at the file. We use it as g++ -DA=1 -DB=2 -DC=3 file.cc.
That said, don't use #define whenever possible. For enumerations, use enum, and for functions that need to be fast, use the inline keyword to automatically inline the function: RETURN_TYPE inline NAME(...). This directive is useful for debugging flags to turn on debugging features in the program.
#define VARIABLE defines VARIABLE to be the empty string. This simply defines the variable but gives it a blank value.
This is often used with the #ifdef VARIABLE and #ifndef VARIABLE directives, which check if VARIABLE is defined and include code accordingly.
The #include directive works much line in C, but for standard library paths we can drop the .h suffix - it is #include <iostream> rather than #include <iostream.h>. As usual, we include relative to the current directory with #include "some_file.h".
If we use #include on the same file twice, it will include that file twice. So if we have a file with some definitions, including it twice will result in a double definition and an error. We can avoid this by using the following pattern wherever we have a file that needs a library:
#ifndef __LIBX__ // double underscores is standard naming convention
#include <libx>
#define __LIBX__
#endifNow whenever we include a file, it will set a preprocessor variable, so when we encounter another inclusion of the same file that uses this pattern, it is not incuded again. This is a part of good coding style and is required for all inclusions from now on.
The #if EXPRESSION directive and its corresponding #else and #elseif EXPRESSION and #endif operator allow us to include code depending on the value of EXPRESSION. EXPRESSION supports all of the operators as C++ source code, but the operands must be integers or characters.
This is often used to make code cross platform:
#define UNIX 0
#define WINDOWS 1
#define OS UNIX
int main() {
#if OS == UNIX
// compatibility stuff here
#elseif OS == WINDOWS
//compatiility stuff here
#else
// default case
#endif
}Also, we can use #if 0 to make a block that will never be included. This is useful for commenting out the body of the directive, especially where block comments don't work when there are nested block comments.
The cassert library adds assertions, much like those in C. After using #include <cassert>, the assert(EXPRESSION) or assert(DESCRIPTION_STRING, EXPRESSION) function can be used.
A program split over multiple files can be written in such a way that each file can be compiled separately. Each module should have an interface (header file) and implementation (source file).
A function prototype is a signature associated with a return type. For example, int v(int x, string y). A signature is the types of the arguments of a function, such as v(int, string) (the parameter names are optional).
We can overload operator+ and other functions to implement functionality:
struct Vector {
int x;
int y;
}
Vector operator+(const Vector &a, const Vector &b) {
Vector v;
v.x = a.x + b.x;
v.y = a.y + b.y;
return v;
}For many projects, we can just compile them with g++ *.cc. However, this only works well if all the source files are part of the project. We can also simply specify every file to compile: g++ main.cc vector.cc.
For large projects, it can take hours just to compile all the files. Separate compilation means that we can recompile only the parts that we changed, and in this way save a lot of time.
The linker is the program that runs after the compiler in the compilation chain. It combines all the compiled files together into a single executable. The linker in Linux is called ld.
Compilation results in an object file, which has the code, a list of what symbols it expects, and which it provides. They are conventionally stored in "*.o" files. The linker resolves these names together in a way that allows all the requirements to be satisfied.
The -c command line option (used like g++ -c FILE) allows us to compile without linking. This results in the object file, and the linker is not invoked at all.
An object file can be directly linked, so we don't need to compile the source again for that file. For examplle, if we compiled "vector.cc" into vector.o, then our compilation command would change from g++ main.cc vector.cc to g++ main.cc vector.o, and G++ would use the object file instead of compiling vector.cc again.
We should never have global variables in headers (global int n). This is because global variables are declarations and definitions (since they reserve space for the variable), so there would be multiple definitions if we included the header more than once. Instead, we use extern int n to only declare and not define the variable. ;wip: C++ globals
Another advantage of separable compilation is the ability to compile the source file and leave the header file uncompiled
We should never put using namespace std; in a header file. This is because it brings in a lot of names into the current namespace, like cin and endl, which the client that is including the file may not want. As a result, we should only use this in programs that will not be included by clients, and use std::string and similar in header files.
Using classes, we can put functions directly inside a struct.
A class is basically just a struct that can contain functions. Every struct is therefore a class.
The class keyword is also available, and it behaves a lot like struct, but has some slightly different behaviour that will be discussed in detail later.
An object is an instance of a class. A member function or method is a function inside a class. grade is therefore a method of Student.
struct Student { // class declaration
int assignment_grade;
int midterm_grade;
int final_grade;
float grade() { // grade is a function that is associated with Student, so we want to put it inside the struct
return assignment_grade * 0.4 + midterm_grade * 0.2 + final_grade * 0.4; // we can use the fields of the class instance just like normal variables
// when we call this below, `assignment_grade` refers to `s.assignment_grade`, and so on
// the fields are taken from the instance the method was called on, so if we called `some_other_student.grade()`, `assignment_grade` would refer to `some_other_student.assignment_grade` instead, and so on
}
}
int main() {
Student s = {80, 50, 70}; // `s` is now an instance of `Student`
std::cout << s.grade() << std::endl; // call the `grade` method
}We saw the same dot syntax before when we used some_string.length() or cin.ignore().
The difference between functions and methods is that methods have a hidden parameter called this. this is implicitly inserted before the first actual parameter, and contains a pointer to the object on which the method was called. Functions do not have this hidden parameter.
So in grade, the value of this is the same as &s in main. As a result, we can also write the grade method as follows:
struct Student {
int assignment_grade;
int midterm_grade;
int final_grade;
float grade() {
return this->assignment_grade * 0.4 + this->midterm_grade * 0.2 + this->final_grade * 0.4;
// when we write `assignment_grade` directly, it is exactly the same as `this->assignment_grade`
// we might use `this->` when we have a local variable or parameter with the same name as a class variable, because the local variable or parameter would shadow the class variable and there would be no other way to refer to it
// it is good coding style to always use `this->` to make it explicit that it is a class variable
}
}In C-style initialization, we initialize objects in a certain way: Student someone = {A, B, C};. The disadvantage is that this is very inflexible, and we can't really add any custom behaviour associated with object initialization. For example, if we created a database object, we probably also want it to open a database connection.
In C++, we have a constructor ("ctor" for short) method that is used to initialize an object. For example:
struct Student { // class declaration
int assignment_grade;
int midterm_grade;
int final_grade;
Student(int a_g = 0, int m_g = 0, int f_g = 0) { // the constructor is the function that has the same name as the class
// the constructor has no return type because it should always return a new instance of `Student`
this->assignment_grade = a_g;
this->midterm_grade = m_g;
// we can now do anything here to initialize things
}
float grade() {
return assignment_grade * 0.4 + midterm_grade * 0.2 + final_grade * 0.4;
}
}
int main() {
Student s(90, 80, 70); // this calls the constructor instead of initializing the struct directly
Student other = Student(90, 80, 70); // this is exactly equivalent to the definition above
Student *heapy = new Student(90, 80, 70); // this allocates the `Student` object on the heap and gives a pointer to it, so we can do `heapy->grade()` and such
// this is the same syntax we saw before with `ifstream` objects.
// we also cannot call the constructor of an object that is already created, so `other.Student(1, 2, 3)` is invalid
Student someone(); // THIS IS A FUNCTION DEFINITION, NOT A STRUCTURE DEFINITION - WE CANNOT USE PARENTHESES WHEN THERE ARE NO ARGUMENTS TO THE CONSTRUCTOR
Student someone; // this is how we use default values for all the arguments instead
}The advantage of contructors is that we can associate arbitrary behaviour with the creation of an object. Also, we can use default values for parameters of constructors, or even function overloading on constructors, to allow different ways to initialize the object.
If no constructor is specified in a class, then there is a default constructor that calls the default constructor for each of the fields, if they exist. Most of the time, this doesn't do anything. This is just a constructor that accepts no arguments.
So if we define any of our own constructors, the default constructor will no longer exist. To get the same behaviour, we can define a zero-argument constructor.
If we specify our own constructor for a class, we can no longer use C-style initialization on it - Vec v = {1, 2} will give an error.
Initializers are not allowed for structure fields - we can't initialize a field directly inside a struct.
Objects are created on the stack if they are defined with Vector v(5, 6); or Vector v = Vector(5, 6), and on the heap if we use Vector v = new v(5, 6).
Whenever we create an object, first the memory is allocated for it in the heap or stack depending on how it is created. Then, the fields are initialized using the default constructors for the fields (for things like int, often by setting them to 0), and finally the constructor body runs.
We can initialize constant and reference values using a member initialization list. This is a list that comes after a constructor declaration and a colon that allows us to bypass initializing the specified fields using the default constructors, and call the default constructors with the arguments we want:
struct Something {
int normal; // this is just a normal struct field
const int some_constant; // this must be initialized, because we can't change it later
int &some_reference; // this also must be initialized, because it must always refer to something
Something(int c, int &r): normal(5), some_constant(c), some_reference(r) { // member initialization list calls the default constructors, but with values that we specify
// it is too late to initialize them in the constructor body, because they should be initialized (and for constants, made fixed) as soon as they are defined
}
};This is also useful for shortening constructors, because we can just initialize the fields of a structure using a member initialization list and leave the body blank.
In a member initialization list, the name outside the parentheses must be a field, and the value inside the parentheses can be any valid expression, like globals and scope variables, or fields that have already been initialized.
struct S {
int n;
Something(int n): n(n) {} // in the member initialization list, it is valid to use the same name because the name outside the parentheses is searched for in the fields, not as an expression
}; // it is also more efficient to use these member initialization lists than to assign them values inside the constructor body, because we don't need to call the default constructors any moreWe use member initialization lists because they are the only way to initialize constants/references, because they are shorter and cleaner than assigning in the constructor body, and because it can be more efficient.
Fields are initialized in the order that they are declared in the struct, regardless of their order in the member initialization list. However, we should generally keep them in the same order to avoid a compiler warning.
There is also a copy constructor that is called when we make a copy of a struct:
Student a(60, 70, 80);
Student b = a; // this calls the default copy constructorThere is a default copy constructor, which just makes a shallow copy of a (a field-for-field copy).
We can define a custom copy constructor as follows:
struct Student {
int assignment_grade;
int midterm_grade;
int final_grade;
float grade() {
return this->assignment_grade * 0.4 + this->midterm_grade * 0.2 + this->final_grade * 0.4;
}
Student(const Student &other): assignment_grade(other.assignment_grade), midterm_grade(other.midterm_grade), final_grade(other.final_grade) {} // the reference should be constant since it usually doesn't need to be modified
};The custom copy constructor is often useful when we have dynamic memory or want a deep copy. For example, we want a deep copy for a linked list to avoid sharing the same linked list nodes for multiple starting lists, which would make freeing the memory very difficult:
struct Node {
int data;
Node *next;
Node(const Node &other): data(other.data), next(other.next ? new Node(other.next) : 0) {};
};So every class has a default constructor, a default copy constructor, a copy assignment operator, and a destructor.
The delete keyword can be used to destroy an object on the heap given its pointer. If we defined something like int *x = new int(5) (a pointer to an integer on the heap), then afterwards we can destroy it using delete x;.
If we have an array on the heap like int *a = new int[20], then we must use delete [] a to properly destroy the array. Using delete without the [] might result in the wrong thing being destroyed.
delete cannot be used with stack memory. It works in a way conceptually similar to the free function in C.
An object on the stack is destroyed when it goes out of scope (for example, an object created inside a function would be destroyed when the function returns, unless it is returned).
An object on the heap is destroyed when we explicitly destroy it using delete. Otherwise the object remains in memory.
Objects have methods called destructors that get called when an instance of the object gets destroyed. We can specify a custom destructor as follows:
struct Node {
int data;
Node *next;
Node(const Node &other): data(other.data), next(other.next ? new Node(other.next) : 0) {};
~Node() {
delete next; // since `next` is on the heap, the default destructor wouldn't destroy it and there would have been a memory leak
// a destructor should never throw any exceptions
// we can do other cleanup stuff here, like closing database connections, destroying heap objects, or other things
}
};There is also a default destructor, which just calls the destructors on the individual fields of the object.
Header files should contain function declarations, structure declarations, and things like constants. Source files should actually implement the functions.
Up to this point we have been defining the whole class in one big struct declaration and putting implementation together with declarations. This is not the ideal way to go about it - it is possible to separate the two. The following would go into the header file:
#ifndef __NODE_H__
#define __NODE_H__
struct Node {
int data;
Node *next;
Node(int data, Node *next); // constructor
Node(const Node &other); // copy constructor
};
#endifAnd the following would go in the source file:
#include "Node.h"
Node::Node (int data, Node *next) : data(data), next(next) {}
Node::Node (const &other) : data(other.data), next(other.next ? new Node(*other.next) : 0);The a::b is the scope resolution operator. It resolves the identifier b in the context of a. For example, if a is a struct, then b would be resolved as a field of a. So Node::Node would let us define functions inside the Node struct, even though we are lexically outside of the struct declaration.
When we do an assignment a = b, we are actually using the = operator on a and b. This works a lot like the copy constructor, but the operator= is now a method of a rather than an overloaded function. We can use this to provide custom behaviour when someone assigns to an instance of a particular class:
struct Node {
int data;
Node *next;
Node(int data, Node *next); // constructor
Node(const Node &other); // copy constructor
};
Node &Node::operator=(const Node &other) {
if (this == other) return *this; // assigning an object to itself could be problematic if we aren't careful
delete this->next; // delete the rest of the list to prevent memory leaks
this->data = other.data; // set this node to be the new node
this->next = other.next ? new Node(*other.next) : 0;
return *this; // the return value is a pointer to what the new value of the variable is
// we might also assign `this.next` to a pointer variable and delete it last in case the copying of `other.next` failed for whatever reason
}The copy and swap technique is a way of implementing assignment that uses the copy constructor to simplify assignment and freeing the memory of the old object in a simple way:
struct Node {
void swap(Node &other) { // this swaps the values of this instance and a specified other instance
int *data = this->data;
this->data = other.data;
other.data = data;
Node *next = this->next;
this->next = other.next;
other.next = next;
}
Node &operator=(Node &other) {
Node t = other; // using the default copy constructor to make a copy of `other`
this->swap(t); // set the fields to the temporary value
return *this;
// this does not leak memory because `t` is on the stack and the destructor is called when it goes out of scope
}
}The rule of 3 states that if we need any one of the copy constructor, destructor, or operator=, we probably need to write all three.
Whenever we declare one of the operator+ or similar member functions, we get the this parameter inserted implicitly and this acts as the left hand side of the operation. This allows us to implement a lot of different functionality:
struct Vec {
int x, y;
Vec operator+(const Vec &o) { return Vec(this->x + o.x, this->y + o.y); }
Vec operator*(const int k) { return Vec(this->x * k, this->y * k); } // this works for expressions of the form `SOME_VEC * SOME_INT`
}
Vec operator*(const int k, const Vec &v) { // to allow things like `SOME_INT * SOME_VEC`, we must use another function
return v * k; // this calls the member function
}Most operators can be implemented as either standalone functions (like the second operator* in the above example), or as member functions (like operator+ in the above example).
Some operators can only be implemented as methods: operator= (assignment), operator[] (subscripting), operator-> (dereferencing field reference), operator() (function call), operator T() (T is a type, and defines implicit conversion, like operator void* allows us to implicitly convert the object to a void pointer). operator= must be a member function because there is already a default operator= member function, so we must override the member function itself.
A single argument constructor can be used to do implicit conversions. For example, a Node(int data): data(data), next(0) {} constructor method would allow us to do something like Node n = 4. To avoid implicit conversion, we can use the explicit keyword, which goes right before the Node in the declaration. This makes the compiler give an error if we attempt to perform implicit conversion.
The following code results in a compilation error:
struct Vec {
int x, y;
Vec(const int x, const int y): x(x), y(y) {}
}
int main() {
Vec v[3]; // this is an error because we didn't initialize the vectors in `v`
Vec v[3] = {Vec(0, 1), Vec(1, 2), Vec(2, 3)}; // this is correct
Vec *w = new Vec[5]; // we cannot use the above technique because it is on the stack
// we could implement a default constructor in `Vec`, or we could just deal with pointers to objects instead
Vec **w = new Vec *[10];
}Suppose we have a constant argument: void f(const Student &s) { BODY }. Inside of BODY, we cannot modify the fields of s or assign a new value to it. Additionally, we cannot call any methods on s unless those methods specify that they do not modify fields too.
We can specify that a method will not change its instance by using const: float Student::grade const () { BODY }. If specified, the compiler checks that the method does not modify fields, and if it doesn't, we can call the methods when their instances are constant, in addition to when their instances are not.
We can also define that a field is exempt from the compiler checking for fields being modified in a const object. If we define a field like mutable int x;, then we can actually change it even when its instance is constant.
A static field is a field of a class rather than a method of an instance of a class. So all instances of the class would share the same static field, so modifying it would change its value for all instances. For example:
struct Vec {
static std::string __doc__; // static field
int assignment_grade, midterm_grade, final_grade;
static something() { // static method
// we can access static fields or call other static methods here, but not instance fields or methods
}
}
std::string Vec::__doc__ = "Information about this class"; // we still cannot define values in the declaration of a structureA static method does not depend on instances, so it has no this parameter. The difference between a function and a method is that a method has a this parameter. Since a static method is not, it is technically a static member function rather than a method.
We call member functions using CLASS_NAME::MEMBER() and methods using INSTANCE.METHOD().
Inside a function, static in a variable declaration means that the variable keeps its value in between function calls, like a global variable that can only be accessed within the function.
Design patterns are commonly occurring patterns of problems and good solutions to these problems in object oriented programming.
Problem: we have a class c, and we want only one instance of c to ever be created no matter how many times we attempt to create an instance.
We can do this by declaring a static field of c as a flag, and in the constructor, setting the flag to prevent future instances from being created:
struct Student {
static Student *instance;
static Student *getInstance();
int grade;
Student();
}
Student Student::instance = 0;
Student *Student::getInstance() {
if (!instance)
instance = new Student;
return instance;
}
Student::Student(): grade(0) {}Every new should be matched with a delete. In the above example, the this->instance is a memory leak - it leaks the single instance of the wallet.
We want the data to be deleted at the end of the program. This is not always the end of the main function, because when we have global objects, their constructors run before main, and their destructors run after main.
The cstdlib library contains a function called atexit(void (*function)()), which accepts a function pointer to run when the program terminates. The function specified should have a void return type and no arguments. If called multiple times, these functions queue up.
We can use this to implement cleaning up the instances on termination:
#include <cstdlib>
struct Student {
static Student *instance;
static Student getInstance();
int grade;
Student();
static void cleanup()
}
Student Student::instance = 0;
Student Student::getInstance() {
if (!instance) {
instance = new Student;
atexit(cleanup);
}
return *instance;
}
Student::Student(): grade(0) {}
Student::cleanup() { delete Student::instance; }There is a tool known as Valgrind that can perform various correctness checks on programs. By running a program in a certain way using Valgrind, it is possible to detect memory leaks for that particular execution path. A typical usage might look like valgrind a.out. It simply slows down the program slightly while it is running.
Note that the constructor is still accessible to all users. This means that it is still possible to create a new wallet directly from the client code, which we want to avoid.
We can use encapsulation to hide the implementation details to make the program more robust. This forces clients to treat the object as a black blox, and only use the provided interface:
struct Student {
static Student getInstance(); // fields in a struct default to public
private: // this label makes fields after it private
static Student *instance;
int grade;
Student();
static void cleanup()
public: // this label makes fields after it public again - there can be multiple public and private labels in a class
int getGrade();
Student operator+(const Student &other);
}Private fields are hidden to outsiders - code that is not inside the methods or member functions. In general, it is good practice to make as many fields private as possible. This is because if we make fields public, we can't guarantee class invariance - statements about the program/class that are always true. For example, a 2D coordinate class might have the invariant "both components are always positive", which might be broken if we allow the user to modify the components using a public field. We should instead use methods that get ("getters"/"accessors") or set ("setters"/"mutators") the private field, because these methods can enforce the invariants.
It is also important to use private fields because if we have public fields, it is no longer possible to change the implementation later without breaking client code. For example, if we changed a 2D coordinate class from Cartesian to polar coordinates, field names would be changed, which would break client code if they were public.
Getters should be const, like int getX() const { return this->x }. This allows us to use them when the this instance is constant.
The class keyword works the same way as struct, except all fields we define in a class block defaults to private rather than public. We will now transition to using class over struct in order to make encapsulation easier.
We want to implement operator<< without using getters, because we don't want the client to have access to them. We want to give access to the stream class only, but nothing else. We can do this using friend declarations. In a class, this allows us to specify that some function should have full access to all the fields of this class:
class Vec {
int x, y;
friend ostream &operator<<(const ostream &out, const Vec &v);
}Class destructors should be public in order for them to be usable. We define destructors with ClassName::~ClassName() { ... }.
;wip: relations between classes. Composition, friends, aggregation, and he started inheritance near the end
The unified modelling languagge (UML) is a graphical notation focused on object oriented design for software systems.
UML diagrams can represent either structure or behaviour of a program. There are different conventions for both types.
UML diagrams look a lot like flowcharts, but have some different conventions. Comments are placed in a square box with a folded top right corner.
Class diagrams allow us to denote class models by showing information about classes in boxes and using various types of lines to show relationships between them.
Class boxes are rectangular and have the class name at the top. Optionally, they also contain a list of fields (attributes), or optionally also a list of methods (routines).
Each attribute list entry is of the form VISIBILITY NAME [":" [TYPE] ["[" MULTIPLICITY "]"] ["=" DEFAULT]], where VISIBILITY is "+" for public, "-" for private, "#" for protected, and "~" for package; NAME is the field identifier, TYPE is the field type ("Boolean", "Integer", "Float", "String", or a class name), MULTIPLICITY is the cardinality (array size) of the field of the form "LOW..HIGH" or "n" (specific amount) or "*" (any amount), defaulting to 1; and DEFAULT is the default value of the property.
Each routine list entry is of the form [VISIBILITY] NAME ["(" ([DIRECTION PARAMETER_NAME ":" TYPE ["[" MULTIPLICITY "]"] ["=" DEFAULT]])* ")"] [":" RETURN_TYPE] where DIRECTION is the direction of data flow ("in", "out", or "inout"), PARAMETER_NAME is the name of a parameter, and RETURN_TYPE is the return type of the method.
A class with a field that contains a class instance (rather than a basic type like a string or bool) has an owns-a relationship with that class.
A class with a field that contains a pointer to a class instance has a has-a relationship with that class.
;wip: relationships is-a
In UML, has-a is represented by an open diamond, and owns-a is represented by a filled diamond.
Private fields are inherited by subclasses, but they can't access them. In addition to private and public, we also have access level called protected that acts like private, but all subclasses can access it as well.
When an object is created, space is allocated for it, the superclass is constructed, the fields are initialized, and then the constructor body runs. However, if the superclass doesn't have a default constructor, superclass construction cannot occur:
class Book {
protected:
string title, author;
private:
int ISBN;
public:
Book(string title, string author, int ISBN): title(title), author(author) {}
}
class CSBook: public Book { // `CSBook` inherits from `Book`
// here, we can set/get `title` and `author`, but not `ISBN`
public:
CSBook(string title, string author, int ISBN): Book(title, author, ISBN) {} // we override calling the default superclass constructor with our custom call to the constructor in the initialization list
}Protected fields are a bad idea because they break encapsulation. We use encapsulation because then we can enforce class invariants, like the components of a vector being positive.
If we have protected fields, the client could potentially write their own subclass that gives them access to the protected fields of a class. Instead, we should use protected accessors/mutators, while the fields stay private. This allows us to enforce invariants inside the protected methods, while the private fields remain inaccessible outside the class, even to subclasses.
The relationship between Book and CSBook is an "is-a" relationship. We say that CSBook "is-a" Book, and draw a line with a filled arrow pointing from CSBook to Book:
a=>operation: Book
b=>operation: CSBook
b->aConsider the following:
class A {
public:
int x() { return 5 }
}
class B: public A {
public:
int x() { return 20 }
int y;
}
int main() {
A v = B(); // `v` is a variable declared to be of type `Book` but is an instance of `B`
cout << v.x(); // this prints out 5 rather than 20
}The above outputs 5 because v is declared to be of type A, not B, so A::x runs rather than B::x, even though v is specifically an instance of B.
If we access a subclass through a superclass variable, the compiler will look only at the superclass - we cannot use subclass fields from v. When we did A v = B (coercing a B object into an A object), there was only enough memory allocated for a single A object, so extra fields like y would get truncated from the end. The compiler determined it is an A object, so v.y is an error. If subclass fields are out of order or get truncated, there is a compiler warning.
We can avoid this by using a pointer. A *w = new B() would no longer cut out the extra fields at the ends since there is still memory for all of them, but w->x() still prints out 5 because the compiler determines that it is an A object at compile time. Therefore, w->y results in an error. If subclass fields are out of order, then we get invalid memory accesses and undefined behaviour.
We can avoid this by using the virtual specifier for methods, which makes it so that the type of the object is considered at runtime, rather than from the type of the variable. So if A.x was declared as virtual int x() and A *w = new B(), the method to call when we do w->x() is decided at runtime from the value of w itself.
;wip: tutorial tomorrow about makefiles
The process of virtual methods being resolved to the correct one at runtime is known as dynamic dispatch. We use this by putting virtual in the superclass. Dynamic dispatch is the process of choosing which method to call at runtime based on the type of a value.
Dynamic dispatch is used when we can't decide which exact method to call at compile time. It is slightly slower than static dispatch (the default), which is why we should use it sparingly. Java has every call use dynamic dispatch, one of the reasons it is slow.
Dynamic dispatch lets us use polymorphism - the ability to use multiple types under one abstraction.
For example, we might have an array of A objects, and in this array we could keep A and B instances. So when we call the x method on each element in the array, it actually executes the correct method of each object. In this case the types are A and B and the abstraction is an array.
Consider the following code:
class x {
int *x;
public:
x(int n): x(new int[n]) {}
virtual ~x() { delete [] x } // WE HAVE TO USE `virtual` HERE FOR THE RIGHT DESTRUCTOR TO BE CALLED
}
class y: public x {
int *y;
public:
y(int k, int n): x(k), y(new int[n]) {}
~y() { delete [] y } // when called, this will automatically also call the destructor of its base class, `~x()`
}
int main() {
x *a = new y(10, 20);
delete a; // this calls the correct destructor because the destructor of the base class is virtual
}We should always implement the destructor of a virtual class, and make it virtual, because otherwise when we have a polymorphic variable with the type of the base class, it will not call the destructors of the subclasses.
A pure virtual method is one where the virtual method of the base class is not implemented, perhaps because the class is so abstract that it is only meant to be subclassed, never itself instantiated. So we cannot declare a variable of this type or call its constructor.
We write one of these method using something like virtual int k() = 0;. This specifies that we intentionally did not implement k in this class - that we want subclasses to implement it.
Classes with any pure virtual methods cannot be instantiated because they are abstract classes - at least one of the methods is still missing an implementation. A class that is not abstract is a concrete class - a class without pure virtual methods.
Subclasses of an abstract class are also abtract unless they implement all of the pure virtual methods it inherits.
In UML, pure virtual method names, as well as abstract class names, are written in italics. Also, static method/field names are underlined and protected method/field names are prefixed with "#".
When we call the copy constructor of a subclass B where only the base class A has a copy constructor, the default copy constructor for B is called. The default copy constructor calls the copy constructor for the base class, A, and then does a shallow copy on B - it copies the instance field by field.
The default copy constructor is therefore roughly equivalent to B &B::B(const B &other): A(other), y(other.y). We can do the same thing for operator=, since the default operator= works in almost the same way: B: &B::operator=(const B &other) { A::operator=(other); y = other.y }. As before, we still need to consider heap memory and such.
Consider the following:
class A {
int x, y;
public:
A();
A &operator=(const A &other);
}
class B: public A {
// ...
}
int main() {
B b1(), b2();
A *pb1 = &b1, *pb2 = &b2;
*pb1 = *pb2; // partial assignment because we used `A::operator=`
}Partial assignment is when we try to assign something using an operator= that is for a superclass. For example, if B used a concrete A::operator=, and we tried to assign a B object into a B object, then it would only assign the fields of A into the B object, ignoring the fields of B. This is because the implementation of A::operator= is not aware of the fields of B.
We could try to fix it as follows:
class A {
int x, y;
public:
A();
virtual &operator=(const A &other);
}
class B: public A {
// ...
public:
B &operator=(const A &other) {
// we have to accept `A` objects in order to properly override `A::operator=`
}
}
int main() {
B b();
b = A(); // mixed assignment because we used `B::operator=`
// extra fields of `b` are now unknown values
}Mixed assignment is when we try to assign other classes into an instance of the current class. For example, if B implemented B::operator= to override A::operator=, it would have to accept an A object for its parameter. As a result, it would be possible to pass an A object to a B object, which causes mixed assignment.
A pure virtual method can actually have an implementation, which is occasionally useful. A pure virtual method is simply a method that subclasses must override, or otherwise the subclass becomes an abstract class.
We can do this by declaring a method like void f() = 0; in the header file, and in the source file implementing it normally, like void BASE_CLASS::f() { }. We do this because then we can call BASE_CLASS::f() inside of our subclass methods.
Now we can do the above using something like the following:
class A {
int x, y;
protected:
virtual &operator=(const A &other);
public:
A();
virtual ~A() = 0;
}
class B: public A {
// ...
public:
B &operator=(const B &other) {
A::operator=(other);
// rest of the fields can be copied here
return *this;
}
}
class C: public A {
//...
}This avoids partial assignment because we can assign the remaining fields in B::operator=, and avoids mixed assignment because we can only pass B objects to B::operator=.
Also known as a publish-subscribe model. There is a publisher/subject that generates data, and any number of subscribers/observers that receive data and react to it. Basically, this allows subscribers to automatically update when the publisher's data changes.
For example, the publisher could be a temperature sensor and a subscriber could be a thermostat that controls the furnace and air conditioning. In a spreadsheet individual cells are publishers and other cells can subscribe to them.
This allows us to add features to an object while it is running. For example, a window might be decorated with a scrollbar and a text field.
For example:
Component *c = new Component();
c = new Decorator2(c);
c = new Decorator1(c);
c = new Decorator2(c);
delete c;We must be careful to make sure the destructors are correctly implemented to avoid leaking memory.
;wip: GDB stuff
A factory method is a method that creates objects for us, without having to specify which exact type of object to create. The factory method pattern is a design pattern in which these factory methods are used.
The factory methods are often implemented as an abstract creator class that specify the interface, plus multiple possible concrete creator classes that result in an instance of the product class (which is often abstract and we give instances of subclasses).
class Level {
public:
virtual Enemy *createEnemy() = 0; // this is a factory method
}
class NormalLevel: public Level {
public:
Enemy *createEnemy() {
// normal levels would have higher probability of creating turtles randomly rather than bullets
}
}
class CastleLevel: public Level {
public:
Enemy *createEnemy() {
// the castle level would have a higher probability of producing a bullet rather than turtles
// we might also check game progress and generate a boss when we get to a certain point
}
}
int main() {
Level *l = new NormalLevel;
Enemy *e = l->createEnemy(); // the factory method calls the level function to give the correct probability of getting a turtle or a bullet
// we did not call the constructor for an enemy, but the factory method calls it for us
// we also did not have to decide whether to create a turtle or a bullet, since `createEnemy` decides for us
}We can also implement factory methods in a base class as a template method that is filled in in subclasses. This is also an example of this pattern.
The singleton pattern works quite well with factory methods. For example, in this game a boss might be implemented as a singleton class, so that there can only be one of them. In this case, the factory method would simply call getInstance and obtain a boss instance.
The template method pattern is a design pattern where we override some behaviour from a superclass, but not all of it - the superclass is used as a template for the subclass.
A template method is one that outlines an algorithm, but might have some steps of the algorithm call virtual methods (often private), which are actually implemented in subclasses. A template method can do most of the work, but the subclasses are reponsible for implementing those last missing pieces:
class Turtle: public Enemy {
void drawHead() {
// draw the turtle head
}
virtual void drawShell() = 0; // we used pure virtual but could also provide a default implementation
void drawTail() {
// draw the turtle tail
}
public:
draw() {
drawHead();
drawShell(); // this is not yet implemented
drawTail();
}
}
class BigTurtle: public Turtle {
void drawShell() {
// actually draw then shell here
}
}Templates in C++ have nothing to do with the template method pattern. They are a very complex topic, but are very useful.
Consider the linked list implementation:
class Node {
int data;
Node *next;
public:
Node(int data, Node *next): data(data), next(next) {}
~Node() { delete next; }
int getData() { return data; }
Node *getNode() { return next; }
};
int main() {
Node *ll = new Node(1, new Node(2, 0));
// ...
delete ll;
}This can only hold a list of int. However, if we want to store other types of objects, we have to either use void * pointers or templates.
A template is a class parameterized over one or more types:
template<typename T> class Node {
T data; // this data is of type `T`
Node<T> *next; // `Node<T>` refers to this class parameterized over the same type
public:
Node(T data, Node<T> *next): data(data), next(next) {}
~Node() { delete next; }
T getData() { return data; }
Node<T> *getNode() { return next; }
}
int main() {
Node<char> *ll = new Node<char>('a', new Node<char>('b', 0))
// `ll` is a linked list of characters
// ...
delete ll;
}The template keyword allows us to declare that the following is parameterized over the type T. So inside the part that follows, T refers to a typename that we can specify in our client code.
The Node<SOME_TYPE_GOES_HERE> is a template specialization. The name of the class is still Node, but we still need to write <T> when it is ambiguous what type T might be. This allows us to have a linked list of whatever type we want.
The compiler, when encountering a template specialization like Node<int>, creates in memory a new class identical to Node with T replaced with the actual type. This is similar to the preprocessor, but more powerful, and also typesafe. In Java, templates are similar to generics.
We can even do things like Node< Node<int> > or even more nested structures. However, note that Node<Node<int>> doesn't compile because >> is a right shift operator, so we need to add a space.
This is a huge library of many templates implementing everything from algorithms to data structures. One of the most useful are dynamic length arrays:
#include <vector>
int main() {
std::vector<int> v;
v.push_back(1); v.push_back(2); v.push_back(3);
// now `v` has 1, 2, 3
// `v` will resize itself as needed to store all the items
for (int i = 0; i < v.size(); i ++)
std::cout << v[i] << std::endl; // array access with no range check
for (int i = 0; i < v.size(); i ++)
std::cout << v.at(i) << std::endl; // array access with range checking (impossible to get out of bounds error)
for (std::vector<int>::iterator i = v.begin(); i != v.end(); i ++)
std::cout << *i << std::endl; // RECOMMENDED WAY OF ITERATING THROUGH A DATA STRUCTURE
}The iterators of data structures expose the same interface, which allows us to abstract enumeration of the objects in the structure. For example, we can use the same syntax to iterate through a linked list or a tree, where a normal for loop would need to be customized for each one. The iterator is an abstraction of a pointer.
v.begin() is the first element of the vector, while v.end() is one past the last element.
Many ordered data structures also have something like vector<int>::reverse_iterator, which works the same as vector<int>::iterator, but starts at the end and goes toward the beginning. For this we use v.rbegin() to start and v.rend() in the for loop condition.
Since iterators are simply abstractions over pointers, we can use them like pointers. v.erase(v.begin()) removes the first element, v.erase(v.begin() + 3) removes the fourth, and v.erase(v.end() - 1) removes the last.
Another useful data structure is the unordered dictionary:
#include <map>
int main() {
std::map<string, int> m;
m["some string"] = 1;
m["some other string"] = 45;
m["something else"] = 56;
m.erase("some other string"); // overloaded version of `m.erase` that accepts a key
m.erase(m.begin()); // delete an arbitrary element
std::cout << m.count("nonexistant") << std::endl; // this is the number of keys that match a given key; in a map, this can only be 0 or 1, but other data structures might support duplicate keys
std::cout << m["some string"] << std::endl;
for (map<string, int>::iterator i = m.begin(); i != m.end(); i ++)
std::cout << *i << std::endl; // element is not
}The visitor pattern is used in order to do double dispatch - dispatching methods based on the type of multiple objects. It is also used for adding functionality to to a class heirarchy without changing any of the classes in the heirarchy.
Consider the following:
class Enemy { ... };
class Weak: public Enemy { ... };
class Strong: public Enemy { ... };
class Weapon { ... };
class Rock: public Weapon { ... };
class Stick: public Weapon { ... };Suppose we want to add a strike() method that strikes an Enemy. What it does should depend on both the type of the enemy and the type of the weapon.
We could put the method as virtual void Enemy::strike(Weapon &w), but it would only be dynamic dispatch based on the type of Enemy.
We could put the method as virtual void Weapon::useOn(Enemy &w), but it would only be dynamic dispatch based on the type of Weapon.
The solution is to combine overriding with overloading - the visitor pattern:
class Enemy {
...
public:
virtual void strike(Weapon &w) = 0;
};
class Weak: public Enemy {
...
public:
// this method is dynamically dispatched based on the enemy type
void strike(Weapon &w) { w.useOn(*this); } // the body is then dynamically dispatched based on the weapon type
};
class Strong: public Enemy {
...
public:
void strike(Weapon &w) { w.useOn(*this); }
};
class Weapon {
...
public:
virtual void useOn(Weak &e) = 0;
virtual void useOn(Strong &e) = 0;
};
class Rock: public Weapon {
...
public:
void useOn(Weak &e) { ... };
void useOn(Strong &e) { ... };
};
class Stick: public Weapon {
...
public:
void useOn(Weak &e) { ... };
void useOn(Strong &e) { ... };
};
int main() {
Enemy *e = new Bullet;
Weapon *w = new Stick;
c->strike(*w); // this calls the correct method now
}Note that the correct useOn method is called automatically based on which type of Enemy and which type of Weapon. This is the purpose of the visitor pattern.
The visitor pattern also allows us to add functionality to a class heirarchy without changing the heirarchy itself. This is done by having the methods accept visitors. For example:
class BookVisitor { // abstract class
public:
visit(Book &b) = 0;
visit(CSBook &b) = 0;
visit(OtherBook &b) = 0;
};
class Book {
...
public:
virtual void accept(BookVisitor &v) { v.visit(*this); }
};
class CSBook {
...
public:
virtual void accept(BookVisitor &v) { v.visit(*this); } // overloading based on the type of `*this`
};
class OtherBook {
...
public:
virtual void accept(BookVisitor &v) { v.visit(*this); }
};BookVisitor and the rest of the class heirarchy is often implemented by the author. For example, the following counts the number of each type of object:
#include <map>
using namespace std;
class Catalogue: public BookVisitor {
int books = 0, csbooks = 0, otherbooks = 0;
public:
visit(Book &b) { books ++; };
visit(CSBook &b) { csbooks ++; };
visit(OtherBook &b) { otherbooks ++; };
friend operator<<(ostream &out, Catalogue &c);
};
ostream &operator<<(ostream &out, Catalogue &c) { out << "Books: " << books << "\tCSBooks: " << csbooks << "\tOtherBooks: " << otherbooks; }
int main() {
vector<book> collection;
collection.push_back(new CSBook("A", "B", 200, "C++"));
collection.push_back(new Book("C", "D", 400));
// here we add the books to the collection
Catalogue c;
for (vector<book>::iterator i = collection.begin(); i != collection.end(); i ++) (*i)->accept(v); // visit every book
cout << c;
}Also, for std::map if the key doesn't exist when we try to access it with SOME_MAP[SOME_KEY], the key is automatically created and the value is initialized to the default value and returned. So a previously unused element of std::map<std::string, int> will be 0 when first accessed.
When we have a cyclic dependency, like A.h including B.h and B.h including A.h, we can restructure the code such that A.h includes B.h, and B.h simply uses forward declarations of all the things it needs. For example, the resolve cyclic dependencies we frequently need to use forward declarations of classes: class A; would be in B.h to avoid the need to include A.h. If we do this, we often need to actually include A.h in B.cc.
This is an extension of the "pImplementation" idiom with subclasses to abstract alternate implementations. It is often found in graphical applications, like when we switch the window style or a backend engine.
The bridge pattern makes it easy to swap out implementations. It separates an abstraction from its implementation so we can change either separately.
Casting allows us to bypass the type system - a manual override for type checking. In C, its syntax appeared as Node n; int *p = (int *)&n;.
Casting is difficult to get right and is a common source of bugs. It is
C++ has 4 types of casts. These casts stands out more in the code and have some small restrictions.
static_cast simply converts one type to another: int i = static_cast<int> some_double.
reinterpret_cast converts one type to another without checking if it is reasonable: Vec v; Book *b = reinterpret_cast<Book *>&v.
static_cast, but it will also try to cast even if it doesn't make sense.const_cast converts a constant type into a non-constant type, or a non-constant type to a constant type: const int i = 5; *(const_cast<int *>&i) = 6;
dynamic_cast safely converts one type to another: Book *b = &some_book; CSBook *c = dynamic_cast<CSBook *>b.
Casting allows us to do things like converting a Book pointer to a CSBook object back into a CSBook pointer.
dynamic_cast gives us runtime type information, and allows code to make decisions based on the runtime type of an object, since if the cast doesn't work the value is null. For example, if (dynamic_cast<CSBook *>b) { ... } does something if b is a CSBook. However, this should be avoided because it is highly coupled - it is inflexible to changes in the class heirarchy.
;wip: exceptions
This work by Anthony Zhang is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright 2013-2017 Anthony Zhang.