31251 - Summary

1. Intro to C++

1.1 Lecture

Introduction to C++

Output and Input I/O

Output (std::cout): Stands for "character output" and uses the insertion operator (<<) to flow data from the program to the console.
Input (std::cin): Stands for "character input" and uses the extraction operator (>>) to flow data from the console into a variable.
Type Sensitivity: The behavior of std::cin is dependent on the data type of the variable receiving the input , such as int , float , or std::string.

Different between std::cin and std::getline (std::cin, userInput)

std::cin is used for reading a single word (up to the first whitespace) into a variable.
std::getline reads an entire line of text, including spaces, into a variable.

std::string userInput;
std::cin >> userInput; // Reads a single word
std::getline(std::cin, userInput); // Reads the entire line

Ways to define int

int x; - Declares an integer variable named x without initialization.
int x = 5; - Declares and initializes x with the value 5.
int x(5); - Declares and initializes x with the value 5 using direct initialization.
int x{5}; - Declares and initializes x with the value 5 using uniform initialization (C++11).

int myNumber{3.5} //this will give an error
int myNumber(3.5) //no error will change to 3
int myNumber{} //value is 0
int myNumber() //value is random

Function

void myFunction() {
    // Function body
}

int main() {
    myFunction();
    return 0;
}

Classes

class Car {
    public:
        std::string brand;
        int model;
        void start() {
            std::cout << "Car started!" << std::endl;
        }
    private:
        int speed;
};

Memory Management: Variables, References, and Pointers

Understanding how C++ handles data in RAM is fundamental to Data Structures and Algorithms.

Variables

Variables act like a box stored in memory.
Each variable box has a unique hexadecimal address.
Declaration: A free memory box is selected and assigned a name.
Initialization: Assigning a name and putting a specific value into the box.

References

A reference acts as an alias or "nickname" for an existing variable.
It is declared using the & symbol, such as char &ref = test;.
Modifying a reference directly changes the value of the original variable because they share the same memory address.

Pointers

A pointer is a variable that stores the memory address of another variable.
Address Operator (&): Used to retrieve the memory address of a variable.

Pointer Declaration (*): Tells the compiler the variable is a pointer, such as char *ptr;. This Declaration also apply to the function parameters

//variable declaration
char test = 'A';
char *ptr = &test;

//function with pointer parameter
void myFunction(char *ptr) {
    // Function body
    *ptr = 'B'; // *ptr, dereferencing the pointer to change the value
}
myFunction(&test); //pass the address of test to the function

Dereferencing (*): Using the * symbol to access or change the value stored at the memory address the pointer is pointing to.

Passing Variables to Functions

There are three distinct methods for passing arguments to functions in C++:

Method	Description	Effect on Original Variable
Pass by Value	A copy of the value is created and passed to the function.	None; changes within the function do not affect the original.
Pass by Reference	The function receives a reference to the original variable.	Direct; changes to the parameter affect the original value.
Pass by Pointer	The function receives the memory address (pointer) of the variable.	Direct; changes via dereferencing affect the original value.
Pass by Const Reference	Receives a reference (alias) but treats it as read-only.	None; Efficient for large data (no copy).

Pass by Value

The function creates a completely new "box" in memory and copies the value into it. Changes to the parameter x do not affect the original num.

void doubleValue(int x) {
    x = x * 2; // Changes ONLY the copy
}

int main() {
    int num = 5;
    doubleValue(num);
    // num is still 5
}

Pass by Reference

The function receives an alias (nickname) for the original variable. No copy is made, so modifying x directly modifies num.

void doubleValue(int &x) {
    x = x * 2; // Changes the original num
}

int main() {
    int num = 5;
    doubleValue(num);
    // num is now 10
}

Pass by Pointer

The function receives the memory address of the original variable. Using the dereference operator (*), it can directly access and modify the value in the original variable's memory location.

void doubleValue(int *x) {
    *x = (*x) * 2; // Reaches into the address to change value
}

int main() {
    int num = 5;
    doubleValue(&num); // Pass the address of num
    // num is now 10
}

Pass by Const Reference

The function uses the direct memory block (address) but cannot alter the value. This combines the safety of Pass by Value with the efficiency of Pass by Reference by avoiding expensive copies (e.g., when passing large text or 1 million rows of data).

void processBigData(const std::string &data) {
    // data += " modification"; // Error: Cannot modify const reference
    std::cout << "Read-only access to " << data.length() << " chars." << std::endl;
}

