Section5: OOP, Pointers, and Heaps, Oh My!

Section materials curated by our Head TA Trip Master, drawing upon materials from previous quarters. Special thanks to
Nick Bowman and Julie Zelenski for awesome ideas!

This week’s section cover a handful of topics: object oriented programming, to keep your class-skills sharp, pointers and memory management, to deepen your knowledge of how computers operate under the hood, and linked lists, to show you a totally new kind of data structure! There's no place like main().

Remember that every week we will also be releasing a Qt Creator project containing starter code and testing infrastructure for that week's section problems. When a problem name is followed by the name of a .cpp file, that means you can practice writing the code for that problem in the named file of the Qt Creator project. Here is the zip of the section starter code:

📦 Starter code

1) Reciprocate and Divide (Fraction.h/.cpp)

Topics: Classes

Consider the Fraction class from lecture.

class Fraction {
public:
	Fraction();
	Fraction(int num, int denom);
	void add(Fraction f);
	void multiply(Fraction f);
	double decimal();
	int getNumer();
	int getDenom();
	friend ostream& operator<<(ostream &out, Fraction &frac);
private:
	int numer;
	int demon;
	void reduce();
	int gcd(int u, int v);
}

We're going to expand the interface with two additional methods.

Add a public method named reciprocal to the Fraction class which converts the fraction to its reciprocal (note that by definition the reciprocal of a number x is a number y such that xy == 1 holds). You can assume the numerator and denominator will always be non-zero.

Add a public method named divide to the Fraction class that takes in a Fraction f and divides the original Fraction by f. You can assume the numerator and denominator will always be non-zero.

Solution 
void Fraction::reciprocal() {
	int tempDenom = denom;
	denom = numer;
	numer = tempDenom;
}

void Fraction::divide(Fraction other) {
	multiply(Fraction(other.getDenom(), other.getNumer()));
}

2) A Series of Unfortunate References

Topics: Pointers and references

What is the output of the following code snippet?

void VFD(int *duncan, int isadora, int& quigley) {
	isadora += *duncan;
	quigley *= isadora;
	(*duncan) = 1;
	isadora = *duncan;
}

int main() {
	int sunny = -6;
	int klaus = 21;
	int violet = 2;
	VFD(&sunny, violet, klaus);
 	cout << sunny << " " << klaus << " " << violet << " " << endl; 
 	return 0;
}
Solution

1 -84 2

3) Pointed Points about Pointers

Topics: Arrays and pointers

Pointers to arrays are different in many ways from ADTs in how they interact with pass by-value and the = operator. To better understand how they work, trace through the following program. What is its output?

void print(int* first, int* second) {
	for (int i = 0; i < 5; i++) {
		cout << i << ": " << first[i] << ", " << second[i] << endl;
	}
}
void transmogrify(int* first, int* second) {
	for (int i = 0; i < 5; i++) {
		first[i] = 137;
	}
}
void mutate(int* first, int* second) {
	first = second;
	second[0] = first[0];
}
void change(int* first, int* second) {
	first = new int[5];
	second = new int[5];
	for (int i = 0; i < 5; i++) {
		first[i] = second[i] = 271;
	}
}
int main() {
	int* one = new int[5];
	int* two = new int[5];

	for (int i = 0; i < 5; i++) {
		one[i] = i;
		two[i] = 10 * i;
	}

	transmogrify(one, two);
	print(one, two);
	
	mutate(one, two);
	print(one, two);
	
	change(one, two);
	print(one, two);
	
	delete[] one;
	delete[] two;
	return 0;
}
Solution

The output of the program is shown here:

0: 137, 0
1: 137, 10
2: 137, 20
3: 137, 30
4: 137, 40
0: 137, 0
1: 137, 10
2: 137, 20
3: 137, 30
4: 137, 40
0: 137, 0
1: 137, 10
2: 137, 20
3: 137, 30
4: 137, 40

Remember that when passing a pointer to a function, the pointer is passed by value! This means that you can change the contents of the array being pointed at, because those elements aren't copied when the function is called. On the other hand, if you change which array is pointed at, the change does not persist outside the function because you have only changed the copy of the pointer, not the original pointer itself.

4) The Notorious RBQ, Revisited (RingBufferQueue.h/.cpp)

Topics: Classes, dynamic memory allocation, pointers

Remember our good friend the RingBufferQueue from last section? Check out the problem definition from last week if you want a quick refresher. Last time we visited the RBQ it had fixed capacity – that is, it couldn't grow in size after it was initially created. How limiting! With our newfound pointer and dynamic allocation skills, we can remove this limitation on the RBQ and make it fully functional!

Add functionality to the class RingBufferQueue from the previous section problem so that the queue resizes to an array twice as large when it runs out of space. In other words, if asked to enqueue when the queue is full, it will enlarge the array to give it enough capacity.

For example, say our queue can hold 5 elements and we enqueue the five values 10, 20, 30, 40, and 50. Our queue would look like this:

index    0    1    2    3    4
      +----+----+----+----+----+
