ece244notes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <big>Complete Notes</big><br>ECE244 : Programming Fundamentals\n",
    "\n",
    "&nbsp;&nbsp;&nbsp; Yvonne Yang\n",
    "&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp; University of Toronto\n",
    "&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp; Last updated: 2021/02/02  \n",
    "\n",
    "---  \n",
    "\n",
    "Welcome to the ECE244 notebook.  \n",
    "\n",
    "In this magic notebook, you will see notes as well as pieces of C++ code that you can interact with.  \n",
    "\n",
    "## Table of Contents  \n",
    "* [How to use this notebook](#tut)\n",
    "* [09/15 - Introduction to C++](#09/15)  \n",
    "* [09/16 - Function Prototypes & Compilation](#09/16)   \n",
    "* [09/17 - The C Preprocessor & More Compilation](#09/17)  \n",
    "* [09/22 - Classes & Objects](#09/22)  \n",
    "* [09/23 - Classes & Objects](#09/23)  \n",
    "* [09/24 - Classes & Objects - Program Organization and Constructors](#09/24)  \n",
    "* [09/29 - Classes & Objects- Destructor and 'this' pointer](#09/29)  \n",
    "* [09/30 - C++ I/O - Console input](#09/30)  \n",
    "* [10/01 - C++ I/O - Cin errortrapping](#10/01)  \n",
    "* [10/06 - C++ I/O - The getline function and custom streams](#10/06)  \n",
    "* [10/07 - C++ I/O miscellaneous and Pointers, Scopes, Arrays ](#10/07)  \n",
    "* [10/08 - Pointers, Scopes, Arrays ](#10/08)  \n",
    "* [10/13 - Pointers, Scopes, Arrays ](#10/13)  \n",
    "* [10/14 - Pointers, Scopes, Arrays ](#10/14)  \n",
    "* [10/15 - Pointers, Scopes, Arrays & Operator overloading](#10/15)  \n",
    "* [10/20 - Operator overloading & copy constructor](#10/20)  \n",
    "* [10/21 - Operator overloading example](#10/21)  \n",
    "* [10/27 - Objects that contain pointers](#10/27)  \n",
    "* [Fun extra stuff - classes](#extra1)  \n",
    "* [Fun extra stuff - operator overloading](#extra2)  \n",
    "* [11/03 - Linked Lists](#11/03)  \n",
    "* [11/05 - Recursion](#11/05)  \n",
    "* [11/17 - Binary tree](#11/17)  \n",
    "* [11/18 - Binary tree & Inheritance](#11/18)  \n",
    "* [11/24 - Inheritance](#11/24)\n",
    "* [11/25 - Inheritance](#11/25)\n",
    "* [11/26 - Inheritance](#11/26)\n",
    "* [12/01 - Inheritance](#12/01)\n",
    "* [Fun extra stuff - inheritance](#extra3)  \n",
    "* [12/02 - Inheritance](#12/02)\n",
    "* [12/03 - Complexity Analysis](#12/03)\n",
    "* [12/08 - Complexity Analysis](#12/08)\n",
    "* [Extra - STL](#extra4)\n",
    "* [Extra - Graphs](#graph)\n",
    "* [Extra - Miscellaneous](#extra99)\n",
    "---  \n",
    "To start, move to the next cell and press \\<Shift+Enter> to execute it. \n",
    "\n",
    "\\**Note: It is crucial to run this set-up cell before you test out anything else on this notebook, as it imports the necessary libraries.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "/*** Set up this notebook ***/\n",
    "#pragma once\n",
    "#include <iostream>\n",
    "#include <string>\n",
    "#include <iomanip>\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How to use this notebook  <a class = \"anchor\" id = \"tut\"></a>\n",
    "\n",
    "Thanks to Jupyter Notebook and Xeus Cling, we can do many interesting things here.  \n",
    "You will never have to go through the pain of making files and projects just to output \"hello world\". You can print it directly (see next cell). You can declare variables and play with them. You can also do fast computations here, treating the notebook as a calculator.  \n",
    "Test these out below.  \n",
    "<br>\n",
    "\\**Note: Even here, C++ does not allow duplicate definitions of variables. It's good practice to use braces to make an anonymous cell with temporary variables so that it can be run multiple times.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hello world"
     ]
    }
   ],
   "source": [
    "cout << \"hello world\";"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Your variable ece = 244"
     ]
    }
   ],
   "source": [
    "{\n",
    "    int ece = 244;\n",
    "    cout << \"Your variable ece = \" << ece;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.397208"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "log(1024*32) // Computations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 09/15 - Introduction to C++ <a class=\"anchor\" id=\"09/15\"></a> \n",
    "---\n",
    "### An example program \n",
    "A standard cpp program is shown here:\n",
    "```cpp\n",
    "#include <iostream>\n",
    "using namespace std;\n",
    "\n",
    "int main () {\n",
    "    cout << \"Hello world!\" << endl; // see below\n",
    "    return (0);\n",
    "}\n",
    "\n",
    "// Recall that in C this is equivalent to \n",
    "// printf(\"Hello World!\\n\");\n",
    "```\n",
    "\\**Note: This main method won't run here but will run in a separate .cpp file.*  \n",
    "\n",
    "Explanations of the above program \n",
    "- `<iostream>` is the standard I/O library for cpp. Notice the use of angle brackets and the ommission of the \".h\"\n",
    "- `namespace` is a container for names; allows code to flow without conflict of variable names from diff programs. `namespace std` allows us to use functions like `cout` and `endl` without having to write `std::cout` and `std::endl` every time.  \n",
    "\\* To disambiguate the variable, say `cout`, that we're using without specifying the whole namespace, replace the `using namespace...` line with `using std::cout`\n",
    "- `main` function is the entry point of the program\n",
    "- `cout` stands for console output, `cin` is console input\n",
    "- `<<` is called a \"stream insertion operator\", for now, think of it as \"send to\"\n",
    "- `endl` indicates end of line like '\\n' in C   \n",
    "\n",
    "Test out console input and output below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1234\n",
      "Your integer: 1234"
     ]
    }
   ],
   "source": [
    "/* Enter an integer and have it outputted */\n",
    "{\n",
    "    int integer;\n",
    "    cin >> integer; // in\n",
    "    cout << \"Your integer: \" << integer; // out\n",
    "}\n",
    "// equivalent to scanf (\"%d\", &integer); in C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Variables in C++\n",
    "- declarations are just as in C\n",
    "- there is a new type called \"bool\" for boolean values (true or false)\n",
    "```cpp\n",
    "bool coding = true;\n",
    "```\n",
    "\n",
    "The metatype **auto**  \n",
    "- a C++ keyword used in place of a type declaration so that the compiler deduces the type from the initializer\n",
    "```cpp\n",
    "auto length = 6; // the variable count automatically becomes of type int  \n",
    "auto maxLen = length; // compiler looks at count and matches maxCount to the type of count  \n",
    "auto minLen = length;\n",
    "```\n",
    "- say you create some variables of the same type, then decide to change the data type for all of them, then auto really saves time!\n",
    "```cpp\n",
    "// To change length and related variables' types, simple do:\n",
    "auto length = 6.0;\n",
    "```\n",
    "- **Warning**: cannnot use auto without initialization! Results in compiler error!  \n",
    "\n",
    "### Constants (\\* not course material)  \n",
    "Keyword `constexpr`\n",
    "- very similar to `const`, but is for functions/expressions. For example:  \n",
    "```cpp\n",
    "constexpr double GetPi() {return 22.0/7;}\n",
    "// the following also works\n",
    "constexpr double TwicePi() {return GetPi()*2;}\n",
    "```\n",
    "- in C++11, this is better than `const` because it evaluates the expression at compile time, instead of runtime, thus making the program run faster\n",
    "\n",
    "### Expressions and statements\n",
    "- including arithmetic and logic expressions (+,/,<,etc.), if-else if-else, while, for\n",
    "- all similar to C  \n",
    "\n",
    "### Strings\n",
    "- in C, strings are character arrays and you must remember their terminating null character\n",
    "- C++ improves this by providing a data type called string (remember to `#include <string>`)  \n",
    "\n",
    "Below is a demo of functions on C++ strings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I code in C\n",
      "I code in C++\n"
     ]
    }
   ],
   "source": [
    "/* C++ built-in string functions */\n",
    "{\n",
    "string s1 = \"I code\";\n",
    "string s2 = \"in C\";\n",
    "string str = s1 + \" \" + s2; // concatenation with + operator\n",
    "cout << str << endl;\n",
    "\n",
    "if (str.find (\"C++\") == string::npos) // substring not found\n",
    "{\n",
    "    unsigned int size = str.size(); // length of string; alternatively, use str.length()\n",
    "    str.resize(size + 2, '+'); // resize string and fill the new spaces with '+'\n",
    "    cout << str << endl;\n",
    "}\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Functions  \n",
    "- like in C, parameter is passed by value: if you pass `y` into `int foo(int v)`, then `v` becomes a copy of `y` and `foo` cannot change `y`'s value  \n",
    "\n",
    "The good ol' swap-two-variables function:  \n",
    "- in C, we have to write:  \n",
    "```c\n",
    "void swap (int* x, int* y)\n",
    "{\n",
    "    int temp = *x;\n",
    "    *x = *y;\n",
    "    *y = temp;\n",
    "}\n",
    "```  \n",
    "and if we have `int a` and `int b`, call the function with \n",
    "```cpp\n",
    "swap(&a, &b);\n",
    "```\n",
    "- syntactic sugar in C++: `void swap (int & x, int & y)` tells cpp to pass by **reference** instead of **value**. So we can simply write:  \n",
    "```cpp\n",
    "void swap (int & x, int & y)\n",
    "{\n",
    "    int temp = x;\n",
    "    x = y;\n",
    "    y = temp;\n",
    "}\n",
    "```  \n",
    "and if we have `int a` and `int b`, call the function with \n",
    "```cpp\n",
    "swap(a, b);\n",
    "```\n",
    "- note that this overloads the symbol `&` and is different from the reference operator `&`  \n",
    "\n",
    "Some esoteric swap functions without using a `temp` variable:\n",
    "```cpp\n",
    "void swap(int& x, int& y){\n",
    "    x = x+y;\n",
    "    y = x-y;\n",
    "    x = x-y;\n",
    "}\n",
    "```\n",
    "- note that this won't work for too large numbers or if x=y  \n",
    "\n",
    "```cpp\n",
    "void swap(int& x, int& y){\n",
    "    x = x^y; // bitwise XOR\n",
    "    y = x^y;\n",
    "    x = x^y;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 09/16 - Function Prototypes & Compilation <a class=\"anchor\" id=\"09/16\"></a>\n",
    "---  \n",
    "&nbsp;&nbsp;&nbsp;\\* file extensions: .cxx or .cc or .cpp are all good  \n",
    "\n",
    "### Function prototype  \n",
    "- the problem: in C++ as in other languages, functions must be defined before they're called\n",
    "- a solution: when a function calls another function foo(), put a prototype of foo() at the start of the function\n",
    "    - problem: have to do this for every single function that calls foo()\n",
    "- a better solution: put a global function prototype foo() at the start of the program (below global variable declarations)\n",
    "\n",
    "### Compiling/Executing the program\n",
    "- a compiler takes a source file and generates object code files that contains machine language (from .cc/.cpp/.cxx to .o)  \n",
    "- a linker then organizes these object code files to create an executable file (from .o to, for example, .exe)\n",
    "\n",
    "Types of errors (from lowest level to highest level):\n",
    "- **syntax errors**:  \n",
    "  the form/grammar of code is wrong. eg. `int a = 1` is missing a semicolon, `if (a && b = c)` is also bad form  \n",
    "- **semantic errors**:   \n",
    "  the meaning of some code is undefined. eg. `float f = 'e'` is assigning a character to a float\n",
    "- **run-time errors**:  \n",
    "  errors that happen during execution time. eg. `double result = 14/0` is the classic division-by-zero error\n",
    "- **logical errors**:  \n",
    "    correct code but not desirable behavior; hardest to debug since undetectable by compiler\n",
    "- start from debugging the lower level errors (you cannot run a program without passing compiler tests), move on to high level errors. This might raise lower level issues again, so repeat. This is called the **development cycle**.\n",
    "- try using the command line to compile and run your program! :D  \n",
    "\n",
    "For example, if you have a source file called \"myprog.cc\", compile and run it like this:  \n",
    "```\n",
    "g++ myprog.cc -o myprog.exe\n",
    "myprog.exe\n",
    "```\n",
    "Explanation of above code\n",
    "- `g++` is the GNU C++ compiler\n",
    "- `-o` tag helps name the output file to a name of our choosing, in this case, \"myprog.exe\". We need to name it since an .exe file is compiled from multiple source files\n",
    "- calling `myprog.exe` executes the program"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 09/17 - The C Preprocessor and More Compilation <a class=\"anchor\" id=\"09/17\"></a>\n",
    "\n",
    "---  \n",
    "### More on Compilation\n",
    "Compiling multiple files at the same time  \n",
    "```\n",
    "g++ main.cc square.cc squareRoot.cc -o myprog.exe  \n",
    "```  \n",
    "separate compilation: \n",
    "- first, compile each source file to an object file. These files are called **partial executables**  \n",
    "- next, use the compiler again to merge all object files into one executable file. This process is called **linking**  \n",
    "```\n",
    "g++ -c main.cc\n",
    "g++ -c squared.cc\n",
    "g++ -c squareRoot.cc\n",
    "g++ main.o squared.o squaredRoot.o -o myprog.exe\n",
    "```\n",
    "- the `-c` flag tells compiler to only run preprocess, compile, and assemble steps\n",
    "- this is advantageous when we are debugging individual files, so that we can save time by only compiling the files that changed. Note also that linking is a lot faster than compiling  \n",
    "    - say we changed \"main.cc\", then we only need to call command \\#1 and 4\n",
    "    - (Tricky!) say we changed \"squared.h\", the header file for \"squared.cc\", then we need to call commands  \\#1, 2, and 4 again  \n",
    "- keeping track of what changed can be tricky...  \n",
    "\n",
    "compiling with the cmd `make`\n",
    "- the command `make` creates shortcuts of the commands you need to type with a MakeFile. You can simply call\n",
    "```\n",
    "make\n",
    "```  \n",
    "to compile your program now!\n",
    "- `make` checks if the timestamp of a source file is more recent than its compiled object file. If so, it compiles that source file again  \n",
    "\n",
    "### The C Preprocessor<a class=\"anchor\" id=\"preproc\"></a>\n",
    "\n",
    "The best program organization:  \n",
    "- splitting the program into files helps compile faster - **parallel compilation**\n",
    "- put each function in their own .cpp file\n",
    "- put the prototypes of similar functions in a header file\n",
    "\n",
    "The `#include` direction \n",
    "- The `#include \"foo.h\"` direction tells the C preprocessor to take contents of \"foo.h\" and dump them where the include statement is. Do this at the top of \"foo.cpp\" and any other file that needs these prototypes.\n",
    "The `#define` direction\n",
    "- an example usage: `#define PI 3.14`\n",
    "- the preprocessor substitues 3.14 for PI anywhere it appears in the program.\n",
    "- note that PI does not have a data type! It is **not** a variable.\n",
    "\n",
    "The `#pragma once` direction\n",
    "- Beware of including variables! You can't declare two variables with the same name in cpp  \n",
    "- `#pragma once` checks if a file has been included before and skips it\n",
    "- especially helpful when you include headers that include other headers\n",
    "- before `#pragma once` appeared, people have to use if-statements in the preprocessor directives:\n",
    "```cpp\n",
    "#ifndef PI\n",
    "#define PI 3\n",
    "#else  /* do something else */\n",
    "#endif\n",
    "```  \n",
    "or something like the trick we use for doing something special in the first iteration of a loop:\n",
    "```cpp\n",
    "bool first = true;\n",
    "while(/*...*/) {\n",
    "    if (first) {\n",
    "        /* do something */\n",
    "        first = false;\n",
    "    }\n",
    "}\n",
    "```\n",
    "except now it's for the preprocessor, and we put it in every header  \n",
    "```cpp\n",
    "#ifndef MY_FLAG\n",
    "#define MY_FLAG\n",
    "int my_global = 1;\n",
    "#endif\n",
    "```  \n",
    "Note that the flag name in every header file must be unique\n",
    "\n",
    "\n",
    "Use the -E flag while compiling to only run the preprocessor\n",
    "```\n",
    "g++ -E main.cpp\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 09/22 - Classes and Objects <a class=\"anchor\" id=\"09/22\"></a>\n",
    "---  \n",
    "### Program Organization\n",
    "header files provide a template of the functions to implement, so they're called **definition files**  \n",
    "using header files is good practic because\n",
    "- they serve as a \"contract\" b/w collaborators\n",
    "- they facilitate software releases\n",
    "\n",
    "### More on The C Preprocessor\n",
    "older ways of doing `#pragma once`: two ways of using `#ifndef` (see [The C Preprocessor](#preproc))  \n",
    "\n",
    "### Classes\n",
    "recall struct in C, it's very similar to classes  \n",
    "An example class:\n",
    "```cpp\n",
    "class Date{\n",
    "    int year;\n",
    "    int month;\n",
    "    int day;\n",
    "    \n",
    "    void printDate();\n",
    "    void setDate(int year, int month, int day);\n",
    "    int nthDayOfYear();\n",
    "    int difference (Date other);\n",
    "};\n",
    "```\n",
    "- keyword `class` indicates everything that follows is the class definition\n",
    "- the word right after `class`, `Date`, is the name of the class\n",
    "- a class can have variable members (like a struct) as well as function members!\n",
    "- <span style=\"color:red\">Note to self</span>: remember to include the semicolon at the end!  \n",
    "\n",
    "\\* *Note: all the variables are stored in \"contiguous\" memory blocks, subject to alignment constraints*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 09/23 - Classes and Objects cont'<a class=\"anchor\" id=\"09/23\"></a>\n",
    "---  \n",
    "- an object is an instantiated variable of a class type\n",
    "- creation of an object: \n",
    "```cpp\n",
    "Date christmas;\n",
    "``` \n",
    "creates an object of the type `Date` called `christmas`\n",
    "- use the dot operator (.) to access members:\n",
    "```cpp\n",
    "christmas.month = 12;\n",
    "christmas.day = 25;\n",
    "```  \n",
    "- member functions can be invoked in the same way:\n",
    "```cpp\n",
    "christmas.setDate(2020,12,25);\n",
    "christmas.printDate();\n",
    "```\n",
    "- note that you can't invoke member methods without specifying which object it belongs to\n",
    "- the methods of a class are immutable, so they're not stored in each specific object  \n",
    "\n",
    "method implementation:\n",
    "- instead of prototypes, simply put implementation of functions in braces after the argument list\n",
    "- to implement a function outside of the file where it's defined, use the scoping operator (::) to disambiguate between methods with the same name but belong to different classes, eg.\n",
    "```cpp\n",
    "void Date::setDate(int y, int m, int d){\n",
    "    year = y;\n",
    "    month = m;\n",
    "    day = d;\n",
    "}\n",
    "```\n",
    "  - this way is preferred as it enables us to put function implementations in different files -> separate compilation\n",
    "  - note that we don't have to specify which class `year` or `month` or `day` belongs to, since when we call `setDate`, we specify the object anyway! Also see [the 'this' pointer](#this) \n",
    "  - this is really important!!!  \n",
    "  \n",
    "Why provide function to change member variables instead of directly changing the variables?\n",
    "- firstly, we can provide error checking, eg.\n",
    "```cpp\n",
    "void Date::setDate(int y, int m, int d){\n",
    "    /* ... */\n",
    "    if (m < 0 || m > 12){\n",
    "        cout << \"Error, invalid month!\" << endl;\n",
    "    }\n",
    "    else{ month = m; }\n",
    "    /* ...*/\n",
    "}\n",
    "```  \n",
    "- for **encapsulation**, one of the cornerstone ideas of OOP, which prevents accidental changes to members of a class. For that purpose, we'll declare all class member variables `private`, so that they're not visible to other classes  \n",
    "  - if another class tries to access a private field, they will get a compile error  \n",
    "  - all members are private by default\n",
    "  - a member functino can access all variables of its class, regardless of private/public  \n",
    "  \n",
    "Below is a demo of all concepts in this lecture:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "My favorite day is: 2019/12/25\n"
     ]
    }
   ],
   "source": [
    "/* Demo of basic concepts of classes and objects */\n",
    "class Date{\n",
    "    private:\n",
    "    int year;\n",
    "    int month;\n",
    "    int day;\n",
    "\n",
    "    public:\n",
    "    void printDate(){\n",
    "        cout << year << \"/\" << month << \"/\" << day << endl;\n",
    "    }\n",
    "    \n",
    "    void setDate(int y, int m, int d){\n",
    "        /* could put error-checking here... */\n",
    "        year = y;\n",
    "        month = m;\n",
    "        day = d;\n",
    "    }\n",
    "    \n",
    "    /* more functions to be implemented... */\n",
    "    int nthDayOfYear();\n",
    "    int difference (Date other);\n",
    "};\n",
    "\n",
    "/* Making an object */\n",
    "Date christmas;\n",
    "christmas.setDate(2019, 12, 25);\n",
    "cout << \"My favorite day is: \";\n",
    "christmas.printDate();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 09/24 - More Program Organization and Constructors<a class=\"anchor\" id=\"09/24\"></a>\n",
    "---  \n",
    "### Program organization with classes:\n",
    "- as mentioned before, it's good practice to separate definition files from implementation files\n",
    "- example definition file for the class `Date`, \"Date.h\"\n",
    "```cpp\n",
    "#ifndef _date_h\n",
    "#define _date_h\n",
    "class Date{\n",
    "    private:\n",
    "      int day; int month; int year;\n",
    "    public: \n",
    "      void setDate(); /*...*/\n",
    "};\n",
    "#endif\n",
    "```\n",
    "  - use the same `#ifndef...#endif` convention as shown in the cell about [the C Preprocessor](#preproc)\n",
    "  - remember to include the flags as before\n",
    "- example implementation file for the class `Date`, \"Date.cpp\":\n",
    "```cpp\n",
    "#include \"Date.h\"\n",
    "/* other includes such as <iostream>...*/\n",
    "class Date{\n",
    "    /* implementation of methods */\n",
    "}\n",
    "```\n",
    "  - remember to include the header file at the start!!\n",
    "  \n",
    "### Initialization of objects  with constructors\n",
    "- at the end of the day, objects are nothing but fancy variables, so we'd want to initialize them\n",
    "- two ways: constructor & default member initializer  \n",
    "\n",
    "Constructor: a function written by the programmer that is **automatically** invoked every time an object is created\n",
    "- every class must have a constructor\n",
    "- there can be multiple constructors for each class\n",
    "- if none is specified by the programmer, C++ provides the **default constructor**, aka no-argument constructor, for you. This constructor does *not*initialize member variables properly, eg. pointers will be filled with garbage instead of NULL!\n",
    "1. to write your own no-argument constructor (also called **overloading** the no-argument constructor):  \n",
    "to define/prototype:  \n",
    "```cpp\n",
    "/* in the \"Date.h\" file */\n",
    "class Date{\n",
    "    private:\n",
    "      /* variables */\n",
    "    public:\n",
    "       Date();\n",
    "      /* methods */\n",
    "}\n",
    "```\n",
    "to implement:  \n",
    "```cpp\n",
    "/* in the \"Date.cpp\" file */\n",
    "Date::Date(){\n",
    "    day = 1;\n",
    "    month = 1;\n",
    "    year = 2020;\n",
    "}\n",
    "```\n",
    "when is it called?\n",
    "```cpp\n",
    "Date myBirthday; // automatically calls the default constructor\n",
    "```\n",
    "- `Date()` is the constructor. It does not have a return type (void/int/etc.) and has the same name as the class\n",
    "- normally a public instead of private method. Declare private when, for example, you'd like to partially construct an object or make a custom construction, but only to be used internally in the class\n",
    "- <span style = \"color:red\"> warning </span>: if you prototype the no-argument constructor, then C++ assumes you're implementing it. If it's not implemented, you get a compile-time error!\n",
    "- <span style = \"color:red\"> warning </span>: if you implement your custom constructor, then C++ does NOT provide the default constructor \n",
    "2. custom constructor that takes arguments  \n",
    "to define:\n",
    "```cpp\n",
    "/* in the \"Date.h\" file */\n",
    "class Date{\n",
    "    private:\n",
    "      /* variables */\n",
    "    public:\n",
    "        Date();\n",
    "        Date(int y, int m, int d);\n",
    "        Date(string s);\n",
    "      /* methods */\n",
    "}\n",
    "```\n",
    "invocation:\n",
    "```cpp\n",
    "Date midterm(\"October 23\");\n",
    "```\n",
    "- the compiler looks at the argument and chooses the constructor that matches that data type"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 09/29 - Destructor and 'this' pointer<a class=\"anchor\" id=\"09/29\"></a>\n",
    "---  \n",
    "### Destructors\n",
    "What happens right before an object is destroyed? C++ automatically calls a function called a **destructor**\n",
    "- the destructor helps the object say any \"last words\": last actions to take before the object disappears\n",
    "- <span style = \"color:red\">important</span>: it is C++ that wipes the memory, not your custom destructor\n",
    "- for now, just know that destructors exist, later we'll see its use [(pointers in objects)](#10/27)\n",
    "\n",
    "Definition:\n",
    "```cpp\n",
    "/* in \"Date.h\"... */\n",
    "public class Date{\n",
    "    /* member variables and other functions*/\n",
    "    public:\n",
    "    ~Date(); // this may look like a dash but it's a tilde!!\n",
    "}\n",
    "```\n",
    "- the destructor is a member of the class\n",
    "- named tilde followed by the same name as class\n",
    "- has no argument, no return type\n",
    "- usually public not private\n",
    "\n",
    "\\*There can only be one destructor, and it must exist. If not specified, an empty one is given.\n",
    "\n",
    "### The 'this' Pointer <a class=\"anchor\" id = \"this\"></a>\n",
    "- every member method is given the address of the object on which it is invoked\n",
    "- passed as hidden parameter to all non-static function calls\n",
    "- if a member is called within its own class, the compiler gives the address of the object in a pointer called `this`\n",
    "- think of it as a read-only variable that C++ provides\n",
    "- it appears only at the execution of that method\n",
    "- within the `Date` class, the following are equivalent:\n",
    "```cpp\n",
    "day = d;\n",
    "(*this).day = d;\n",
    "this->day = d;\n",
    "```\n",
    "- the arrow operator `->` is a shorthand for `(*pointer).member`\n",
    "- note the brackets: field access (dot operator) has higher precedence than the dereference operator (asterisk)!\n",
    "- `this` is a constant pointer, so we can't do eg.\n",
    "```cpp\n",
    "void change(Date *other) {\n",
    "    this = other;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 09/30 - C++ I/O<a class=\"anchor\" id=\"09/30\"></a>\n",
    "---  \n",
    "### Topics\n",
    "- notion of stream\n",
    "- how inputs are handled\n",
    "- error handling\n",
    "- how outputs are formatted\n",
    "- briefly cover file streams  \n",
    "\n",
    "### Stream\n",
    "- a stream is a sequence of characters sent to output/input devices from the computer\n",
    "- the computer needs to convert between characters (eg. '5') and their machine representations (eg. 0000 0101), since devices only understand streams\n",
    "- `cin` is for input stream\n",
    "- `cout` is normal output\n",
    "- `cerr` is output for error messages\n",
    "\n",
    "### The input stream\n",
    "- program takes in characters and stores in part of OS called a keyboard buffer\n",
    "- when you hit \\<Enter>, the input stream is sent to `cin` to be made sense of\n",
    "- only sends after \\<Enter> so that user can change the input as needed  \n",
    "\n",
    "See example below: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input: 103 20.4\n",
      "\n",
      "x = 103\n",
      " y = 20"
     ]
    }
   ],
   "source": [
    "/* Example - reading integers */\n",
    "cout << \"input: \";\n",
    "int x, y;\n",
    "cin >> x >> y;\n",
    "\n",
    "cout << \"\\nx = \" << x << \"\\n y = \" << y;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "say we input '1' '0' '3' ' ' '2' '0' '.' '4' '\\n' for the above program\n",
    "- `cin` checks the first character, it's an integer so `cin` sends it, and moves the pointer to the next character\n",
    "- same for 2nd and 3rd character. Check, store, move pointer\n",
    "- when space is encountered, `cin` stops reading and leaves the rest of the stream for subsequent extractions\n",
    "- compiler goes on to next insertion argument y\n",
    "- `cin` skip over all spaces and starts pointer at the first integer after, which is '2'\n",
    "- `cin` similarly stores all digits of y as an integer and stops at the dot since it's not part of an integer\n",
    "- if stream is exhausted and there's a `cin` operation executing, it waits for more input\n",
    "\n",
    "**delimiters** are characters used to separate input items\n",
    "- in this case, the space and newline characters\n",
    "- in general, white spaces and tabs can be used as delimiters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input: Tarek Abdelrahman\n",
      "\n",
      "first name = Tarek\n",
      "last name = Abdelrahman"
     ]
    }
   ],
   "source": [
    "/* Example - using space to separate strings */\n",
    "{\n",
    "cout << \"input: \";\n",
    "string firstName, lastName;\n",
    "cin >> firstName >> lastName;\n",
    "\n",
    "cout << \"\\nfirst name = \" << firstName << \"\\nlast name = \" << lastName;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "say the input is \"Tarek Abdelrahman\"\n",
    "- \"Tarek\" will be stored in `firstName` and \"Abdelrahman\" in `lastName`\n",
    "\n",
    "### Errors from the Input Stream <a class = \"anchor\" id = \"err\"></a>\n",
    "- `cin` has a set of boolean variables called `cin` flags\n",
    "- `cin` fails silently if unaddressed\n",
    "- check with `cin.fail()`, which gives true if `cin` fails (think of this as an accessor function) \n",
    "\n",
    "See example below: \n",
    "- Note the dot operator!! This gives away the fact that `cin` is an object! It's of the type `istream`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input: five\n",
      "\n",
      "Bad input!!\n"
     ]
    }
   ],
   "source": [
    "/* Errorthrowing example */\n",
    "{\n",
    "cout << \"input: \";\n",
    "int a;\n",
    "cin >> a;\n",
    "if (cin.fail())\n",
    "    cout << \"\\nBad input!!\" << endl;\n",
    "else\n",
    "    cout << \"\\nYay, you entered an integer!\" << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/01 - C++ I/O <a class=\"anchor\" id=\"10/01\"></a>  \n",
    "---  \n",
    "\n",
    "### Input errors cont'  \n",
    "See\n",
    "[Errors from the input stream](#err).  \n",
    "\n",
    "Errortrapping: example of what doesn't work  \n",
    "```cpp\n",
    "int a;\n",
    "bool retry = true;\n",
    "while (retry)\n",
    "{\n",
    "    cin >> a;\n",
    "    if (cin.fail())\n",
    "        cout << \"\\nBad input!!\" << endl;\n",
    "    else\n",
    "    {\n",
    "        cout << \"\\nYay, you entered an integer!\" << endl;\n",
    "        retry = false;\n",
    "        /* do stuff with your int */\n",
    "    }\n",
    "}\n",
    "```\n",
    "This doesn't work, because\n",
    "- when `cin` reads bad input, it leaves the stream unchanged and the pointer at the same place\n",
    "- if an invalid sequence is inputted, `cin` raises the fail flag, prints error message, goes back and tries to read the same character again, which is still invalid\n",
    "- moreover, the `cin.fail()` flag stays raised forever if we don't lower it\n",
    "- this results in an infinite loop  \n",
    "\n",
    "Let's add in two lines:\n",
    "```cpp\n",
    "int a;\n",
    "bool retry = true;\n",
    "while (retry)\n",
    "{\n",
    "    cin >> a;\n",
    "    if (cin.fail()){\n",
    "        cout << \"Bad input!!\" << endl;\n",
    "        cin.clear(); // resets the flags to normal\n",
    "        cin.ignore(1000, '\\n'); // ignores chars in the stream: \n",
    "                               // up to 1000 characters or until '\\n' is found\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "        cout << \"Yay, you entered an integer!\" << endl;\n",
    "        retry = false;\n",
    "        /* do stuff with your int */\n",
    "    }\n",
    "}\n",
    "```\n",
    "- `cin.clear()` puts down the fail flag (something like fail = false)\n",
    "- `cin.ignore(int, char)` reads the stream and ignores chars up to the integer or when the character is encountered. Normally a stream on a machine consists of 256 characters\n",
    "  - another choice would be to read until a delimiter: `cin.ignore(1000, ' ');`\n",
    "  - `cin.ignore()` ignores the whole stream, `cin.ignore(4)` ignores 4 characters, etc.\n",
    "- `cin.flush` would destroy the entire stream\n",
    "\n",
    "### The eof character\n",
    "- `eof` stands for \"end of file\"\n",
    "- when `cin` encounters `eof`, it raises 2 flags: fail and eof\n",
    "- on the terminal, it is \\<Ctrl-D>  \n",
    "\n",
    "Here's another example:  \n",
    "```cpp\n",
    "int a;\n",
    "bool more = true;\n",
    "while (more)\n",
    "{\n",
    "    cin >> a;\n",
    "    if (cin.eof()){ \n",
    "        cout << \"Oh, we've reached the end!\" << endl;\n",
    "        more = false;\n",
    "    }\n",
    "    else {\n",
    "        /* parse the stream and do stuff */\n",
    "    }\n",
    "}\n",
    "```\n",
    "- remember to add in error trapping!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Enter an integer: ten-million one-hundred-and-fifty-three-thousand seven-hundred fifteen\n",
      "Bad input!!\n",
      "\n",
      "Enter an integer: 1\n",
      "Yay, you entered an integer!\n"
     ]
    }
   ],
   "source": [
    "/* ask for an integer and errortrap */\n",
    "{\n",
    "int a;\n",
    "bool retry = true;\n",
    "while (retry)\n",
    "{\n",
    "    cout << \"\\nEnter an integer: \";\n",
    "    cin >> a;\n",
    "    if (cin.fail()){\n",
    "        cout << \"Bad input!!\" << endl;\n",
    "        cin.clear(); // resets the flags to normal\n",
    "        cin.ignore(1000, '\\n'); // ignores chars in the stream: \n",
    "                               // up to 1000 characters or until '\\n' is found\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "        cout << \"Yay, you entered an integer!\" << endl;\n",
    "        retry = false;\n",
    "        /* do stuff with your int */\n",
    "    }\n",
    "}\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/06 - The getline function and custom streams <a class=\"anchor\" id=\"10/06\"></a>  \n",
    "---  \n",
    "\n",
    "### The getline function\n",
    "- reads an entire line, space included, into a string until \\<Enter> or `eof`\n",
    "- allows delimiters like spaces to be included  \n",
    "Syntax: \n",
    "- `getline(cin, str)`, you can also pass in custom streams in the first parameter, see below\n",
    "- or `cin.getline(str, 256) //read 256 characters or until an <Enter>`\n",
    "\n",
    "### User-created streams\n",
    "1. Reading from strings\n",
    "```cpp\n",
    "#include <sstream> // includes the class stringstream\n",
    "/*...*/\n",
    "int main(){\n",
    "    string str;\n",
    "    stringstream myOwnStream (str);\n",
    "    /* now we can use myOwnStream exactly the same way as cin, eg. */\n",
    "    int i;\n",
    "    myOwnStream >> i;\n",
    "    myOwnStream >> i;\n",
    "    /* ... */\n",
    "}\n",
    "```\n",
    "<span style=\"color:red\">Important!</span> The custom instance of `stringstream`, `myOwnStream`, has the exact same behaviour as `cin`\n",
    "- we can call `myOwnStream.flush()` and `myOwnStream.ignore()`, and it also has `fail` and `eof` flags  \n",
    "\n",
    "The purpose?\n",
    "- useful when you have \"line-oriented\" input: user must enter all required input on one line, and the program has to determin if the line has correct inputs or not\n",
    "- in that case, use `getline` to to grab entire line, build a stringstream out of it and read values from the stream\n",
    "\n",
    "2. Reading from files  \n",
    "```cpp\n",
    "#include <fstream> // include the class named file stream\n",
    "int main{\n",
    "    ifstream inFileStream;\n",
    "    inFileStream.open(\"inputfile.txt\");\n",
    "    // equivalent to the previous two lines, use the constructor:\n",
    "    // ifstream inFileStream(\"inputfile.txt\");\n",
    "    \n",
    "    if (!inFileStream.is_open()) // did the file open successfully?\n",
    "        cout << \"Open file failed. Check if file is in correct folder.\" << endl;\n",
    "    else\n",
    "    {\n",
    "        int a;\n",
    "        inFileStream >> a;\n",
    "        /* do stuff with input */\n",
    "        inFileStream.close();\n",
    "    }\n",
    "}\n",
    "```\n",
    "like `sstream`, behaves exactly like `cin` and reads lines until delimiters.  \n",
    "<span style=\"color:red\">Important!</span> You must always close the file to unattach the stream to the file!\n",
    "- if file isn't found, **runtime** error! \n",
    "- `open()` accepts an address to a file, eg. \"C:/Documents/input.txt\". In this case, the file should be in the same directory as the .exe file\n",
    "- if another file needs to be opened, you need another file stream\n",
    "- no limit on how long the stream can be, like in `cin`  \n",
    "\n",
    "\\* open takes in two parameters, the second of which decides the mode in which the file is read/written to. For example, `ios_base::app` appends to the end of the file, `ios_base::ate` places you at the end of the file, but you can write data anywhere in the file, `ios_base::trunc` overwrites existing files and is the default\n",
    "\n",
    "3. Writing to files  \n",
    "```cpp\n",
    "#include <fstream> // include the class named file stream, which includes input file stream\n",
    "                   // as well as output file stream\n",
    "int main{\n",
    "    ofstream outFileStream;\n",
    "    outFileStream.open(\"inputfile.txt\");\n",
    "    \n",
    "    if (!inFileStream.is_open()) // did the file open successfully?\n",
    "        cout << \"Open file failed. Check if file is in correct folder.\" << endl;\n",
    "    else\n",
    "    {\n",
    "        int a = 100;\n",
    "        outFileStream << a; // the file now contains 100\n",
    "        outFileStream << \"Hello!\"; // the file now reads \"100Hello!\"\n",
    "        outFileStream.close();\n",
    "    }\n",
    "}\n",
    "```  \n",
    "- same runtime error as `ifstream` if file not found\n",
    "- note that `outFileStream` continues writing to the same file (appending items) until file is closed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/07 - I/O Manip and Redirection <a class=\"anchor\" id=\"10/07\"></a>  \n",
    "---  \n",
    "\\* `endl` flushes the output stream!  \n",
    "  \n",
    "### I/O manipulators\n",
    "- use `#include <iomanip>` to import this library  \n",
    "See demos below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "left\n",
      "          right\n",
      "000503\n",
      "   right again!\n",
      "if the width set is shorter than the output, the output is as normal."
     ]
    }
   ],
   "source": [
    "/* text formatting */\n",
    "cout << \"left\" << endl;\n",
    "cout << setw(15) << \"right\" << endl; // this is right-justified with 8 spaces in total\n",
    "cout << setfill ('0'); // this sets the filling character to be '0' instead of whitespaces, \n",
    "                        // and persists until we call it again to reset it\n",
    "cout << setw(6) << 503 << endl; // prints 000503\n",
    "cout << setfill (' ') << setw(15) << \"right again!\" << endl;\n",
    "cout << setw (1) << \"if the width set is shorter than the output, the output is as normal.\";"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The number is 244\n",
      "In octal, it is 364\n",
      "In hexadecimal, it is f4\n",
      "Here's another hex number: 1b6d\n"
     ]
    }
   ],
   "source": [
    "/* switching radix */\n",
    "{\n",
    "int a = 244;\n",
    "cout << \"The number is \" << dec << a << endl;\n",
    "cout << \"In octal, it is \" << oct << a << endl; // change radix to octal!\n",
    "cout << \"In hexadecimal, it is \" << hex << a << endl; // change radix to hexadecimal!\n",
    "cout << \"Here's another hex number: \" << 7021 << endl; // Note that radix manipulators persist\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A formatted hex number: 0XF4\n",
      "Back to default format: f4\n"
     ]
    }
   ],
   "source": [
    "/* formatting different radix outputs */\n",
    "{\n",
    "// sets format for hex numbers\n",
    "cout << setiosflags (ios_base::hex|ios_base::showbase|ios_base::uppercase); \n",
    "cout << \"A formatted hex number: \" << hex << 244 << endl;\n",
    "cout << resetiosflags (ios_base::hex|ios_base::showbase|ios_base::uppercase); \n",
    "cout << \"Back to default format: \" << hex  << 244 << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pi rounded to two decimals is 3.1\n",
      "Pi in scientific notation: 3.14e+00\n",
      "If you set the precision too high, you might get garbage: \n",
      "3.14159250259399414062"
     ]
    }
   ],
   "source": [
    "/* setting precision for floating point numbers and scientific notation */\n",
    "{\n",
    "float pi = 3.1415926;\n",
    "cout << setprecision(2); // note that this persists too!!\n",
    "cout << \"Pi rounded to two decimals is \" << pi << endl;\n",
    "cout << scientific << \"Pi in scientific notation: \" << pi << endl;\n",
    "cout << setprecision(20); \n",
    "cout << fixed << \"If you set the precision too high, you might get garbage: \\n\" << pi;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### I/O Redirection\n",
    "cmd line commands to redirect the entire `cin` or `cout` streams into/out of a file\n",
    "- `myprog.exe > out.txt` writes output from `cout` to `out.txt`\n",
    "- `myprog.exe >& out.txt` sends `cout` and `cerr` (any error output) into the file\n",
    "- `myprog.exe < input.txt > out.txt` writes output as above and takes in input from the file `input.txt`. Must do input first, the order matters!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/07 - Pointers, Scopes and Arrays\n",
    "Topics  \n",
    "- what pointers are, purpose\n",
    "- dynamic allocation\n",
    "- scope of dynamically allocated vars\n",
    "- arrays vs pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/08 - Pointers, Scopes and Arrays <a class=\"anchor\" id=\"10/08\"></a>  \n",
    "---  \n",
    "- **segmentation fault**: if you try to dereference a null pointer\n",
    "- if you dereference an uninitialized pointer, the behaviour is undefined (depends on compiler)\n",
    "\n",
    "### Making dynamic data\n",
    "- we can use pointers to create new variables while the program is executing (i.e. at run-time). These variables are called **dynamic data**  \n",
    "\n",
    "The keyword `new` \n",
    "```cpp\n",
    "int* px = new int;\n",
    "```\n",
    "- is equivalent to `int* px = (int*)malloc(sizeof(int));`, creates run-time variables on the heap\n",
    "- think of `new` as a function that returns the address of the new variable\n",
    "- since the variable created in this way does not have a name, the pointer is our only access to it. If you then change the pointer to point to another value, this will cause a **memory leak**!!  \n",
    "- a key characteristic of dynamic variables is that the variable itself does not have a name (only accessed through its pointer)\n",
    "\n",
    "```cpp\n",
    "int* px = new int;\n",
    "*px = 5; // assign this integer a value of 5\n",
    "int a;\n",
    "px = &a; // You lost access to the int that stored 5 forever! :((\n",
    "```  \n",
    "\n",
    "The keyword `delete`  \n",
    "```cpp\n",
    "delete px;\n",
    "```\n",
    "- similar to `free(px)`\n",
    "- takes a pointer, follows it to the variable pointed to, and deletes that variable\n",
    "- the syntax might suggest the pointer itself is deleted, but the pointer still exists! \n",
    "- we should then set the pointer to null. This is good practise, since for example, if another part of the program overwrites the memory that stored the int with a float later, and we dereference the original pointer to an int, the compiler will complain loudly!\n",
    "```cpp\n",
    "px = nullptr; // or equivalently,\n",
    "px = NULL;\n",
    "```\n",
    "- if we try to access what the pointer was pointing to after deleting it, no compile error is given, and you might or might not get a runtime error (undefined behaviour)\n",
    "\n",
    "### Pointers to structs\n",
    "- if you have a struct, the pointer points to the whole thing\n",
    "- if `pstruct` is a pointer to a struct, then to access a member, do \n",
    "```cpp\n",
    "(*pstruct).member\n",
    "```\n",
    "Note that the member-access operator (.) has precedence over the dereference operator (\\*), so the brackets must be there! \n",
    "- A sweeter syntax for this is \n",
    "```cpp\n",
    "pstruct->member\n",
    "```\n",
    "- when you `delete pstruct`, the entire struct is wiped clear, but make sure you free individual member pointers as well. eg.\n",
    "```cpp\n",
    "struct student{\n",
    "    int ID;\n",
    "    char* name;\n",
    "    int* gpa;\n",
    "}\n",
    "int main(){\n",
    "    // initialize a struct pointer\n",
    "    student* yvon = new student;\n",
    "    \n",
    "    // initialize the pointers within the struct\n",
    "    yvon->name = new char[11];\n",
    "    yvon->gpa = new int;\n",
    "    \n",
    "    /* do stuff with the struct...*/\n",
    "    \n",
    "    // delete the pointers within the struct\n",
    "    delete yvon->gpa;\n",
    "    delete[] yvon->name;\n",
    "    \n",
    "    //delete the pointer to the struct itself\n",
    "    delete yvon;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "{ /* Try dereferencing a pointer after deleting its content */\n",
    "int a = 80;\n",
    "int* px = &a;\n",
    "delete px;\n",
    "int b = *px; // you'll notice that the kernel dies here. It's not a coincidence, don't do this!!!\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/13 - Pointers, Scopes and Arrays <a class=\"anchor\" id=\"10/13\"></a>  \n",
    "---  \n",
    "\n",
    "### Dynamic allocation of objects\n",
    "```cpp\n",
    "Date* day1, day2;\n",
    "day1 = new Date; // this makes a pointer to a Date object with the no-argument constructor\n",
    "day2 = new Date(1,1,2020); // this calls the constructor that takes 3 ints\n",
    "```\n",
    "\n",
    "### Scope\n",
    "- a var is visible from the point of its declaration to the end of the code block (surrounded by {}) in which it is declared, except when eclipsed\n",
    "- scope **hiding/masking/eclipsing**: when another var with the same name is declared within the scope of one var, eg.\n",
    "```cpp\n",
    "int x = 1; // a global var\n",
    "void foo ()\n",
    "{\n",
    "    int x = 10; // a local var that eclipses the global one\n",
    "    /*...*/\n",
    "}\n",
    "```  \n",
    "\n",
    "### Memory Errors\n",
    "**Memory leaks** (allocated memory that we lost access to) b/c of local pointers going out of scope eg.  \n",
    "```cpp\n",
    "void foo ()\n",
    "{\n",
    "    int* p = new int;\n",
    "    *p = 5;\n",
    "} // end of function, all local variables (including p) are cleared\n",
    "int main ()\n",
    "{\n",
    "    foo();\n",
    "    // oh no! we lost access to that 5 forever!!\n",
    "}\n",
    "```\n",
    "- to fix this, we can change return type of `foo()` to be `int*` and pass back the pointer to 5  \n",
    "\n",
    "**Dangling pointer**: problem with making a pointer to a local variable and returning it\n",
    "```cpp\n",
    "int* foo ()\n",
    "{\n",
    "    int a = 8;\n",
    "    return (&a);\n",
    "} // end of function, local variable a is cleared\n",
    "int main()\n",
    "{\n",
    "    int* p = foo(); // p stores the address of the local variable a, but a went out of scope\n",
    "    // so what is p pointing to now?\n",
    "}\n",
    "```\n",
    "- depending on compiler, might give a warning, but just don't do it\n",
    "- if memory is reallocated at the place the dangling pointer points to, dereferencing the pointer will cause seg fault  \n",
    "\n",
    "**Double free**: deleting a pointer more than once, or deleting a null pointer  \n",
    "**Invalid read/write**: attempting to read/write outside of your program's memory, such as accessing an array index that is out of bounds (this sometimes does not give a compiler error and causes your program's own variables to be overwritten)\n",
    "\n",
    "### Memory segments\n",
    "A running program has four distinct areas in memory (aka segments)\n",
    "1. code (instructions)\n",
    "2. data (global/static vars; created at compile-time)\n",
    "3. stack (automatic vars: eg. local, function arguments; allocated at compile-time)\n",
    "4. heap (dynamic vars/user-managed vars; allocated at runtime)  \n",
    "At the end of `main`, i.e. program execution, the OS cleans the entire memory and takes back all memory leaks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/14 - Pointers, Scopes and Arrays <a class=\"anchor\" id=\"10/14\"></a>  \n",
    "---  \n",
    "\n",
    "- the size of the array must be a compile-time known constant\n",
    "```cpp\n",
    "// dynamically allocating an array\n",
    "int* arr = new int[10];\n",
    "// deallocating the array\n",
    "delete[] arr;\n",
    "arr = nullptr;\n",
    "```\n",
    "Note that you must use `new[]` and `delete[]` on arrays! Clang++ gives stern error if you do `delete` on an array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/15 - Pointers and Arrays with Objects & Operator Overloading<a class=\"anchor\" id=\"10/15\"></a>  \n",
    "---  \n",
    "- when making an array of objects, can only call the no-argument constructor\n",
    "```cpp\n",
    "Date listOfDates[10]; // the no-argument constructor is called 10 times\n",
    "Date* plist = new Date[10]; // same with dynamically allocated array\n",
    "```  \n",
    "\n",
    "### Operator overloading\n",
    "Say we want to overload \"+\" to add an integer to a `Date` object like below\n",
    "```cpp\n",
    "Date startOfSchool;\n",
    "Date endOfSchool = startOfSchool + 180;\n",
    "```\n",
    "in declaration file:\n",
    "```cpp\n",
    "class Date\n",
    "{\n",
    "    /* variables, constructors, functions... */\n",
    "    public:\n",
    "    Date operator+ (int addDays);\n",
    "};\n",
    "```\n",
    "- `operator` is a reserved keyword  \n",
    "\n",
    "in implementation file:\n",
    "```cpp\n",
    "Date Date::operator+ (int addDays)\n",
    "{\n",
    "    Date newDate = this;\n",
    "    if (month == 2)\n",
    "        newDate += addDays % 28;\n",
    "    else if (...)\n",
    "    /* more implementation... */\n",
    "    \n",
    "    return newDate;\n",
    "}\n",
    "```\n",
    "- the first `Date` is the return type  \n",
    "\n",
    "in main:\n",
    "```cpp\n",
    "Date x, y;\n",
    "Date z = x.operator+ y;\n",
    "```\n",
    "but c++ has syntactic sugar, so that this is equivalent to:\n",
    "```cpp\n",
    "Date z = x + y;\n",
    "```\n",
    "\n",
    "the default operator = used on objects copies member by member\n",
    "- this is the only operator given by default for objects  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/20 - Operator Overloading & Copy Constructor <a class=\"anchor\" id=\"10/20\"></a>  \n",
    "---  \n",
    "### Copy Constructor\n",
    "- called every time an object is copied, or passed as parameter, eg.\n",
    "```cpp\n",
    "// Date Y is declared\n",
    "Date X(Y); \n",
    "// or \n",
    "Date X = Y; // this is not the assignment operator, this is the copy constructor!!\n",
    "```\n",
    "- by default, it creates a shallow copy\n",
    "- syntax:\n",
    "```cpp\n",
    "/* prototype */\n",
    "void Date(Date & source); // passing by reference and must pass by reference\n",
    "/* implementation */\n",
    "Date::Date(Date & source){\n",
    "    year = source.year;\n",
    "    month = source.month;\n",
    "    day = source.day;\n",
    "}\n",
    "```  \n",
    "- recall that passing by value invokes the copy constructor, so we can't define the copy constructor itself with pass-by-value. It'd result in the copy constructor calling itself again and again (this results in a compile-time error)  \n",
    "\n",
    "### Overloading the assignment operator (=)\n",
    "```cpp\n",
    "Date Date::operator= (Date rhs){\n",
    "    year = rhs.year;\n",
    "    month = rhs.month;\n",
    "    day = rhs.day;\n",
    "    \n",
    "    return (*this);\n",
    "}\n",
    "```\n",
    "- this is given by default for every object\n",
    "- implementation must return the object type, since assignment always returns whatever is assigned, so we can do:\n",
    "```cpp\n",
    "Z = Y = X;\n",
    "```\n",
    "\n",
    "Difference b/w copy constructor and assignment\n",
    "```cpp\n",
    "Date Y(); // no-argument constructor invoked\n",
    "Date X = Y; // this is not the assignment operator, this only invokes the copy constructor!!\n",
    "// this is syntactic sugar for Date X(Y); (to make objects behave like int a = b)\n",
    "```\n",
    "```cpp\n",
    "// Declarations...\n",
    "Date Y();\n",
    "Date X();\n",
    "\n",
    "X = Y; // THIS is the assignment operator\n",
    "```\n",
    "\n",
    "Function calls during execution of the statement `X = Y;`\n",
    "1. first, the overloaded operator= is called\n",
    "2. copy constructor to pass Y into X.operator=(Y)\n",
    "3. `return (*this)` calls the copy constructor again\n",
    "4. `rhs` is local to the operator= function. As `rhs` goes out of scope, destructor is called\n",
    "5. eventually, destructor is called again to destroy the object that's returned  \n",
    "This is 5 function calls just for one simple assignment! Terrible!\n",
    "\n",
    "Let's pass by reference and return by reference: meaning that the object passed is one and the same as `Y`, and the one returned is `X`\n",
    "- the `const` modifier prevents you from accidentally modifying the object passed by reference in the function\n",
    "- this avoids all the cost of copying and destructing objects\n",
    "```cpp\n",
    "Date & Date::operator= (const Date & rhs){\n",
    "    year = rhs.year;\n",
    "    month = rhs.month;\n",
    "    day = rhs.day;\n",
    "    \n",
    "    return (*this);\n",
    "}\n",
    "```\n",
    "- now there is only one function call: the operator= function!!! Try tracing it!\n",
    "\n",
    "Recall the operator+ function, we can improve it by making the return argument and its parameter `const`\n",
    "```cpp\n",
    "Date Date::operator+ (const Time & rhs) const{// this is a constant function, and accepts a const Date argument\n",
    "    Date sum;\n",
    "    /* calculations...*/\n",
    "    return (sum);\n",
    "}\n",
    "```\n",
    "- but we can't return by reference, since sum is a local var and will go out of scope\n",
    "- in good compilers, the lifetime of local vars may be extended so that you can return it by reference, but don't rely on it\n",
    "- we can, however make sum dynamically allocated, eg.  \n",
    "```cpp\n",
    "Date Date::operator+ (const Time & rhs) const{ \n",
    "    Date* p_sum = new Date;\n",
    "    /* calculations...*/\n",
    "    return (*sum);\n",
    "}\n",
    "```  \n",
    "but why would you want this...\n",
    "\n",
    "### About constant functions:\n",
    "- they protect against accidental changes to the object that they belong to\n",
    "- it's recommended to make as many functions const as possible\n",
    "- constant functions can be called on const and non-const objects; non-const functions can only be called by non-const objects, eg.\n",
    "```cpp\n",
    "// say we have in the declaration:\n",
    "class Date{\n",
    "    int get_month();\n",
    "    const int get_day();\n",
    "    /*...*/\n",
    "};\n",
    "// then in main:\n",
    "const Date birthday(2001,12,01);\n",
    "int m = birthday.get_month(); // this gives an error since get_month isn't const but the object birthday is\n",
    "int d = birthday.get_day(); // this is fine :)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/21 - Operator Overloading Example<a class=\"anchor\" id=\"10/21\"></a>  \n",
    "---  \n",
    "Example: make a class for complex numbers so that the following works:\n",
    "```cpp\n",
    "Complex a(5.0, 8.3);\n",
    "Complex b(a); // copy constructor\n",
    "Complex c; // real = imag = 0\n",
    "c = a + b;\n",
    "c = a * b;\n",
    "c = a - b;\n",
    "c = a / b;\n",
    "c = -a; // unary operator minus\n",
    "if (a == b){ // note the comparison operator\n",
    "    c.print(); \n",
    "    // or even\n",
    "    // std::cout << c << endl; //////////////// we'll do this next time\n",
    "}\n",
    "```\n",
    "Class declaration:\n",
    "```cpp\n",
    "class Complex{\n",
    "    private:\n",
    "    float real, imag;\n",
    "    \n",
    "    public:\n",
    "    Complex();\n",
    "    Complex(float real, float imag);\n",
    "    // Note that we don't have to write the copy constructor: Complex(const Complex & other); since the default one is good enough\n",
    "    \n",
    "    void print();\n",
    "    /* accessors and mutators... */\n",
    "    \n",
    "    Complex operator+(const Complex & rhs) const;\n",
    "    Complex operator-(const Complex & rhs) const;\n",
    "    Complex operator*(const Complex & rhs) const;\n",
    "    Complex operator/(const Complex & rhs) const;\n",
    "    Complex & operator-(); // the unary minus operator\n",
    "    Complex & operator=(const Complex & rhs); // assignment\n",
    "    bool operator==(const Complex & rhs) const; // comparison\n",
    "};\n",
    "```\n",
    "Consider the implementation of `==`:\n",
    "```cpp\n",
    "Complex & Complex::operator=(const Complex & rhs) const{\n",
    "    if (real == rhs.get_real() && imag == rhs.get_imag())\n",
    "        return (true);\n",
    "    return (false);\n",
    "}\n",
    "```\n",
    "- it's got another `==` inside! But don't worry, there's no function recursion since the one inside is the overloaded operator for floats!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/22 - Friends <a class=\"anchor\" id=\"10/22\"></a>  \n",
    "---  \n",
    "- In a class definition, we can declare an external class/function a `friend` of it, to give it access to all the private members of this class\n",
    "- This is useful if you'd like to overload the >> operator for stream operations\n",
    "- `stream >> a` translates to `stream.operator>>(a)`, so we're invoking this function on a stream object, not your custom class!\n",
    "```cpp\n",
    "/* In the class header file, declare operator>> as a friend of the class */\n",
    "class Complex {\n",
    "    /*...*/\n",
    "    friend ostream& operator>>(ostream& os, const Complex& z);\n",
    "};\n",
    "```\n",
    "```cpp\n",
    "/* In the implementation file (Complex.cpp) along with other functions: */\n",
    "ostream& operator>>(ostream& os, const Complex& z){\n",
    "    os << z.real << \" + i*\" << z.imag;\n",
    "}\n",
    "```\n",
    "- Note how we could directly access the private members of the class Complex here!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10/27 - Objects that contains pointers <a class=\"anchor\" id=\"10/27\"></a>  \n",
    "---  \n",
    "- C++ constructors, assignment operator and destructors are \"shallow\" operations, which means that they are limited to the variables directly within the object (so not anything that a member pointer points to)\n",
    "- so you have to write your own constructor (invoked after creation and before usage), destructor (invoked before object disappears), and assignment operator!\n",
    "- the `const` modifier also only gives shallow protection: limited to members of the class, not what member pointers point to"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fun extra stuff on Classes<a class = \"anchor\" id=\"extra1\"></a>\n",
    "### (Non-static) Class that forbids copying\n",
    "- Simply make the copy constructor and assignment operator private! Then you would get a compile-time error every time the copy constructor is called/you try to assign an object to another. eg.\n",
    "```cpp\n",
    "class Homework{\n",
    "    private: \n",
    "    string contents;\n",
    "    Homework (const & Homework) {}; // prohibits the creation of copies\n",
    "    Homework& operator= (const & Homework); // prohibits assignment\n",
    "    \n",
    "    public: \n",
    "    Homework (string contents);\n",
    "};\n",
    "```\n",
    "Then we can test the following:\n",
    "```cpp\n",
    "void foo_by_value(Homework hw){ /*...*/ }\n",
    "void foo_by_reference(Homework & hw) { /*...*/ }\n",
    "int main(){\n",
    "    Homework my_hw (\"ece244\");\n",
    "    Homework andrews_hw (my_hw); // Error! Not allowed to access the copy constructor\n",
    "    Homework andrews_hw = my_hw; // Error! Not allowed to access the assignment operator\n",
    "    foo_by_value(my_hw); // Error! This calls the copy constructor\n",
    "    foo_by_reference(my_hw); // This is fine\n",
    "}\n",
    "```\n",
    "- note that since passing arguments to a function calls the copy constructor, we cannot pass this object to any function by value!\n",
    "- We can also do the following:\n",
    "```cpp\n",
    "    Homework(const Homework& rhs) = delete; // this also gets rid of the copy constructor\n",
    "```\n",
    "\n",
    "### Class that can only be dynamically created\n",
    "- Say we have a gigantic database that we want to avoid creating on the stack, so that it can only be created on the heap\n",
    "- The way to do this is to make the destructor private! \n",
    "```cpp\n",
    "/* in the class definition...*/\n",
    "    private:\n",
    "    ~HumongousDatabase();\n",
    "```\n",
    "- Now the compiler would not let you do this\n",
    "```cpp\n",
    "HumongousDatabase DB_on_stack();\n",
    "```\n",
    "- Cool. But then, how do we delete a dynamic instance? Turns out you'll need a [static](#static) function, see below\n",
    "```cpp\n",
    "class HumongousDatabase{\n",
    "    private:\n",
    "    ~HumongousDatabase(); // prohibits object creation on the stack\n",
    "    public:\n",
    "    static void destroyDB(HumongousDatabase* pDB)\n",
    "    { delete pDB; }\n",
    "    /*...*/\n",
    "};\n",
    "int main()\n",
    "{\n",
    "    HumongousDatabase * pDB = new HumongousDatabase();\n",
    "    /* do stuff with DB... */\n",
    "    // Note that the following line gives an error!\n",
    "    delete pDB;\n",
    "    // The correct way is:\n",
    "    destroyDB(pDB);\n",
    "    pDB = nullptr;\n",
    "}\n",
    "```  \n",
    "\n",
    "### Static vars, functions, classes <a class = \"anchor\" id = \"static\"></a>\n",
    "(give me some time to think through this)\n",
    "//////////// to be added\n",
    "\n",
    "### Constructor initializer lists (and default parameter values)\n",
    "- This is an alternative to the traditional way of implementing constructors. It's easier!\n",
    "- The syntax: (where arg_k stands for the k-th argument name, and var_k is the variable passed into arg_k)\n",
    "> ClassName(*default_arg_values*): arg_1(var_1), arg_2(var_2), ... {/* other code in constructor */}  \n",
    "- (it's kind of like Verilog port connections)\n",
    "- Say we have a class Circle, and it's got member variables radius and centre and the default is the unit circle, then this is what we normally do in the header file:\n",
    "```cpp\n",
    "class Circle{\n",
    "    private:\n",
    "    int radius, centre_x, centre_y;\n",
    "    public:\n",
    "    Circle();\n",
    "    Circle(int r,int x,int y);\n",
    "    /*...*/\n",
    "};\n",
    "```\n",
    "then in the implementation file, \"Circle.cpp\":\n",
    "```cpp\n",
    "Circle::Circle(){ // the zero-argument constructor, set default values\n",
    "    radius = 1;\n",
    "    centre_x = 0;\n",
    "    centre_y = 0;\n",
    "    cout << \"Circle created!\" << endl; // display a success message\n",
    "}\n",
    "Circle::Circle(int r, int x, int y){\n",
    "    radius = r;\n",
    "    centre_x = x;\n",
    "    centre_y = y;\n",
    "    cout << \"Circle created!\" << endl; // display a success message\n",
    "}\n",
    "```\n",
    "But with initializer lists, we can do all this in the definition file:\n",
    "```cpp\n",
    "class Circle{\n",
    "    private:\n",
    "    int radius, centre_x, centre_y;\n",
    "    public:\n",
    "    Circle(int r = 1, int x = 0, int y = 0)\n",
    "        :radius(r), centre_x(x), centre_y(y)\n",
    "    {\n",
    "        cout << \"Circle created!\" << endl; // display a success message\n",
    "    }\n",
    "}\n",
    "```\n",
    "- Note that we can omit all of the arguments in the default argument list, so that `Circle unit_circle()` would still work!  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fun extra stuff on Operator Overloading <a class = \"anchor\" id=\"extra2\"></a>\n",
    "(/////to be added...)\n",
    "### Resource\n",
    "Hear Stroustrup himself explain operator overloading! Super entertaining and insightful.  \n",
    "https://isocpp.org/wiki/faq/operator-overloading#creating-new-opers  \n",
    "Golden rules of operator overloading:\n",
    "- do it to make the programmer/user's life easier, not harder\n",
    "- you can only overload existing operators, and cannot change their precedence/associativity/arity  \n",
    "\n",
    "### Prefix/Postfix Increment/Decrement\n",
    "### Conversion operators\n",
    "### Smart pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11/03 - Linked Lists <a class = \"anchor\" id=\"11/03\"></a>\n",
    "---\n",
    "### Basic data type\n",
    "```cpp\n",
    "class LinkedList{\n",
    "    Node* head;\n",
    "};\n",
    "class Node{\n",
    "    string key; // or char, int, whatever type\n",
    "    Node* next;\n",
    "};\n",
    "```\n",
    "\n",
    "### Quick notes:\n",
    "- order of commands matter! eg. to insert p1 after p0, where p1 and p0 are both pointers to nodes, do:\n",
    "```cpp\n",
    "p1->next = p0->next;\n",
    "p0->next = p1;\n",
    "```\n",
    "This can't be reversed!\n",
    "- common corner cases: empty list, operation on head node/tail node\n",
    "\n",
    "### LinkedList as a class\n",
    "We will implement the following API:\n",
    "```cpp\n",
    "class Node {\n",
    "    private:\n",
    "    string key;\n",
    "    Node* next;\n",
    "    public:\n",
    "    Node();\n",
    "    Node(int k);\n",
    "    Node(int k, Node* n);\n",
    "    Node(const Node& other);\n",
    "    ~Node();\n",
    "    int getKey() const;\n",
    "    Node* getNext() const;\n",
    "    void setKey(int k);\n",
    "    void setNext(Node* n);\n",
    "    void print() const;\n",
    "};\n",
    "class LinkedList{\n",
    "    private:\n",
    "    Node* head;\n",
    "    public:\n",
    "    LinkedList();\n",
    "    LinkedList(const LinkedList & other);\n",
    "    ~LinkedList();\n",
    "    bool keyExists(const string key);\n",
    "    bool insertFront(const string key);\n",
    "    bool insertBack(const string key);\n",
    "    bool insertAfter(const string key);\n",
    "    bool deleteFront();\n",
    "    bool deleteBack();\n",
    "    bool deleteAfter(const string key);\n",
    "    void print()const;\n",
    "}\n",
    "```\n",
    "- Note that the functions that return bool will return a negative value if the action can't be performed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11/05 - Recursion <a class = \"anchor\" id = \"11/05\"></a>\n",
    "---\n",
    "- trace stack frames\n",
    "- think through the recursive basis and the recursive step first\n",
    "- Note: if a recursive function takes a pointer, some care needs to be taken to pass it by reference\n",
    "eg. the in-class example of printing a linkedlist in reverse order, and the one on the quiz /////"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11/17 - Binary tree <a class = \"anchor\" id = \"11/17\"></a>\n",
    "---\n",
    "    \n",
    "### Terms\n",
    "- Recursive definition:  \n",
    "    A **binary tree** is either empty (base case), or consists of two disjoint binary trees.\n",
    "- A binary tree **node** consists of a key and a value.\n",
    "- Relationship between nodes: descendant, ancestor, child (immediate descendant), parent (immediate ancestor), root\n",
    "- 2 types of nodes: leaf (does not have any descendants) or interior (non-leaf)\n",
    "- left subtree of a node is the binary tree formed by the node's left child and all of its descendants\n",
    "- a **path** between two nodes n1 and n2 is a set of connected nodes with start and endpoints n1 and n2\n",
    "\n",
    "### Properties\n",
    "Proving properties of binary trees: prove by contradiction  \n",
    "1. Each node has a unique parent, except for the root (has no parent)\n",
    "2. The path between the root and each node in the tree is unique\n",
    "\n",
    "### Traversals\n",
    "- in-order: left-node-right\n",
    "- pre-order: node-left-right\n",
    "- post-order: left-right-node\n",
    "\n",
    "(The in/pre/post-order refer to the position of the current node. The right subtree is always traversed after the left subtree in these three traversals.)\n",
    "\n",
    "### Binary search tree\n",
    "A binary tree with the following properties:\n",
    "- each node has a unique key\n",
    "- the key of each node is greater than all keys in its left subtree, and less than all keys in its right subtree  \n",
    "         left < node < right\n",
    "- because of ^, keys will be sorted if the tree is traversed in-order\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11/18 - Binary tree <a class = \"anchor\" id = \"11/18\"></a>\n",
    "---\n",
    "\n",
    "insertion of one node: O(logn)  \n",
    "deletion of one node: O(logn) replace node with max of left subtree or min of right subtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## 11/19 - Binary tree with OOP implementation <a class = \"anchor\" id = \"11/19\"></a>\n",
    "---\n",
    "destructor\n",
    "- base case is empty tree, then use a recursive helper function to delete LRN (note that the current node must be deleted last!)  \n",
    "\n",
    "insert into tree\n",
    "- use a recursive helper function that takes in two `Node*` arguments (the one to insert and the one we're currently at)  \n",
    "\n",
    "copy constructor\n",
    "- similar to print function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11/24 - Inheritance <a class = \"anchor\" id = \"11/24\"></a>\n",
    "---\n",
    "- an important mantra of OOP design, **OCP (open–closed principle)** states \"software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification\"\n",
    "- **inheritance** allows us to build upon existing code and use classes without having to understand their inner workings  \n",
    "- there are 3 types of inheritance: public, private, protected  \n",
    "\n",
    "Example:\n",
    "```cpp\n",
    "class Professor:public Human{};\n",
    "```\n",
    "- **base/parent/super class**: the class that is inherited from (`Human`)\n",
    "- **derived/child/sub class**: the class that inherits from the other (`Professor` is the derived class)\n",
    "- the class `Professor` inherits from the class `Human`, meaning that it will inherit all of `Human`'s member functions and variables (including private ones)\n",
    "- but b/c this is public inheritance, private members cannot be accessed by objects of the base class!\n",
    "\n",
    "- what's not inherited:\n",
    "    - constructors and destructors of the base class \n",
    "    - overloaded assignment operator\n",
    "    - friends of base class (you need to make your own friends :)\n",
    "- remember that you need to include \"Human.h\" in \"Professor.cpp\", and Human.cpp must be compiled before Professor.cpp to be linked together. Professor.cpp can be compiled into an object file without Human.cpp being compiled.\n",
    "- restriction on inheritance: cycles are not allowed (eg. two classes cannot inherit each other, and a cycle of classes inheriting one another is not allowed)\n",
    "\n",
    "### Method overriding\n",
    "- if the derived class has a method/variable with the same name (only name! not signature!!) as a variable/method(s) in the base class, then it **eclipses/masks/overrides** the one in the base class (eg. when you call the function on an object of `Professor`, it's the function in `Professor` that is invoked)  \n",
    "- note that one function in the derived class is enough to override all overloaded functions with the same name in the base class!!!  \n",
    "eg.\n",
    "```cpp\n",
    "class Human{\n",
    "    string name;\n",
    "    public:\n",
    "    string getName() const; \n",
    "    void setName();\n",
    "    void printInfo();\n",
    "    void printInfo(string a);\n",
    "}\n",
    "class Professor:public Human{\n",
    "    string course; // new variable\n",
    "    public:\n",
    "    string getCourse() const; // new functions...\n",
    "    void setCourse();\n",
    "    void teach();\n",
    "    void printInfo(); // override function\n",
    "}\n",
    "int main(){\n",
    "    Professor Tarek;\n",
    "    Tarek.printInfo(); // this invokes Professor::printInfo()\n",
    "    Tarek.printInfor(\"address\"); // compile error!\n",
    "    Tarek.Human::printInfo(); // this invokes Human::printInfo()\n",
    "    Tarek.Human::printInfo(\"address\"); // this invokes Human::printInfo(string)\n",
    "    return 0;\n",
    "}\n",
    "```\n",
    "- if a base class function isn't shadowed, we can access it (if the inheritance is public and the method is public) with the scope operator `::`\n",
    "eg2. we can also call the inherited function in the implementation of the base class:\n",
    "- if the two classes have a variable or function with the same signature (same name, return type and argument list), then the variable/function in the child class **eclipses/masks/overrides** the one in the parent class (eg. when you call the function on an object of `Professor`, it's the function in `Professor` that is invoked)  \n",
    "eg.\n",
    "```cpp\n",
    "Professor::printInfo(){\n",
    "    Human::printInfo();\n",
    "    std::cout << \"...and he/she is a professor!\" << std::endl;\n",
    "}\n",
    "```\n",
    "\n",
    "### Initialization and destruction\n",
    "Ex1. \n",
    "```cpp\n",
    "Professor Tarek;\n",
    "```\n",
    "- both default constructors of `Professor` and `Human` are called! Additionally, constructor for base class is called before the derived class (bottom up)  \n",
    "\n",
    "Ex2. what if we want to call a custom constructor of `Human` in `Professor`?\n",
    "```cpp\n",
    "// let's say Human has the constructor Human(string name), to call it in the derived class, do:\n",
    "Professor::Professor(string name, string course):Human(name){\n",
    "    this->name = name;\n",
    "    this->course = course;\n",
    "}\n",
    "```\n",
    "- the destructors are called in reverse order: derived class' destructor is first called, then the base class (top down)\n",
    "\n",
    "### Type inheritance\n",
    "- objects of the derived class type is also of the base class type (eg. a `Professor` object is also of type `Human`), but the reverse does not apply (eg. a `Human` object isn't of type `Professor`!)  \n",
    "- implicitly casting a derived object to its base type is called **slicing**, since we slice off the new parts, and is usually not desirable \n",
    "\n",
    "Say we have:\n",
    "```cpp\n",
    "Human human;\n",
    "Professor prof;\n",
    "\n",
    "human = prof; // equivalent to human.operator=(Human&)\n",
    "              // prof gets implicitly cast to type Human, this works!\n",
    "prof = human; // equivalent to the default assignment function, prof.operator=(Professor&)\n",
    "// If we don't have a custom assignment function Professor::operator=(Human&), then this is a compile error!\n",
    "```\n",
    "- Note that it will be problematic to write the `Professor::operator=(Human&)` since we're assigning a smaller object to a bigger, derived one\n",
    "- the rule is that the larger object can always shrink, but the small one cannot grow on its own"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11/25 - Inheritance <a class = \"anchor\" id = \"11/25\"></a>\n",
    "---\n",
    "\n",
    "### Pointers\n",
    "- pointers to a base object can point to object of its derived types, this is called **polymorphism** - the same variable being able to store objects of different types\n",
    "- pointers to a derived object cannot point to object of type base (we do not want it to access new functions of the derived object and find out that they're envoked on a base object)  \n",
    "- references behave just like pointers\n",
    "Ex. Say we have the following class definitions\n",
    "```cpp\n",
    "class Human{\n",
    "    string name;\n",
    "    public:\n",
    "    string getName() const; \n",
    "    void setName();\n",
    "    void printInfo();\n",
    "}\n",
    "class Professor:public Human{\n",
    "    string course; // new variable\n",
    "    public:\n",
    "    string getCourse() const; // new functions...\n",
    "    void setCourse();\n",
    "    void teach();\n",
    "    void printInfo(); // override function\n",
    "}\n",
    "```\n",
    "Then,\n",
    "```cpp\n",
    "Professor* p = new Professor;\n",
    "Human* h = new Human;\n",
    "h = p; // this is ok\n",
    "p = h; // this is not ok!\n",
    "\n",
    "h->teach(); // compile-time error\n",
    "h->printInfo(); // Human::printInfo() is invoked \n",
    "\n",
    "```\n",
    "- if a `Human` pointer is pointing to a `Professor` object, it can only invoke the functions defined in `Human`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11/26 - Inheritance <a class = \"anchor\" id = \"11/26\"></a>\n",
    "---\n",
    "\n",
    "- **binding**: the process of finding the function to invoke for an object (compiler lingo)\n",
    "- **static/early binding** is based entirely on the type of the pointer (Human pointer invokes Human::print and Professor pointer invokes Professor::print). This happens at runtime\n",
    "- we can't figure out at compile time what kind of object a pointer points to!\n",
    "- use **dynamic/late binding**! tell the compiler to generate code that inspects the object pointed to at runtime, and behave accordingly  \n",
    "### Virtual Functions  \n",
    "Ex.\n",
    "```cpp\n",
    "class Human{\n",
    "    /*...*/\n",
    "    virtual void printInfo();\n",
    "}\n",
    "class Professor{\n",
    "    /*...*/\n",
    "    virtual void printInfo();\n",
    "}\n",
    "```\n",
    "- making one function **virtual** makes every other function with the same signature in all its derived classes virtual as well (so we don't have to specify virtual in Professor again). Note that this goes up the chain of inheritance (to its derived classes) and not down\n",
    "- since `printInfo()` is virtual, at runtime then, the compiler adds code that looks like this pseudocode:\n",
    "```\n",
    "obj_type = get_type(object);\n",
    "if (obj_type==\"Human\") Human::printInfo();\n",
    "else if (obj_type==\"Professor\") Professor::printInfo();\n",
    "```\n",
    "- in other words, it halts the binding until runtime, when the object type is known, so that it's invoked on the exact type of the object at runtime\n",
    "Now if we do:\n",
    "```cpp\n",
    "Professor* p = new Professor;\n",
    "Human* h = new Human;\n",
    "```\n",
    "- <span style=\"color:red\">Important!</span> We must make the destructor virtual, so that we won't have memory leaks! If we want others to inherit from a class, then we must make the destructor virtual!\n",
    "    - note that if you make the Human destructor virtual, then all its derived class' destructors become virtual as well (despite having different method signatures). This is a special property of destructors  \n",
    "    - calling a virtual destructor of a child class will also automatically invoke the destructor of its parent class, just as desired (top down)\n",
    "    \n",
    "```cpp\n",
    "class Human{\n",
    "    /*...*/\n",
    "    public:\n",
    "    virtual ~Name(); \n",
    "}\n",
    "```\n",
    "- constructors can not be virtual\n",
    "- why not make functions virtual by default? this slows down the program a lot because everything has to be determined at runtime. The cpp design philosophy is that you should never pay for a feature that you don't use, thus maximizing the efficiency of a program\n",
    "- virtual functions are implemented with a Virtual Function Table (VFT) which consists of pointers to functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12/01- Inheritance <a class = \"anchor\" id = \"12/01\"></a>\n",
    "---\n",
    "### Checking the type of an object\n",
    "1. Using dynamic cast to check if it's a particular type\n",
    "- this uses RTTI (RunTime Type Identification)\n",
    "```cpp\n",
    "t* dynamic_cast<t>(ptr); // returns a (cast)pointer to object if *ptr is of type t, otherwise returns nullptr\n",
    "/* We can use this to check the type of an object at runtime */\n",
    "Human * mysteryptr;\n",
    "/*...*/\n",
    "if (Human *testhuman = dynamic_cast<Human*>(mysteryptr))\n",
    "    std::cout << \"This is a pointer to a Human!\" << std::endl;\n",
    "else if (Professor *testprof = dynamic_cast<Professor*>(mysteryptr))\n",
    "{\n",
    "    std::cout << \"This is a pointer to a Professor!\" << std::endl;\n",
    "    // Now we can call functions unique to Professor w/ the new pointer\n",
    "    testprof.teach();\n",
    "}\n",
    "```\n",
    "- dynamic cast happens at runtime\n",
    "- it's a function from the STL\n",
    "- virtual functions are for functions that are common for base class and derived classes, and dynamic casting deals with functions unique to the derived classes\n",
    "\n",
    "2. Using typeid to print the name of a class\n",
    "```cpp\n",
    "#include <typeinfo>\n",
    "string typeid(variable).name() // returns a string with the internal compiler name for the type of the variable\n",
    "// eg. say we have a pointer p,\n",
    "string class_name = typeid(*p).name();\n",
    "cout<< ”p is pointing to a \" << class_name << \" object\" << endl;\n",
    "```\n",
    "- `typeid` is a kind of object that stores information about the type of another object  \n",
    "\n",
    "\n",
    "* a **polymorphic array** can point to different objects as it stores pointers of a class that implements inheritance\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Extra Inheritance stuff<a class = \"anchor\" id = \"extra3\"></a>\n",
    "### Virtual Inheritance\n",
    "- helps solve the Diamond problem (a base class is inherited by multiple classes, then another class inherit from all of these derived classes)\n",
    "- the keyword virtual is used in another sense here\n",
    "```cpp\n",
    "class Human{};\n",
    "class Professor:public Human{};\n",
    "class Therapist:public Human{};\n",
    "class Tarek:public Professor, public Therapist{};\n",
    "```\n",
    "- this creates problems for poor Tarek, as he inherits 2 copies of the Human class, from Professor and Therapist\n",
    "- eg. if we instantiate a Tarek, then the Human constructor will be called twice!!\n",
    "- solution: use virtual inheritance!\n",
    "```cpp\n",
    "class Human{};\n",
    "class Professor:virtual public Human{};\n",
    "class Therapist:virtual public Human{};\n",
    "class Tarek:public Professor, public Therapist{};\n",
    "```\n",
    "- now members of Human will only be inhertied once by Tarek :)  \n",
    "\n",
    "### Virtual copy constructors?\n",
    "- as mentioned before, you cannot make constructors virtual, you can however define your own virtual copy function to make deep copies of derived classes  \n",
    "\n",
    "\n",
    "### Abstract classes\n",
    "- an abstract base class (ABC) has at least one pure virtual function and cannot be instantiated. Its derived classes must implement all of its pure virtual function, or be abstract classes themselves  \n",
    "- we can always create a pointer to an abstract class, though\n",
    "- abstract functions/pure virtual functions syntax:\n",
    "```cpp\n",
    "class AbstractBaseClass{\n",
    "    public:\n",
    "    virtual void pure_virtual_function() = 0;\n",
    "}\n",
    "```\n",
    "- constructors cannot be abstract, destructors can be abstract but you still have to implement it.....??? (there's no point of doing this)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12/02- Inheritance <a class = \"anchor\" id = \"12/02\"></a>\n",
    "---\n",
    "### Polymorphism\n",
    "- say we'd like to create an array of different shapes, Rectangle, Circle, Triangle... each defined in a different class. Having them all inherit from a base class Shape and creating an array of Shape pointers is really useful!\n",
    "- note that we cannot have an array of different objects! eg. making an array of Shapes and assigning them to Rectangles, Circles and Triangles\n",
    "```cpp\n",
    "class Shape{};\n",
    "class Rectangle:public Shape{};\n",
    "class Circle:public Shape{};\n",
    "class Triangle:public Shape{};\n",
    "```  \n",
    "\n",
    "### The protected qualifier  \n",
    "- `protected` is a member qualifier just like `public` and `private` and provides access somewhere in between\n",
    "- making a function/variable protected makes it accessible to derived classes but not any other classes\n",
    "\n",
    "### Public, private and protected inheritance\n",
    "- these qualifiers refer to what other classes can access from the derived class\n",
    "- the default visibility mode of inheritance is private, just like member variables\n",
    "```cpp\n",
    "class Professor:Human{}; // would be private inheritance\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12/02- Complexity Analysis\n",
    "---\n",
    "- in this course, complexity refers to time complexity (how long it takes a program to run with respect to some parameters)\n",
    "- step: a set of instructions that takes a constant amount of time (independent of input size and data) on any machine\n",
    "- we measure time in steps: Time = f(n,data) where n is the input size and data is the actual input itself\n",
    "- we get rid of data in the function by splitting the function into three: \n",
    "1. Time_best = f_best(n)\n",
    "2. Time_avg = f_avg(n)\n",
    "3. Time_worst = f_worst(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12/03- Complexity Analysis <a class = \"anchor\" id = \"12/03\"></a>\n",
    "---\n",
    "- Big-O notation: a function T(n) is of order O(f(n)) if for sufficiently large n, f(n) bounds T(n) by a constant factor (c\\*f(n)>T((n))\n",
    "- eg. the functions 3\\*n^3, 300000\\*n^3, and n^3+2\\*n^2+log(n) are all of order n^3, or O(n^3)\n",
    "![Graphical comparison of asymptotic behaviours](https://cdn-media-1.freecodecamp.org/images/1*HwLR-DKk0lYNEMpkH475kg.png)\n",
    "```cpp\n",
    "count = 0;\n",
    "for (int i = 0; i < n; i++)\n",
    "{\n",
    "    for (int j = 0; j < n; j++)\n",
    "    {\n",
    "        for (k = 0; k < n/2; k++)\n",
    "             count ++; // this is one step, or O(1)\n",
    "    }\n",
    "}\n",
    "```\n",
    "- The time complexity of the code above is O(n^3) (three nested for loops)\n",
    "```cpp\n",
    "count = 1;\n",
    "for (int i = 1; i < n; i++)\n",
    "{\n",
    "    count *= n; // O(1)\n",
    "}\n",
    "for (int j = 1; j < n; j++)\n",
    "{\n",
    "    count /= j; // O(1)\n",
    "}\n",
    "```\n",
    "- The code above runs in O(n) (for loops are not nested)\n",
    "```cpp\n",
    "for (int i = 0; i < n; i++)\n",
    "{\n",
    "    for (int j = 0; j < i; j++)\n",
    "    {\n",
    "        // something O(1)\n",
    "    }\n",
    "}\n",
    "```\n",
    "- The code above runs in O(n^2). T(n) = 0 + 1 + 2 + ... + n-1 = (n-1)n/2 ~ n^2\n",
    "```cpp\n",
    "int i = n;\n",
    "while (i >= 1){\n",
    "    i/5;\n",
    "}\n",
    "```\n",
    "- The code above runs in O(logn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12/08- Complexity Analysis <a class = \"anchor\" id = \"12/08\"></a>\n",
    "---\n",
    "### Recurrence equations\n",
    "- used to express the time complexity of a recursive function in a recursive way\n",
    "- solve by expansion and inspection\n",
    "\n",
    "Q: What’s the complexity of the recursive function that expands faster than it shrinks, for example;\n",
    "T(n) = c + 3T(n/2)?\n",
    "\n",
    "A: From what we've seen in examples, partitioning the problem into smaller parts (T(n/2)) produces a logarithm, whereas multiplying T(n) by 3 would give you exponential growth. Intuitively, these two cancel out so in the end we have O(n), linear time. In this case, we're expanding by a factor of 3 while taking a log of base 2, so we can guess the result to be \\\\(3^{log_2{n}}\\\\).\n",
    "\n",
    "Let's show this formally. For the general case T(n) = c + a\\*T(n/b), we have the expansion:\n",
    "\\\\(T(n) = c + aT(n/b)\\\\ \\quad= c + a(c + aT(\\frac{n}{b^2})) = c + ac + a^2T(\\frac{n}{b^2})\\\\ \\quad= c +ac + a^2(c + aT(\\frac{n}{b^3})) = c+ac+a^2c+a^3T(\\frac{n}{b^3})\\\\...\\\\)\n",
    "Thus we can derive the following expression with a geometric series for the k-th iteration:\n",
    "$$T(n) = c(1+a+a^2+...+a^{k-1})+k^nT(\\frac{n}{k^n})\\\\ \\qquad = c\\sum_{i=0}^{k-1}a^i +k^nT(\\frac{n}{k^n})$$\n",
    "We want \\\\(T(\\frac{n}{k^n})\\\\) to be \\\\(T(1)\\\\), so let's sub in \\\\(k=\\left\\lceil log_{b}{n} \\right \\rceil\\\\). With the geometric series formula, this is simply:\n",
    "$$T(n) = c\\frac{a^{log_{b}{n}}-1}{a-1}+a^kT(1)$$\n",
    "The second term is just a constant wrt n so we can discard it. Let's clean the first term up.\n",
    "$$c\\frac{a^{log_{b}{n}}-1}{a-1} = \\frac{c}{a-1}a^{log_{b}{n}}-constant$$\n",
    "With some change of base logarithm magic*, you can show that \\\\(a^{log_{b}{n}}=n^{\\frac{loga}{logb}}\\\\). So long story short, the complexity of any recurrence relation of the form \\\\(T(n)=c+aT(n/b)\\\\) is $$O(n^{\\frac{log\\,a}{log\\,b}})$$. Since log is strictly increasing, we have \\\\(log\\,a>log\\,b\\\\) only when \\\\(a>b\\\\). And so when a = 3, b = 2, we have \\\\(O(n^{\\frac{log\\,3}{log\\,2}})\\\\) which grows faster than O(n). \n",
    "\n",
    "\n",
    "\\*\\\\(a^{log_{b}{n}}=e^{log\\,a\\frac{log\\,n}{log\\,b}} = (e^{log\\,n})^{\\frac{log\\,a}{log\\,b}}\\\\)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graphs <a class = \"anchor\" id = \"graph\"></a>\n",
    "---\n",
    "////////"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Standard Template Library <a class = \"anchor\" id = \"extra4\"></a>\n",
    "---\n",
    "(some material taught in ECE297)\n",
    "\n",
    "### Templates\n",
    "- keyword `template` is a typesafe way to create classes/functions that work for different types of data (like generics in Java)  \n",
    "- syntax:  \n",
    "> template <*parameter list*>       \n",
    "> *function/class declaration*  \n",
    "- example:\n",
    "```cpp\n",
    "//template function\n",
    "template <typename T1, typename T2=T1> // this is called the template prefix\n",
    "bool tem_func(const T1& param1, const T2& param2);\n",
    "//template class\n",
    "template <typename T3=int> //note the default parameter\n",
    "class Template\n",
    "{\n",
    "    T3 obj;\n",
    "    public:\n",
    "    T3 getObj(){return obj;}\n",
    "};\n",
    "```\n",
    "- we can call the template function like below:\n",
    "```cpp\n",
    "tem_func(x,y); //implicit\n",
    "tem_func<double,int>(x,y) //explicit\n",
    "```\n",
    "\n",
    "- note that there's no implicit casting while using templates, since that defeats the purpose of keeping strong typing\n",
    "    - eg. if we have a template swap function `swap(T & x, T & y);` \n",
    "(sorry, missing image here, probably an example from lecture slides)",
    "- creating a class for a specific type out of a template is called **specialization**. eg.  \n",
    "```cpp\n",
    "Template <int> IntTemplate; // this creates the class IntTemplate with an int obj\n",
    "```\n",
    "- can use `static_assert` to check the type being instantiated to at compile time. eg.  \n",
    "```cpp\n",
    "static_assert (sizeof(T) != sizeof (int), \"Can't be instantiated with int!\");\n",
    "```\n",
    "- STL provides template containers, algorithms, iterators  \n",
    "\n",
    "### Containers\n",
    "2 types: sequential containers and associative containers (also Container Adaptors)  \n",
    "1. Sequential: fast insert slow find  \n",
    "\n",
    "|||\n",
    "|--|--|\n",
    "|`std::vector`|dynamic array, contiguous mem: O(1) insert at end, O(1) index access|\n",
    "|`std::deque`|double-ended queue|\n",
    "|`std::list`|doubly-linked list, non-contiguous mem|\n",
    "|`std::foward_list`|singly-linked list|   \n",
    "\n",
    "\n",
    "2. Associative: slow insert fast find  \n",
    "\n",
    "|||\n",
    "|---|---|\n",
    "|`std::set`|BST, O(logn) insert find erase|\n",
    "|`std::unordered_set`|hash set, O(1) insert|\n",
    "|`std::map`|BST, O(logn) insert find erase|\n",
    "|`std::unordered_map`|hash table|\n",
    "|`std::multiset`|like a set, but support non-unique keys|\n",
    "|`std::unordered_multiset`|support repeated keys|\n",
    "|`std::multimap`|support repeated keys|\n",
    "|`std::unordered_multimap`|support repeated keys|\n",
    "\n",
    "3. Container Adapters  \n",
    "\n",
    "|||\n",
    "|--|--|\n",
    "|`std::stack`||\n",
    "|`std::queue`||\n",
    "|`std::proirity_queue`||\n",
    "\n",
    "std::vector - A Dynamic Array\n",
    "* `operator[]` - used to access/modify elements like an array\n",
    "* `push_back(elt)` - insert at end\n",
    "* `size()`\n",
    "* constructor: `vector(size, initial_value)`\n",
    "    ```cpp\n",
    "    std::vector<int> months(12); // 12 uninitialized values\n",
    "    std::vector<int> zeroes(100,0); // 100 elements initialized to 0\n",
    "    ```\n",
    "* `operator=` - deep copy\n",
    "* destructor - it will clean up after itself\n",
    "* `erase(iterator pos)` or `erase(iterator start, iterator end)` - removes element at *pos* or the range from start to end, and returns an iterator to the next valid element, O(n)\n",
    "\n",
    "std::list - A Doubly Linked List\n",
    "- no random access (operator \\[\\])\n",
    "- `it++` and `it--` allowed but `it+5` is not allowed\n",
    "\n",
    "std::map - Binary Search Tree \n",
    "* `insert(std::pair key_value)` - 3 ways to insert\n",
    "```cpp\n",
    "std::map<std::string, int> uni_population;\n",
    "// Option 1\n",
    "std::pair<std::string, int> uoft(\"University of Toronto\", 61690);\n",
    "uni_population.insert(uoft);\n",
    "// Option 2\n",
    "auto waterloo = std::make_pair(\"University of Waterloo\", 41000);\n",
    "uni_population.insert(waterloo);\n",
    "// Option 3\n",
    "uni_population.insert(std::make_pair(\"York University\", 53000));\n",
    "```\n",
    "* `find(key)` - returns an iterator to the value associated with key. If not found, return `end()`. eg.\n",
    "```cpp\n",
    "auto it = uni_population.find(\"University of Waterloo\");\n",
    "std::cout << it->first << \" has \" << it->second << \" people.\" << std::endl;\n",
    "```\n",
    "\n",
    "std::multimap - Binary Search Tree with repeated keys\n",
    "- `find(key)` would return the first value that matches the key\n",
    "\n",
    "\n",
    "### Iterators\n",
    "- iterators can be input/output, forward/bidirectional/random access\n",
    "- each container class has its own iterator: eg. `std::vector<int>::iterator` and `std::list<float>::iterator` are different types\n",
    "- iterators behave a lot like pointers\n",
    "- for the vector class, we can use the functions `vector.begin()` and `vector.end()` to return iterators to the beginning and the end of the vector\n",
    "- To iterate through a vector with an iterator:\n",
    "```cpp\n",
    "for (std::vector<int>::iterator it = vec.begin(); it < vec.end(); it++;){}; \n",
    "```\n",
    "- Iterate through a vector with a for-each loop\n",
    "```cpp\n",
    "for (auto item : vec){}\n",
    "```\n",
    "- vector iterators are random-access (can be accessed by index), so we can do pointer arithmetic on them\n",
    "\n",
    "### Algorithms\n",
    "common ones:\n",
    "- `std::find`\n",
    "- `std::find_if`\n",
    "- `std::reverse`\n",
    "- `std::remove_if`\n",
    "- `std::transform`\n",
    "////////"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/*** This is the end of the notebook. Start your code here and play around! ***/"
   ]
  }
 ],
 "metadata": {
  "ipub": {
   "globals": {
    "font-family": "Georgia"
   },
   "toc": {
    "depth": 2
   }
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}