int main() {
    std::string hugeText(1000000, 'A'); // Simulate large data
    processBigData(hugeText); // Fast: Passes by address, no copy is made
}

Class in C++

Class Template and Implementation

#ifndef MY_INTEGER_HPP_
#define MY_INTEGER_HPP_

class myInteger {
 private:
  int value {};

 public:
  // default constructor
  myInteger();

  // constructor taking an integer
  // explicit means we don't allow myInteger x = 3
  // the constructor has to be explicitly called
  explicit myInteger(int);

  // copy constructor
  // create a copy constructor with the same value as another myInteger
  myInteger(const myInteger&);

  // assignment operator
  // this enables myInteger x {3}; myInteger y {5}; x = y;
  myInteger& operator=(const myInteger&);
  // allow user to assignment object: a = b = c
  // Without & in the myInteger, it will create copy, causing a redundance work

  // destructor, delete the memory
  ~myInteger();

  // determine if two myIntegers are equal
  friend bool operator==(const myInteger&, const myInteger&);

  // determine if one myInteger is less than another
  friend bool operator<(const myInteger&, const myInteger&);
};

#endif  // MY_INTEGER_HPP_

Class Structure and Encapsulation

class myInteger {
private:
    int value {};

The class stores one private variable: value.
Because it is private, outside code cannot access it directly.
All interaction must happen through constructors, operators, or friend functions.

This demonstrates encapsulation — hiding internal data.

Object Creation (Constructors)

Default Constructor

myInteger::myInteger() {}

Used when no value is provided:

myInteger a;

Because value was declared as int value {};, it is automatically initialized to 0.

Constructor with an Integer

myInteger::myInteger(int input) : value {input} {}

Used when creating an object with a value:

myInteger a(5);

The syntax : value {input} is called a member initializer list. It directly initializes value with input.

The constructor is marked explicit, which prevents:

myInteger a = 5;   // Not allowed

This avoids unintended automatic conversions.

Copying Objects (Copy Constructor)

myInteger::myInteger(const myInteger& x) : value {x.value} {}

Used when creating a new object from an existing one:

myInteger a(5);
myInteger b = a;   // Copy constructor

What happens:

A new object b is created.
b.value is set to a.value.

This teaches how objects are copied safely.

Assigning Objects (Assignment Operator)

myInteger& myInteger::operator=(const myInteger& x) {
    value = x.value;
    return *this;
}

Used when both objects already exist:

myInteger a(5);
myInteger b(3);

b = a;   // Assignment operator

What happens:

b.value is replaced with a.value.
The function returns *this (a reference to the current object).

Returning a reference allows chained assignment:

a = b = c;

If it returned by value instead of reference, extra copies would be created.

Object Destruction (Destructor)

myInteger::~myInteger() {}

Called automatically when an object goes out of scope.

In this class, it does nothing because no dynamic memory is used. However, it demonstrates how cleanup would work if resources were allocated.

Operator Overloading and Friend Functions Relationship

Operator Overloading

The class overloads comparison operators so that objects behave like integers.

Equality Operator

bool operator==(const myInteger& x, const myInteger& y) {
    return x.value == y.value;
}

Allows:

if (a == b)

It compares the private value of both objects.

Less-Than Operator

bool operator<(const myInteger& x, const myInteger& y) {
    return x.value < y.value;
}

Allows:

if (a < b)

Why Are These Operators friend?

In the class:

friend bool operator==(const myInteger&, const myInteger&);
friend bool operator<(const myInteger&, const myInteger&);

These operators are not member functions. They are normal functions defined outside the class.

However, they need access to the private value. The keyword friend gives them permission to access private members.

Without friend, this line would cause an error:

return x.value == y.value;

Summary: Object Lifecycle and Operator Overloading

This class demonstrates:

Encapsulation (private data)
Object initialization (constructors)
Copy construction
Assignment between objects
Object destruction
Operator overloading
Controlled access using friend

Although the class only wraps an int, it teaches how real C++ classes manage their lifecycle and behave like built-in types. This is foundational knowledge for writing safe and well-designed C++ classes.

2. Sequence Containers

2.1 Lecture Part 1: Abstract Data Types (ADTs)

ADT vs Data Structure

ADT Definition: A collection of values and a specification of operations that can be performed on them. It acts like a "user's manual," focusing on what can be done rather than how.
Data Structure Definition: A concrete implementation of an ADT.
Problem Solving Strategy: Design algorithms using ADTs by imagining "special powers" (operations) needed to solve the problem, then find a data structure that efficiently implements those powers

Example: Contains Duplicate

The lecture uses Leetcode 217 to illustrate these concepts.

The Problem: Given an array, determine if any value appears twice.
Brute Force: A double for loop checks every element against all previous elements.
ADT Approach: Define an ADT with two operations: contains(val) and insert(val).
Efficiency: While the double loop is one implementation, using more advanced data structures like Hash Tables or Balanced Binary Search Trees can significantly improve performance.

2.2 Lecture Part 2: Sequence Containers: Vectors, Deques, and Arrays

Fixed-Sized Arrays and the RAM Model

Fixed-Size Array ADT: Requires a maximum size at initialization. Operations include get(i) and set(i, x).
Random Access Memory (RAM) Model:
- Memory is viewed as a long tape of "words" with integer addresses.
- Rule 1: Constant time reading/writing to any address.
- Rule 2: Constant time memory allocation/freeing.
- Rule 3: Constant time arithmetic on addresses.
Implementation: Elements are stored in a contiguous block of memory. The address of any element is calculated using the formula:

\text{Address} = \underbrace{\&arr[0]}_{base\_address} + \underbrace{i \times \text{sizeof(type)}}_{index \times \text{number of bytes per element}}

Resizable Arrays

The Problem: Fixed-size arrays require knowing the size in advance, which isn't always possible.
Resizable Array ADT: Supports push_back(x), pop_back(), size(), get(i), and set(i, x).
Implementation Strategy:
1. Start with a fixed-size array.
2. Fill it from left to right as long as there is excess capacity (takes constant time).
3. When full, allocate a new, larger array, copy the old elements over, and free the old memory.

Growth Strategy: Why Doubling?

Why not just add 1? If we only add 1 element at a time, the cost of copying dominates. To insert N elements, it would take $1 + 2 + 3 + ... + N = O(N^2)$ time.
Why doubling? By doubling the size, we ensure that the expensive copy operation happens less frequently. This leads to an amortized time complexity of $O(1)$ for push_back.

Doubling Strategy: When the array becomes full:

Create a new array
Make its capacity double the old one
Copy old elements into it and Free the old array

Total Copying Cost
Each resize copies all current elements:
1 + 2 + 4 + ... + n/2

Why Not +1 Growth? If capacity increases by 1 each time:

1 + 2 + 3 + ... + (n−1) = n(n−1)/2

This is O(n²) (very slow).

2.3 Vector Functions and Syntax

std::vector Fundamentals

A vector is a dynamic data structure that stores elements in a contiguous block of memory and resizes automatically as needed .

Key Syntax and Operations:

Initialization:
- std::vector<int> nums {3, 1, 4}; — Creates a vector with initial values.
- std::vector<int> result(nums.size(), 1); — Creates a vector of a specific size filled with a default value (e.g., 1).
Accessing Elements:
- nums[i] — Access via indexing operator (fast, no bounds checking) .
- nums.at(i) — Access with bounds checking .
Capacity Management:
- nums.push_back(val) — Adds an element to the end.
- nums.size() — Returns the number of elements currently in the vector .
- nums.capacity() — Returns the total space allocated before a resize is required .
Looping Strategies:
- Standard for-loop: for (std::size_t i = 0; i < nums.size(); i++) — Use std::size_t because it is unsigned and can handle larger indices than int .
  - Alternative of std::size_t is auto, but we need to add u (unsigned), preventing warning
```
for (auto i = 0u; i < nums.size(); i++) {
    // ...
}
```
- Range-based for-loop: for (int n : nums) — Cleanest way to iterate over every element.
- Iterator-based for-loop: for (auto it = nums.begin(); it != nums.end(); it++) — Use iterators to iterate over every element.
```
for (auto it = vec.begin(); it < vec.end(); it++) {
    std::cout << *it << '\n';
}
```

How Vectors Work (Doubling Strategy)

Vectors use a doubling strategy to resize efficiently:

Initial Allocation: When created, a vector has a small initial capacity (e.g., 1 or 2).
Doubling: When full, it allocates a new array with twice the current capacity.
Copying: All existing elements are copied to the new array.
Cleanup: The old array is deleted.

Example:

Action	Size	Capacity	Memory Cost
Create	0	1	1
push_back(10)	1	1	1
push_back(20)	2	2	2 (copy 1 element)
push_back(30)	3	4	4 (copy 2 elements)
push_back(40)	4	4	0
push_back(50)	5	8	4 (copy 4 elements)

Why Doubling?

O(n) amortized time: Each element is copied only when the vector doubles, so the average cost per element is constant .
Avoids O(n²) copying: Unlike +1 growth, doubling keeps copying localized .

3. Templates and Iterators

3.1 Lecture

Code Architecture in C++

In professional C++ development, programs are divided into multiple files. This approach is called separate compilation. It improves organization, maintainability, and compilation efficiency.

Header Files (`.hpp`) – Interface

Header files contain declarations only. They describe:

Class definitions (structure)
Function signatures (name, parameters, return type)
Member variables

They do not contain implementation logic.

Example: student.hpp

#ifndef STUDENT_HPP
#define STUDENT_HPP

#include <string>

class Student {
private:
    std::string name;
    int age;

public:
    Student(std::string n, int a);
    void printInfo();
};

#endif

This file defines what a Student is, but not how its functions work.

Implementation Files (`.cpp`) – Definitions

Implementation files contain the actual logic of functions declared in the header.

Example: student.cpp

#include "student.hpp"
#include <iostream>

Student::Student(std::string n, int a) {
    name = n;
    age = a;
}

void Student::printInfo() {
    std::cout << name << " is " << age << " years old.\n";
}

The Student:: prefix connects the function definition to the class declared in the header.

Compilation and Linking

Compilation happens in two stages:

Compile source files into object files:
```
g++ -c student.cpp
g++ -c main.cpp
```
Link object files into an executable:
```
g++ student.o main.o -o program
```

If only main.cpp changes, student.cpp does not need to be recompiled. This improves efficiency in large projects.

Header Guards

Header guards prevent multiple inclusion of the same header file, which would otherwise cause redefinition errors.

#ifndef STUDENT_HPP
#define STUDENT_HPP

// declarations

#endif

The macro is defined the first time the file is included. Subsequent inclusions are ignored.

Templates (Generic Programming)

Templates allow writing code that works with multiple data types without duplication. They enable generic programming.

Without templates, separate versions of the same function would be required for each type.

Function Template Example

#include <iostream>

template<typename T>
T add(T a, T b) {
    return a + b;
}

int main() {
    std::cout << add(3, 4) << "\n";        // int
    std::cout << add(2.5, 1.5) << "\n";    // double
}

The compiler generates specific versions of the function when it sees how it is used. This is called template instantiation.

Class Template Example

template<typename T>
class Box {
private:
    T value;

public:
    Box(T v) : value(v) {}