value | 10 | 20 | 30 | 40 | 50 |
      +----+----+----+----+----+
         ^                   ^
         |                   |
       head                tail

If the client tries to enqueue a sixth element of 60, your improved queue class should grow to an array twice as large:

index    0    1    2    3    4    5    6    7    8    9
      +----+----+----+----+----+----+----+----+----+----+
value | 10 | 20 | 30 | 40 | 50 | 60 |    |    |    |    |
      +----+----+----+----+----+----+----+----+----+----+
         ^                        ^
         |                        |
       head                     tail

The preceding is the simpler case to handle. But what about if the queue has wrapped around via a series of enqueues and dequeues? For example, if the queue stores the following five elements:

index    0    1    2    3    4
      +----+----+----+----+----+
value | 40 | 50 | 10 | 20 | 30 |
      +----+----+----+----+----+
              ^    ^
              |    |
            tail head

If the client tries to add a sixth element of 60, you cannot simply copy the array as it is shown. If you do so, the head and wrapping will be broken. Instead, copy into the new array so that index 0 always becomes the new head of the queue. The picture will look the same as the previous one with the value 60 at index 5.

Write up the implementation of the new and improved RingBufferQueue. It should have the same members as in the previous problem, but with the new resizing behavior added. You may add new member functions to your class, but you should make them private.

Solution

RingBufferQueue.h

#pragma once

#include <iostream>
using namespace std;
class RingBufferQueue {
public:
    RingBufferQueue();
    ~RingBufferQueue();
    bool isEmpty() const;
    bool isFull() const;
    int size() const;
    void enqueue(int elem);
    int dequeue();
    int peek() const;
private:
    int* _elements;
    int _capacity;
    int _size;
    int _head;
    friend ostream& operator <<(ostream& out, const RingBufferQueue& queue);
    void enlarge();
};

RingBufferQueue.cpp

#include "RingBufferQueue.h"

static int kDefaultCapacity = 5;
RingBufferQueue::RingBufferQueue() {
    _capacity = kDefaultCapacity;
    _elements = new int[_capacity];
    _head = 0;
    _size = 0;
}
RingBufferQueue::~RingBufferQueue() {
    delete[] _elements;
}
void RingBufferQueue::enqueue(int elem) {
    if (isFull()) {
        enlarge();
    }
    int tail = (_head + _size) % _capacity;
    _elements[tail] = elem;
    _size++;
}
int RingBufferQueue::dequeue() {
    int front = peek();
    _head = (_head + 1) % _capacity;
    _size--;
    return front;
}
int RingBufferQueue::peek() const {
    if (isEmpty()) {
        throw "Can't peek at an empty queue!";
    }
    return _elements[_head];
}
bool RingBufferQueue::isEmpty() const {
    return _size == 0;
}
bool RingBufferQueue::isFull() const {
    return _size == _capacity;
}
int RingBufferQueue::size() const {
    return _size;
}
void RingBufferQueue::enlarge() {
    int *larger = new int[_capacity * 2];
    for (int i = 0; i < _size; i++) {
        larger[i] = _elements[(_head + i) % _capacity];
    }
    delete[] _elements;
    _elements = larger;
    _capacity *= 2;
    _head = 0;
}
ostream& operator <<(ostream& out, const RingBufferQueue& queue) {
    out << "{";
    if (!queue.isEmpty()) {
        // We can access the inner ‘_elements’ member variables because
        // this operator is declared as a friend of the RingBufferQueue class
        out << queue._elements[queue._head];
        for (int i = 1; i < queue.size(); i++) {
            int index = (queue._head + i) % queue._capacity;
            out << ", " << queue._elements[index];
        }
    }
    out << "}";
    return out;
}

5) Cleaning Up Your Messes

Topics: Dynamic allocation and freeing

Whenever you allocate an array with new[], you need to deallocate it using delete[]. It's important when you do so that you only deallocate the array exactly once – deallocating an array zero times causes a memory leak, and deallocating an array multiple times usually causes the program to crash. (Fun fact – deallocating memory twice is called a double free and can lead to security vulnerabilities in your code! Take CS155 for details.)

Below are three code snippets. Trace through each snippet and determine whether all memory allocated with new[] is correctly deallocated exactly once. If there are any other errors in the program, make sure to report them as well.

Snippet 1

int main() {
	int* arya = new int[3];
	int* jon = new int[5];

	arya = jon;
	jon = arya;

	delete[] arya;
	delete[] jon;
	
	return 0;
}

Snippet 2

int main() {
	int* stark = new int[6];
	int* lannister = new int[3];
	
	delete[] stark;
	stark = lannister;
	
	delete[] stark;
	return 0;
}

Snippet 3

int main() {
	int* tyrell = new int[137];
	int* arryn = tyrell;
	
	delete[] tyrell;
	delete[] arryn;
	
	return 0;
}
Solution

The first piece of code has two errors in it. First, the line

arya = jon;

causes a memory leak, because there is no longer a way to deallocate the array of three elements allocated in the first line. Second, since both arya and jon point to the same array, the last two lines will cause an error.

The second piece of code is perfectly fine. Even though we execute

delete[] stark;

