Section 5. Classes and Dynamic Memory

Section materials curated by Trip Master, drawing upon materials from previous quarters.

This week’s section exercise consists of several larger problems that will give you practice with designing classes and working with dynamic array allocation. These problems will help you get practice with the skills that you need for the next assignment, where you will start to implement your very own data structures! As you work on these problems, you may find this Classes and Objects Syntax Sheet to be helpful.

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) The Notorious RBQ (RingBufferQueue.h/.cpp)

Topics: Classes, dynamic arrays

Think back to week 2 when we studied collections. We learned about Queues, a "first-in, first-out" data structure. Today in section, we're going to implement a special type of queue called a Ring Buffer Queue. A Ring Buffer Queue, or RBQ, is implemented by using an underlying array. In our implementation, the capacity is capped; once the array is full, additional elements cannot be added until something is dequeued. Another "interesting" thing about RBQs is that we don't want to shift elements when an element is enqueued or dequeued. Instead, we want to keep track of the front and tail of the Queue. For example, say our queue can hold 5 elements and we enqueue 3 elements: 1, 2, 3. Our queue would look like this:

Array with 5 elements. The leftmost 3 elements are 1,2,3 in that order and the rightmost 2 elements are empty. The element 1 is marked with an arrow that says "head" and the element 3 is marked with an arrow that says "tail".

If we enqueued two more elements, our queue would then be full:

Array with 5 elements. All elements are populated 1,2,3,4,5 in that order from left to right. The element 1 is marked with an arrow that says "head" and the element 5 is marked with an arrow that says "tail".

At this point, we cannot add any additional elements until we dequeue at least one element. Dequeuing will remove the element at head, and head will move onto the next element. If we dequeue 2 elements, our queue will look like this:

Array with 5 elements. The leftmost two spots are empty. The rightmost 3 elements are populated 3,4,5. The element 3 is marked with an arrow that says "head" and the element 5 is marked with an arrow that says "tail".

Now there's room to add more elements! Since we still don't want to shift any elements, adding an additional element will wrap around. So, if we enqueue an element, our queue will look like this:

Array with 5 elements. The leftmost element is the value 6, and then there is one empty spot to the right of it. The rightmost 3 elements are populated 3,4,5. The element 3 is marked with an arrow that says "head" and the element 6 is marked with an arrow that says "tail".

Notice that the tail's index is less than the head's index!

Your job is to implement a RingBufferQueue class. Your class should have the following public methods:

Method Description
void enqueue(int elem) Enqueues elem if the queue has room; throws an error if queue is full
int dequeue() Returns and removes the element at the front of the queue; throws a string exception if queue is empty
int peek() Returns element at the front of the queue; throws a string exception if queue is empty
bool isEmpty() Returns true if queue is empty and false otherwise
bool isFull() Returns true if queue is full and false otherwise
int size() Returns number of elements in the queue

You are welcome to add any private methods or fields that are necessary.

It can be hard to know where to start when writing an entire class, so we've given you this breakdown:

  1. Start by identifying the private fields you will need, then write the constructor and destructor to initialize the fields and do any cleanup, if necessary. Questions to think about:
    • Is it easier to keep track of head and tail (as pictured in the diagrams above)? Or would it be better to track head and size?
  2. Write isEmpty(), isFull(), size(), and peek(). Questions to think about:
    • Which of these methods can be const? In general, how do you know when a method can be const?
  3. Write enqueue() and dequeue(). Remember to handle error conditions! Questions to think about:
    • Can you call the methods from part 2 to reduce redundancy?
    • Would using modular math help with wrapping around?
    • Should either of these methods be const?
  4. Finally, deal with ostream insertion!

If you want more practice with writing classes, think about how you could modify this class to implement a double-ended queue. (A double-ended queue, or deque, is one where you can enqueue and dequeue from either the front or the back).

Solution

RingBufferQueue.h

#pragma once 

#include <iostream>
class RBQueue {
public:
	/* Constructs a new empty queue. */
	RBQueue();
	
	~RBQueue();
 	
 	/* Returns true if the queue contains no elements. */
 	bool isEmpty() const;
	
	/* Returns true if no additional elements can be enqueued. */
	bool isFull() const;

	/* Returns number of elements in queue. */
	int size() const;

	/* Adds the given element to back of queue. */
	void enqueue(int elem);

	/*
	* Removes and returns the front element from the queue
	* Throws a string exception if the queue is empty.
	*/
	int dequeue();

	/*
	* Returns the front element from the queue without removing it.
	* Throws a string exception if the queue is empty.
	*/
	int peek() const;

private:
	// member variables (instance variables / fields)
	int* _elements;
	int _capacity;
	int _numUsed;
	int _head;
	
	// by listing this here as a "friend", it can access the private member variables
	friend std::ostream& operator <<(std::ostream& out, const RBQueue& queue);
};