    T getValue() {
        return value;
    }
};

Usage:

Box<int> intBox(10);
Box<std::string> strBox("Hello");

One template definition can produce multiple typed classes.

Importance of Templates

The Standard Template Library (STL) is built using templates. Examples include:

std::vector
std::list
std::sort
std::find

Templates allow algorithms to operate generically on containers using iterators.

Iterators

An iterator is an object that allows traversal of elements in a container. It acts similarly to a pointer. Iterators connect containers with algorithms.

Basic Iterator Example

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {10, 20, 30};

    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << "\n";
    }
}

vec.begin() returns an iterator to the first element.
vec.end() returns an iterator to one past the last element.
*it dereferences the iterator to access the value.

Iterators with Algorithms

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {5, 2, 8, 1};
    std::sort(vec.begin(), vec.end());
}

std::sort operates using iterators. It does not depend on the specific container type, only on the iterator capabilities.

Half-Open Interval

STL algorithms use a half-open interval:

[first, last)

This means:

Include first
Exclude last

Half-Open Interval Example

std::vector<int> vec = {10, 20, 30, 40, 50};
std::sort(vec.begin() + 1, vec.end() - 1);

This sorts the elements from index 1 up to but not including the last element.

Important: Dereferencing vec.end() results in undefined behavior.