twice, the array referred to each time is different. Remember that you delete arrays, not pointers.

Finally, the last piece of code has a double-delete in it, because the pointers referred to in the last two lines point to the same array.

6) Min Heap

Topics: Heaps

We have implemented the Priority Queue ADT using a binary min-heap. Draw a diagram of the heap’s tree structure that results from inserting the following priority values in the order given: 25, 37, 28, 12, 30, 3

This image contains a table with 2 rows and three columns, for a total of 6 entries. These entries read as follows (left to right, top to bottm): 1) Diagram after inserting 25 2) Diagram after inserting 37 3) Diagram after inserting 28 4) Diagram after inserting 12 5) Diagram after inserting 30 6) Diagram after inserting 3

Solution

This image has six parts that diagram insertion of ints into a min heap. The parts show insertion of the following elements in order: 25, 37, 28, 12, 30, and 3. 25 is inserted first, and is the only node in the heap, with no children. 37 is inserted next, and is inserted at the ‘end’ of the heap, as the left-most empty spot as the left child of 25. Becuase its parent, 25, is less than 37, no movement is necessary. 28 is inserted next, and is inserted at the ‘end’ of the heap, as the right child of 25. Because it’s parent, 25, is less than 28, no movement is necessary. 12 is inserted next, and is inserted at the ‘end’ of the heap, as the left child of 37. Because its parent, 37, is greater than 12, the 12 ‘bubbles up’ by swapping with 37 so that is new parent is 25. Because 25 is greater than 12, the 12 bubbles up again by swapping with the 25. At this point, the heap has 12 as the root with left child 25 and right child 28. The 25 has a left child, 37. The ‘end’ of the heap is now the right-child of 25. 30 is inserted at the ‘end’ of the heap as the right child of 25. Because 25 is less than 30, no movement is necessary. The ‘end’ of the heap is now the left-child of 28. Finally, 3 is inserted into the heap at the ‘end’, as the left child of 28. Because 28 is greater than 3, the 3 swaps position with the 28 to bubble up to become the right child of 12. Because 12 is greater than 3, the 3 swaps with 12 to bubble up to become the root of the heap. The final position of all the elements is 3 at the root, with left child 25 and right child 12. The 25 has a left child of 37 and a right child of 30. The 12 has a left child of 28.

7) Max Heap

Topics: Heaps

You have a PriorityQueue class which treats higher (larger integer value) priority elements as frontmost. The internal implementation of the class is a binary max-heap stored in an unfilled array. The initial allocation of the array is for capacity 5 and the array capacity is doubled when asked to enqueue to a queue which is full. You are going to trace the operation of enqueuing and dequeuing elements from the priority queue. You can sketch as a tree if you prefer when working it out, but your final answer should be based on a representation of the underlying array that supports the heap.

(a) Show the contents of the internal array after these elements are enqueued to an empty priority queue in this order. Each element has a string value and a priority in parenthesis.

Red(8), Blue(33), Green(29), Purple(42), Orange(20), Yellow(22), Indigo(10), Teal(21)

(b) Dequeue is called twice on the priority queue. Which two values are removed?

(c) Show the contents of the internal array after the above two elements have been dequeued

Solution

(a) Color names are abbreviated


    

        elements:
        P(42)
        B(33)
        G(29)
        T(21)
        O(20)
        Y(22)
        I(10)
        R(8)
        ?
        ?
    

    

        index:
         0 
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 

(b) Purple(42) and Blue(33)

(c)


    

        elements:
        G(29)
        T(21)
        Y(22)
        R(8)
        O(20)
        I(10)
        ?
        ?
        ?
        ?
    

    

        index:
         0 
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 

8) Reversing a Linked List (reverse.cpp)

Topics: Linked Lists

For the final problem in this handout, assume the following structures have been declared:

struct Node {
    int data;
    Node *next;
};

struct StringNode {
    string data;
    StringNode *next;
};

struct DoubleNode {
    double data;
    DoubleNode *next;
};

You can also assume the following utility functions have been defined as well:

/* Prints the contents of a linked list, in order. */
void printList(Node* list) {
    for (Node* cur = list; cur != nullptr; cur = cur->next) {
        cout << cur->data << endl;
    }
}

/* Frees all the memory used by a linked list. */
void deleteList(Node* list) {
    while (list != nullptr) {
        /* Store where to go next, since we're about to blow up our linked
         * list node.
         */
        Node *next = list->next;
        delete list;
        list = next;
    }
}

Write a function reverse that reverses the order of the elements in a list of integers. For example, if a list initially stores the sequence of integers below at left, it should store the sequence at right after your function is called:

{1, 8, 19, 4, 17} -> {17, 4, 19, 8, 1}

You should implement your code to match the following prototype

void reverse(Node*& front)

Bonus: This one also has an interesting recursive solution.

Solution 
void reverse(Node*& front) {
    Node* current = front;
    Node* previous = nullptr;
    while (current != nullptr) {
        Node* nextNode = current->next;
        current->next = previous;
        previous = current;
        current = nextNode;
    }
    front = previous;
}