RingBufferQueue.cpp

#include "RingBufferQueue.h"

const int kDefaultCapacity = 10;

using namespace std;

RBQueue::RBQueue() {
	_capacity = kDefaultCapacity;
	_elements = new int[_capacity];
	_head = 0;
	_numUsed = 0;
}

RBQueue::~RBQueue() {
	delete[] _elements;
}

bool RBQueue::isEmpty() const {
	return _numUsed == 0;
}

bool RBQueue::isFull() const {
	return _numUsed == _capacity;
}

int RBQueue::size() const {
	return _numUsed;
}

int RBQueue::peek() const {
	if (isEmpty()) {
 		error("Can't peek from an empty queue!");
	}
 	
 	return _elements[_head];
}

int RBQueue::dequeue() {
	if (isEmpty()) {
		error("Can't dequeue from an empty queue!");
	}
	
	int front = _elements[_head];
	_head = (_head + 1) % _capacity;
	_numUsed--;
	return front;
}

void RBQueue::enqueue(int elem) {
	if (isFull()) {
		error("Can't enqueue to already full queue!");
	}

	int tail = (_head + _numUsed) % _capacity;
	_elements[tail] = elem;
	_numUsed++;
}

ostream& operator <<(ostream& out, const RBQueue& queue) {
	out << "{";
 
	if (!queue.isEmpty()) {
		// we can access the inner '_elements' member variable because
		// this operator is declared as a 'friend' of the queue class
		out << queue._elements[queue._head];

		for (int i = 1; i < queue._numUsed; i++) {
			int index = (queue._head + i) % queue._capacity;
			out << ", " << queue._elements[index];
		}
	}
 
	out << "}";
	return out;
}

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

Note: we won't be getting to memory and pointers until the lecture on Thursday, 7/21, but this is a great continuation to the RBQ problem if you're interested.

Topics: Classes, dynamic memory allocation, pointers

Remember our good friend the RingBufferQueue from one problem ago? 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()) {
        error("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;
}

2) 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.

3) Creative Destruction

Topics: Constructors and Destructors

Constructors and destructors are unusual functions in that they're called automatically in many contexts and usually aren't written explicitly. To help build an intuition for when constructors and destructors are called, trace through the execution of this program and list all times when a constructor or destructor is called.

/* Prints the elements of a stack from the bottom of the stack up to the top
 * of the stack. To do this, we transfer the elements from the stack to a
 * second stack (reversing the order of the elements), then print out the
 * contents of that stack.
*/
void printStack(Stack<int> toPrint) {
	Stack<int> temp;
	while (!toPrint.isEmpty()) {
		temp.push(toPrint.pop());
	}

	while (!temp.isEmpty()) {
		cout << temp.pop() << endl;
	}
}

int main() {
	Stack<int> elems;
	for (int i = 0; i < 10; i++) {
		elems.push(i);
	}
 
	printStack(elems);
	return 0;
}
Solution

The ordering is as follows:

  • A constructor is called when elem is declared in main.
  • A constructor is then called to set toPrint equal to a copy of elem.
  • A constructor is then called to initialize the temp variable in printStack.
  • When printStack exits, a destructor is called to clean up the temp variable.
  • Also when printStack exits, a destructor is called to clean up the toPrint variable.
  • When main exits, a destructor is called to clean up the elem variable.

4) 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.

5) 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 

6) Some Pointers on Cats

Topics: Pointer tracing and memory diagrams

Trace through the following function and draw the program’s memory at the designated spot. Indicate which variables are on the stack and which are on the heap, and indicate orphaned memory. Indicate with a question mark (?) memory that we don’t know the values of.

struct Lion {
	int roar;
	int *meow;
	int purr[2];
};

struct Savanna {
	int giraffe;
	Lion cat;
	Lion *kitten;
};

Lion *explore(Savanna *prairie) {
	Lion *leader = &(prairie->cat);
	leader->meow = new int;
	*(leader->meow) = 2;
	prairie = new Savanna;
	prairie->cat.roar = 6;
	prairie->kitten = leader;
	prairie->kitten->roar = 8;
	prairie->kitten->meow = &(prairie->kitten->purr[1]);
	leader->purr[0] = 4;
	return leader;
}

void kittens() {
	Savanna *habitat = new Savanna[3];
	habitat[1].giraffe = 3;
	habitat[1].kitten = nullptr;
	habitat[0] = habitat[1];
	habitat[2].kitten = explore(habitat);
	habitat[2].kitten->roar = 4;
	
	// DRAW THE MEMORY AS IT LOOKS HERE
}
Solution

Orphaned memory (memory on the heap that we no longer have access to but that was not freed) is represented with dotted lines. For a full walkthrough of the solution, check out: https://tinyurl.com/CatsPointers.

Memory diagram, more detailed description to come soon