Iterator Categories

Category	Capabilities	Example Container
Random Access	Jump forward/backward, compare, arithmetic	`std::vector`
Bidirectional	Move forward and backward	`std::list`
Forward	Move forward only	`std::forward_list`

Random Access Example

auto it = vec.begin();
it = it + 2;  // valid for vector

This is invalid for std::list because it does not support random access.

Bidirectional Example

#include <list>

std::list<int> myList = {10, 20, 30};
auto it = myList.begin();
++it; // Move forward to 20
--it; // Move backward to 10

Bidirectional iterators can be incremented (++) and decremented (--), but do not support arithmetic like it + 2.

Forward Example

#include <forward_list>

std::forward_list<int> fList = {10, 20, 30};
auto it = fList.begin();
++it; // Move forward to 20
// --it; // Error: Cannot move backward

Forward iterators can only be incremented sequentially using ++.

Stack vs Heap (Memory Model)

Feature	Stack	Heap
Usage	Local variables and function call frames	Dynamic memory (`new`, `new[]` / `delete`, `delete[]`)
Speed/Management	Fast, automatically managed	Slower, manually managed (unless using smart pointers)
Lifetime	Memory is freed when the variable goes out of scope	Controlled by the programmer; objects can outlive their creation scope
Size limits	Limited and fixed per thread (not suitable for very large allocations)	Used by containers (e.g., `std::vector` naturally stores its elements here)

