C++ Memory Management, Data Structures, and Recursion
Dynamic Memory Allocation in C++
Dynamic Memory: Use the new keyword to allocate memory on the heap. It returns the address of the allocated memory. Note: For dynamic arrays, use delete[]. Note: When dynamic arrays store pointers to dynamically allocated objects, you need to delete each element before freeing the array itself.
Common Memory Issues
- Memory Leak: Forgetting to free memory allocated with
new. - Orphaned Memory: Losing the address of allocated memory.
- Double Free: Attempting to free memory twice.
- Non-Heap Delete: Using
deleteon a non-heap pointer. - Wrong Delete: Using
deleteinstead ofdelete[]for arrays.
RAII (Resource Acquisition Is Initialization)
RAII automates memory management, reducing errors like leaks or double frees.
The Big Three and Resource Management
Use the Big Three when a class manages resources like dynamic memory (e.g., pointers, file handles), or when a constructor allocates dynamic memory or initializes complex resources.
-
Copy Constructor:
UnsortedSet(const UnsortedSet &other) : elts(new T[other.capacity]), capacity(other.capacity), elts_size(other.elts_size) { for (int i = 0; i < other.elts_size; ++i) { elts[i] = other.elts[i]; } } -
Assignment Operator:
UnsortedSet& operator=(const UnsortedSet &rhs) { if (this == &rhs) return *this; // Self-assignment check delete[] elts; // Clean up old resources elts = new T[rhs.capacity]; capacity = rhs.capacity; elts_size = rhs.elts_size; for (int i = 0; i < rhs.elts_size; ++i) { elts[i] = rhs.elts[i]; } return *this; }
Iterators and Functors in C++
Iterators
Traverse through a container with an iterator. Use a pointer or iterator to move through elements in sequence. Start at the first element and move to the next using the next pointer until you reach a null pointer.
Example:
void print(ostream &os) const {
for (Node *np = first; np; np = np->next) {
os << np->datum << " ";
}
os << endl;
}When Iterators Become Invalid
- If elements are added or removed while using the iterator.
- If the container is destroyed or modified in a way that reallocates memory.
End Iterator: Represents a position just past the last element in a container. It’s a stopping point in iteration (null in linked lists or container.end() in STL).
Functors
A functor is a class or struct with an overloaded operator() that acts like a function. It allows objects to be used where functions are expected.
Why Use Functors: Functors can maintain state between calls (unlike regular functions) and are flexible for customization in algorithms.
Example:
struct MultiplyBy {
int factor;
MultiplyBy(int f) : factor(f) {}
int operator()(int x) const {
return x * factor;
}
};
MultiplyBy times2(2);
cout << times2(5); // Output: 10Predicate: A function or functor that returns true or false. Used for conditional checks in algorithms like find_if.
Example:
bool isEven(int x) { return x % 2 == 0; }Comparator: A function or functor that defines a custom sorting rule by comparing two elements.
Example:
bool compareLength(const string &a, const string &b) { return a.size() < b.size(); }Range-based for loops internally use iterators to traverse a container.
Example:
for (int x : list) { ... }Dereference When: You need the value the iterator points to.
Example:
for (auto it = container.begin(); it != container.end(); ++it) {
cout << *it << " ";
}Iterators typically reference memory managed by the container. Containers handle memory; implementing the Big Three in iterators could lead to confusion or double deletions.
Function Pointers
A function pointer is a variable that holds the address of a function. It can be used to pass functions as arguments.
Example:
int add(int a, int b) {
return a + b;
}
int (*funcPtr)(int, int) = add;
cout << funcPtr(5, 3); // Output: 8Linked Lists in C++
Linked List: A linked list uses non-contiguous memory; each node is dynamically allocated and linked via pointers. It is faster for insertion/deletion at arbitrary positions if you already have the node pointer.
Example:
Node* iterator = head; // head points to the first node of the listTraversing Example:
for (Node* it = head; it != nullptr; it = it->next) {
cout << it->datum << " ";
}Iterating and Printing Example:
Node* it = head;
while (it != nullptr) {
cout << it->datum << " ";
it = it->next;
}Adding Nodes
void push_front(int value) {
Node* newNode = new Node{value, head};
head = newNode;
}Deleting Nodes
void pop_front() {
if (head) {
Node* toDelete = head;
head = head->next;
delete toDelete;
}
}Chopping a List (Removing All Nodes)
void clear() {
while (head != nullptr) {
pop_front();
}
}Stretching a List (Adding Nodes to the End)
void push_back(int value) {
Node* newNode = new Node{value, nullptr};
if (head == nullptr) {
head = newNode;
} else {
Node* it = head;
while (it->next != nullptr) {
it = it->next;
}
it->next = newNode;
}
}Recursion in C++
Recursion: A function calling itself.
- Tail Recursion: The recursive call is the last operation in the function (e.g., factorial with an accumulator).
- Tree Recursion: Each call results in multiple recursive calls (e.g., Fibonacci sequence).
- Structural Recursion: The recursion operates on data structures like lists or trees, breaking them into smaller parts.
Example:
int fact(int n) {
if (n <= 1) return 1; // Base case
return n * fact(n - 1); // Recursive case
}How to Break Down a Problem Recursively
- Define the base case.
- Break the problem into smaller sub-problems.
- Combine results from sub-problems into the final solution.
Structural Recursion Example:
void reverse(int *left, int *right) {
if (left >= right) return; // Base case.
swap(*left, *right); // Swap elements
reverse(left + 1, right - 1); // Recursive case
}Recursive functions often process one element (e.g., the head of a linked list or the root of a tree) and then recurse on the remaining structure.
A base case should define the simplest scenario where recursion stops.
Example: For the sum of a list:
if (list == nullptr) return 0;- Normal Recursion: Each recursive call adds a frame to the stack (linear space complexity, O(n)).
- Tail Recursion: Stack frames are reused (constant space complexity, O(1)) if optimized by the compiler.
Iteration to Recursion
Use recursion to replace loops:
void printArray(int arr[], int n) {
if (n == 0) return;
cout << arr[0] << " ";
printArray(arr + 1, n - 1);
}Recursion to Iteration
Replace recursion with explicit loops.
Use recursion when:
- Problems can be broken into smaller sub-problems.
- Working with recursive data structures (e.g., trees).
Use iteration for simple, repetitive tasks without structural breakdown.
Binary Search Trees in C++
Each node contains:
- Datum (value).
- Left pointer (subtree with smaller values).
- Right pointer (subtree with larger values).
Insert
void insert(Node* &root, int value) {
if (!root) root = new Node{value, nullptr, nullptr}; // Base case
else if (value < root->datum) insert(root->left, value);
else insert(root->right, value);
}Find
bool contains(Node* root, int value) {
if (!root) return false; // Base case
if (root->datum == value) return true;
return value < root->datum ? contains(root->left, value) : contains(root->right, value);
}Height
int height(Node* root) {
if (!root) return 0; // Base case
return 1 + max(height(root->left), height(root->right)); // Recursive case
}Destructor
~BinarySearchTree() { clear(root); }
void clear(Node* root) {
if (!root) return;
clear(root->left);
clear(root->right);
delete root;
}Copy Constructor
Node* copy(Node* root) {
if (!root) return nullptr;
return new Node{root->datum, copy(root->left), copy(root->right)};
}Assignment Operator
BinarySearchTree& operator=(const BinarySearchTree &other) {
if (this == &other) return *this;
clear(root);
root = copy(other.root);
return *this;
}
void preorder(Node* root) {
if (!root) return;
cout << root->datum << " ";
preorder(root->left);
preorder(root->right);
}