Stack vs Heap Example

void foo() {
    Player p;                 // p on stack, destroyed at end of foo()
    Player* q = new Player(); // object on heap, pointer q on stack
    // ... use q ...
    delete q;                 // must delete to avoid memory leak
}

Constructors and Destructors

Default Constructor

Called when an object is created without arguments. Used to set sensible defaults.

class Player {
public:
    std::string name;
    int health;

    Player() : name("Unknown"), health(100) {}
};

Parameterized Constructor and Initialization Lists

Initializes an object with explicit values. Prefer initialization lists over assignment inside the constructor body—they are more efficient and required for const members and references.

Player(std::string n, int h) : name(n), health(h) {}

Destructor

Called when an object is destroyed. Used to free resources allocated by the object (e.g., heap memory, file handles, sockets).

~MyVector() {
    delete[] arrayPointer_;
}

Copy Initialization and Assignment

Copy Constructor

Purpose: Defines how to create a new object as a copy of an existing object.

MyVector v1;
MyVector v2 = v1; // copy constructor used

Shallow vs Deep Copy

Shallow Copy (Default): Member-wise copy where pointers are copied as values, meaning both objects point to the same heap memory. Dangerous for owned resources.
Deep Copy: Allocates new memory and copies the actual contents so each object owns its own resource.

The Shallow Copy Problem:

MyVector v1;
v1.arrayPointer_ = new int[5]{1,2,3,4,5};
MyVector v2 = v1; // default shallow copy
// v1 and v2 point to the same memory. When both are destroyed -> double delete -> crash.

Deep Copy Implementation:

MyVector::MyVector(const MyVector& other)
  : size_(other.size_), capacity_(other.capacity_) {
    if (other.arrayPointer_) {
        arrayPointer_ = new int[capacity_];
        for (int i = 0; i < size_; ++i)
            arrayPointer_[i] = other.arrayPointer_[i];
    } else {
        arrayPointer_ = nullptr;
    }
}

Result: v2 receives its own copy of the array and can be safely destroyed independently of v1.

Copy Assignment

Used to overwrite an existing object with data from another (v2 = v1; where both already exist).

Copy-and-Swap Idiom

Best Practice: Use the Copy-and-Swap idiom to ensure exception safety and avoid self-assignment issues.

MyVector& MyVector::operator=(MyVector other) {
    std::swap(arrayPointer_, other.arrayPointer_);
    std::swap(size_, other.size_);
    return *this;
}

The Rule of Three

The Rule of Three states that if a class requires a manual implementation of a raw pointer to heap memory, it likely requires all three:

Destructor: To free the memory (delete[]).
Copy Constructor: To perform a Deep Copy during initialization.
Copy Assignment Operator: To perform a Deep Copy during assignment.

If you omit any of these while using new, your program will likely suffer from memory leaks (forgetting the destructor) or double-free crashes (forgetting the copy logic).

3.2 Templated + MyVector functions

MyVector & Template Example

Set up

1. Overview: What is `MyVector`?

1. Overview: What is MyVector?

template <typename T>
class MyVector { ... };

A dynamic array container similar to std::vector.
Supports adding, removing, and accessing elements dynamically.
Stores size_, capacity_, and arrayPointer_ to manage memory efficiently.

2. Private Variables

T* arrayPointer_ = nullptr;
int size_ = 0;
int capacity_ = 0;

arrayPointer_ points to the first element of a dynamic array.
size_ tracks the number of elements currently in the vector.
capacity_ tracks allocated memory size, which may exceed size_.
Key invariant: size_ <= capacity_.

Functions + Templates

3. Default Constructor

template <typename T>
MyVector<T>::MyVector() {}

Creates an empty vector.
Initial values: arrayPointer_ = nullptr, size_ = 0, capacity_ = 0.

4. Constructor with Size

template <typename T>
MyVector<T>::MyVector(int n) :
  arrayPointer_ {n > 0 ? new T[n]{} : nullptr},
  size_ {n},
  capacity_ {n} {}

Allocates memory for n elements initialized to 0.
Both size_ and capacity_ are set to n.
Example: MyVector<int> v(5) → [0,0,0,0,0].

5. Copy Constructor

template <typename T>
MyVector<T>::MyVector(const MyVector<T>& other) 
  : arrayPointer_ {other.size_ > 0 ? new T[other.size_] : nullptr},
    size_ {other.size_},
    capacity_ {other.capacity_} {
    for (int i = 0; i < size_; ++i)
        arrayPointer_[i] = other.arrayPointer_[i];
}

Used when copying a vector: MyVector<int> b = a;.
Allocates new memory and copies elements.
Ensures a and b point to different memory.

6. Initializer List Constructor

template <typename T>
MyVector<T>::MyVector(std::initializer_list<T> vals) {
  size_ = capacity_ = vals.size();
  arrayPointer_ = new T[size_];
  int i = 0;
  for (T x : vals)
    arrayPointer_[i++] = x;
}

Allows vector initialization with {}: MyVector<int> v = {1,2,3};.
Sets size_ and capacity_ to list size.
Copies each element from the initializer list.

7. Destructor

template <typename T>
MyVector<T>::~MyVector() {
  delete[] arrayPointer_;
}

Frees dynamically allocated memory.
Prevents memory leaks from new T[].

8. Copy Assignment Operator

template <typename T>
MyVector<T>& MyVector<T>::operator=(MyVector<T> other) {
  std::swap(arrayPointer_, other.arrayPointer_);
  std::swap(size_, other.size_);
  std::swap(capacity_, other.capacity_);
  return *this;
}

Implements copy-swap idiom.
Swaps content of *this with other for safe assignment.
Handles self-assignment and memory management automatically.

9. push_back()

template <typename T>
void MyVector<T>::push_back(T val) { ... }

Adds an element at the end of the vector.
If size_ < capacity_, simply store the value.
If size_ == capacity_, double capacity_, allocate new memory, copy old elements, delete old memory, then add the new value.
Maintains size_ correctly after addition.

10. pop_back()

template <typename T>
void MyVector<T>::pop_back() {
  if (!empty()) --size_;
}

Removes the last element by decreasing size_.
Memory remains allocated; element is logically removed.

11. back()

template <typename T>
T& MyVector<T>::back() {
  return arrayPointer_[size_ - 1];
}

Returns a reference to the last element.
Can be used to read or modify the last element.
Requires size_ > 0 to be safe.

12. empty()

template <typename T>
bool MyVector<T>::empty() {
  return size_ == 0;
}

Returns true if the vector has no elements.
Simple check on size_.

13. size()

template <typename T>
int MyVector<T>::size() const {
  return size_;
}

Returns the number of elements stored.
Constant function, does not modify the vector.

14. capacity()

template <typename T>
int MyVector<T>::capacity() const {
  return capacity_;
}

Returns the allocated memory size (max elements without reallocation).

15. operator[]

template <typename T>
T& MyVector<T>::operator[](int i) { return arrayPointer_[i]; }

template <typename T>
const T& MyVector<T>::operator[](int i) const { return arrayPointer_[i]; }

Access elements by index: v[i].
Returns by reference so values can be modified.
Const version allows read-only access.
If returned by value, assignment like v[0] = 5 would not work.

C++ needs two versions to handle:

Non-const objects → can read and modify elements.

MyVector<int> v;
v[0] = 5;  // uses non-const version
// ---------------
MyVector<int> v = {1,2,3};
v[0] = 10;  // ✅ Can modify

Const objects → can only read elements.

const MyVector<int> cv;
int x = cv[0];  // uses const version
// ---------------
const MyVector<int> cv = {1,2,3};
int x = cv[0];  // ✅ Can read
cv[0] = 10;     // ❌ Error! Cannot modify, because it's const

16. Explicit Template Instantiation

template class MyVector<int>;
template class MyVector<float>;
template class MyVector<double>;

Tells the compiler to generate code for these types.
Ensures vector works for int, float, and double.

17. Example of Memory Layout

MyVector<int> v = {1,2,3};

arrayPointer_ → [1][2][3][ ][ ][ ]
size_ = 3
capacity_ = 6

Shows size_ vs capacity_.
Unused memory is allocated but ignored until needed.

18. Core Concepts Learned

Dynamic memory allocation: new[] / delete[].
Pointers to manage dynamic arrays.
Copy constructor ensures separate memory for copies.
Push-back resizing doubles capacity.
Access via reference allows modification.
Efficient memory management with copy-swap idiom.

4. Linked Lists

4.1 Lecture

Linked List: Singly Linked List

Each node contains a value and a pointer to the next node.
Last node points to nullptr.
Insertion and deletion are efficient.
Random access is not supported.
Memory allocation is dynamic, not contiguous.

4.2 Singly Linked List + forward_list Example

forward_list Example

Set up

1. Overview: What is `ForwardList`?

1. Overview: What is ForwardList?

class ForwardList { ... };

Implements a singly linked list storing integers.
Each node stores data and a pointer to the next node.
Supports operations: push/pop at the front, access front element, display, check empty, and get size.

2. Node Structure

struct Node {
    int data {};
    Node* next = nullptr;
    Node(){}
    Node(int input_data, Node* next_node = nullptr) : data{input_data}, next{next_node} {}
};

data stores the value of the node.
next points to the next node in the list.
Constructors allow default creation or setting data and next node pointer.

3. Private Variables

int size_ = 0;
Node* head_ = nullptr;

size_ tracks the number of nodes.
head_ points to the first node of the list.
If head_ == nullptr, the list is empty.

Functions

4. Default Constructor

ForwardList::ForwardList() {}

Creates an empty list.
head_ is initialized to nullptr, size_ = 0.

5. Destructor

ForwardList::~ForwardList() {
  for (Node* cur = head_; cur != nullptr;) {
    Node* tmp = cur;
    cur = cur->next;
    delete tmp;
    --size_;
  }
}

Frees all nodes to prevent memory leaks.
Traverses from head_ to the end, deleting each node.
Updates size_ as nodes are deleted.

6. Constructor from Initializer List

ForwardList::ForwardList(std::initializer_list<int> input) {
  for (auto it = std::rbegin(input); it != std::rend(input); it++) {
    push_front(*it);
  }
}

Allows initialization: ForwardList fl = {1,2,3};
Iterates backwards through the initializer list.
Calls push_front to maintain order.

7. push_front()

void ForwardList::push_front(int data) {
  head_ = new Node{data, head_};
  size_++;
}

Adds a node at the beginning.
Creates a new node pointing to the old head_.
Updates head_ to the new node.
Increases size_.

8. pop_front()

void ForwardList::pop_front() {
  Node* temp = head_;
  head_ = head_->next;  // (*head_).next
  delete temp;
  size_--;
}

Removes the first node.
head_ = head_->next moves the head pointer to the second node.
Deletes the old head node.
Decreases size_.

Why `head_->next` and not `head_.next`?

head_ is a pointer to Node, not a Node object.
head_.next would be valid only if head_ were an object, because . accesses members of an object.
-> is shorthand for (*head_).next:
```
head_->next == (*head_).next
```
Always use -> when accessing members through a pointer.

9. front() by Value

int ForwardList::front() const {
  return head_->data;
}

Returns the value of the first node.
Const version, cannot modify the node.

10. front() by Reference

int& ForwardList::front() {
  return head_->data;
}

Returns a reference to the first node’s data.
Allows modifying the value:
```
fl.front() = 10;
```

11. display()

void ForwardList::display() const {
  for (Node* it = head_; it != nullptr; it = it->next)
    std::cout << it->data << (it->next ? " " : "");
}

Traverses the list from head_ to nullptr.
Prints values in sequence, separated by spaces.

12. empty()

bool ForwardList::empty() const {
  return size_ == 0;
}

Returns true if the list has no nodes.

13. size()

int ForwardList::size() const {
  return size_;
}

Returns the number of nodes in the list.

14. Key Concepts

Singly linked list: each node points only to the next.
head_ pointer: always points to the first node.
Dynamic memory: new/delete for node allocation.
Push/Pop front: O(1) operations.
Accessing node members:
- Use -> for pointers (head_->next).
- Use . for objects (node.data).
Const vs reference access:
- front() const → read only.
- front() non-const → read/write.

1. Intro to C++

1.1 Lecture​

Introduction to C++​

Memory Management: Variables, References, and Pointers​

Variables​

References​

Pointers​

Passing Variables to Functions​

Class in C++​

Class Template and Implementation​

2. Sequence Containers

2.1 Lecture Part 1: Abstract Data Types (ADTs)​

ADT vs Data Structure​

Example: Contains Duplicate​

2.2 Lecture Part 2: Sequence Containers: Vectors, Deques, and Arrays​

Fixed-Sized Arrays and the RAM Model​

Resizable Arrays​

2.3 Vector Functions and Syntax​

3. Templates and Iterators

3.1 Lecture​

Code Architecture in C++​

Header Files (.hpp) – Interface​

Implementation Files (.cpp) – Definitions​

Compilation and Linking​

Header Guards​

Templates (Generic Programming)​

Importance of Templates​

Iterators​

Half-Open Interval​

Iterator Categories​

Stack vs Heap (Memory Model)​

Constructors and Destructors​

Default Constructor​

Parameterized Constructor and Initialization Lists​

Destructor​

Copy Initialization and Assignment​

Copy Constructor​

Copy Assignment​

The Rule of Three​

3.2 Templated + MyVector functions​

MyVector & Template Example​

Set up​

1. Overview: What is MyVector?​

2. Private Variables​

Functions + Templates​

3. Default Constructor​

4. Constructor with Size​

5. Copy Constructor​

6. Initializer List Constructor​

7. Destructor​

8. Copy Assignment Operator​

9. push_back()​

10. pop_back()​

11. back()​

12. empty()​

13. size()​

14. capacity()​

15. operator[]​

16. Explicit Template Instantiation​

17. Example of Memory Layout​

18. Core Concepts Learned​

4. Linked Lists

4.1 Lecture​

Linked List: Singly Linked List​

4.2 Singly Linked List + forward_list Example​

Set up​

1. Overview: What is ForwardList?​

2. Node Structure​

3. Private Variables​

Functions​

4. Default Constructor​

5. Destructor​

6. Constructor from Initializer List​

7. push_front()​

8. pop_front()​

Why head_->next and not head_.next?​

9. front() by Value​

10. front() by Reference​

11. display()​

12. empty()​

1.1 Lecture

Introduction to C++

Memory Management: Variables, References, and Pointers

Variables

References

Pointers

Passing Variables to Functions

Class in C++

Class Template and Implementation

2.1 Lecture Part 1: Abstract Data Types (ADTs)

ADT vs Data Structure

Example: Contains Duplicate

2.2 Lecture Part 2: Sequence Containers: Vectors, Deques, and Arrays

Fixed-Sized Arrays and the RAM Model

Resizable Arrays

2.3 Vector Functions and Syntax

3.1 Lecture

Code Architecture in C++

Header Files (`.hpp`) – Interface

Implementation Files (`.cpp`) – Definitions

Compilation and Linking

Header Guards

Templates (Generic Programming)

Importance of Templates

Iterators

Half-Open Interval

Iterator Categories

Stack vs Heap (Memory Model)

Constructors and Destructors

Default Constructor

Parameterized Constructor and Initialization Lists

Destructor

Copy Initialization and Assignment

Copy Constructor

Copy Assignment

The Rule of Three

3.2 Templated + MyVector functions

MyVector & Template Example

Set up

1. Overview: What is `MyVector`?

2. Private Variables

Functions + Templates

3. Default Constructor

4. Constructor with Size

5. Copy Constructor

6. Initializer List Constructor

7. Destructor

8. Copy Assignment Operator

9. push_back()

10. pop_back()

11. back()

12. empty()

13. size()

14. capacity()

15. operator[]

16. Explicit Template Instantiation

17. Example of Memory Layout

18. Core Concepts Learned

4.1 Lecture

Linked List: Singly Linked List

4.2 Singly Linked List + forward_list Example

Set up

1. Overview: What is `ForwardList`?

2. Node Structure

3. Private Variables

Functions

4. Default Constructor

5. Destructor

6. Constructor from Initializer List

7. push_front()

8. pop_front()

Why `head_->next` and not `head_.next`?

9. front() by Value

10. front() by Reference

11. display()

12. empty()

13. size()

14. Key Concepts

5.1 Lecture

Linear Data Structures and Hashing Collisions