Section 5. Class Design and Dynamic Memory Allocation

Each 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

Class Design

Problem One: Random Bag Review

The very first container class we implemented was the random bag, which supported two operations:

• add, which adds an element to the random bag, and
• removeRandom, which chooses a random element from the bag and returns it.

Below is the code for the RandomBag class. First, RandomBag.h:

#pragma once

#include "vector.h"

class RandomBag {
public:
    void add(int value);
    int removeRandom();

    int size() const;
    bool isEmpty() const;

private:
    Vector<int> elems;
};

Next, RandomBag.cpp:

#include "RandomBag.h"
#include "random.h"

int RandomBag::size() const {
    return elems.size();
}

bool RandomBag::isEmpty() const {
    return size() == 0;
}

void RandomBag::add(int value) {
    elems += value;
}

int RandomBag::removeRandom() {
    if (isEmpty()) {
        error("That which is not cannot be!");
    }

    int index = randomInteger(0, size() - 1);
    int result = elems[index];

    elems.remove(index);
    return result;
}

Let’s begin by reviewing some aspects of this code.

1. What do the public and private keywords mean in RandomBag.h?

   Solution

   The public keyword indicates that the member functions listed underneath it are publicly accessible by anyone using the RandomBag class. This essentially means that they form the public in-terface for the class.

   The private keyword indicates that the data members listed underneath it are private and only accessible by the class itself. This means that those data members are part of the private implementation of the class and aren’t something that clients should be touching.

   ---

2. What does the :: notation mean in C++?

   Solution

   It’s the scope resolution operator. It’s used to indicate what logical part of the program a given name belongs to. The case we’ll primarily see it used is in the context of defining member func-tions in a .cpp file, where we need to indicate that the functions we’re implementing are actually member functions of a class, not freestanding functions.

   ---

3. What does the const keyword that appears in the declarations of the RandomBag::size() and RandomBag::isEmpty() member functions mean?

   Solution

   It indicates that those member functions aren’t allowed to change the data members of the class. Only const member functions can be called on an object when in a function that accepts an object of that class by const reference.

   ---

Problem Two: Rational Decision Making

Consider the following partially-implemented Fraction class which can be used to model rational numbers in C++, functionality that is not built-in to the language. If you're interested in the actual source code of the public and private helper methods, feel free to refer to the section starter code.

class Fraction {
public:
    /* Creates the fraction num / denom. If neither is specified,
     * the fraction defaults to 0. If only the numerator is specified,
     * the fraction will be equal to that value exactly (the
     * denominator will be 1). For example:
     *
     * Fraction f;          // f == 0      (0/1)
     * Fraction f = 137;    // f == 137    (137/1)
     * Fraction f(137, 42); // f == 137/42
     */
    Fraction(int num = 0, int denom = 1);
    
    /* Access numerator and denominator. */
    int numerator() const;
    int denominator() const;
    
    /* Adds the given value to this fraction. For example, if this
     * fraction is 1/2 and the other fraction is 1/4, this fraction
     * ends up equal to 3/4.
     */
    void add(const Fraction& f);
    
    /* Multiplies this fraction by the other fraction. For example,
     * if this fraction is 1/2 and the other fraction is 1/4, this
     * fraction ends up equal to 1/8.
     */
    void multiply(const Fraction& f);
    
    /* Evaluates the ratio represented by this fraction. */
    double asDecimal() const;
    
private:
    /* The actual numerator and denominator. */
    int num;
    int den;
    
    /* Reduces the fraction to its simplest form. */
    void reduce();
};

1. The constructor for the Fraction type uses two default arguments. Read the comments on the constructor. Given how the constructor is defined and given its default arguments, why does writing Fraction f = 137 produce the fraction 137 / 1?

   Solution

   The constructor takes in two arguments, but has the first default to 0 and the second to 1. Therefore, if only a single argument is provided, C++ will assume the second is 1. This means that Fraction f = 137 is treated as if the first argument is 137 and the second argument is 1, so we get the fraction $\frac{137}{1} = 137\text.$

   ---

2. The function named add could mean one of two different things. First, it could take two fractions and add them together, producing a third fraction. Second, it could take two fractions and modify the first fraction by adding in the second. In the case of our Fraction class, it's the latter. There are two ways you can infer this just by looking at the signature of the function add, without even needing to read the comments. What are they?

   Solution

   The first "tell" is that add has a void return type and thus doesn't return anything. Therefore, it couldn't return a new Fraction.

   The second "tell" is that add is not marked const. This means that the function will modify the Fraction object it's called on. (Otherwise, the function would be marked const.)

   ---

3. Add a function named reciprocal to the Fraction type that returns the reciprocal of the fraction. If the fraction is zero, call error to report that the reciprocal can't be taken.

   Solution

   First, we'll add this to the .h file in the public section of the class.

   /* Returns the reciprocal of this fraction. If the fraction is zero, this
    * operation is not defined, and the function calls error().
    */
   Fraction reciprocal() const;
   

   Next, we'll add this to the .cpp file:

   Fraction Fraction::reciprocal() const {
       if (numerator() == 0) {
           error("I can't divide by zero. (Maybe you can, though?)");
       }
   
       return Fraction(denominator(), numerator());
   }
   

   ---

4. Add a function divide to the Fraction type. Analogously to multiply, the divide function should accept as input another Fraction and modify the receiver by dividing its value by that of the other Fraction.

   If the other fraction is equal to zero, call error().

   Solution

   First, let's add this to our .h file:

   /* Divides this fraction by the fraction given in the parameter. If that
    * fraction is zero, calls error().
    */
   void divide(const Fraction& rhs);
   

   Next, the implementation, which goes in the .cpp file:

   void Fraction::divide(const Fraction& rhs) {
       multiply(rhs.reciprocal());
   }
   

   ---

Problem Three: The Great Circle of Life

Write a class named Circle that stores information about a circle. Your class must implement the following public interface:

class Circle {
public:
    /* Constructs a new circle with the given radius. */
    Circle(double r); 
    
    /* Returns the radius as a real number. */
    double radius() const;
       
    /* Returns the distance around the circle. */
    double circumference() const;
    
    /* Returns the area occupied by the circle. */
    double area() const; 
    
    /* Returns a string representation such as "Circle{radius=2.5}" */
    string toString() const;
    
private:
    /* Up to you! */
};

Feel free to add whatever private member variables or helper functions seem most appropriate. In C++, $\pi$ is given by the constant M_PI defined in the <cmath> header. As usual, make sure to report errors if you're given invalid inputs.

/* File: Circle.h
 *
 * Defines the Circle type, which represents a circle.
 */
#pragma once

#include <string>

class Circle {
public:
    /* Constructs a new circle with the given radius. */
    Circle(double r); 
    
    /* Returns the radius as a real number. */
    double radius() const;
        
    /* Returns the distance around the circle. */
    double circumference() const;
    
    /* Returns the area occupied by the circle. */
    double area() const;

    
    /* Returns a string representation such as "Circle{radius=2.5}".
     *
     * Note the use of std::string here. In a header file, strings go by
     * this longer, more formal name.
     */
    std::string toString() const;
    
private:
    double r; // Radius of the circle
};

/* File: Circle.cpp
 *
 * Implementation of functions that manipulate a circle.
 */
#include "Circle.h"
#include <cmath>
using namespace std;

/* Stash the radius for later use. */
Circle::Circle(double radius) {
    r = radius;
}

/* Return the stashed value. */
double Circle::radius() const{
    return r;
}

/* Circumference of the circle is 2pi r. */
double Circle::circumference() const{
    return 2 * M_PI * r;
}


/* Area of a circle is pi * r^2. */
double Circle::area() const{
    return M_PI * r * r;
}

/* Give a nice pretty representation of our circle. */
string Circle::toString() const{
    return "Circle{radius=" + to_string(r) + "}";
}

Problem Four: Creative Destruction

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 are 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;
}

Problem Five: Speeding Up Random Bags

Now that you’re a bit more acclimated to the syntax, let’s look at this code in a bit more detail.

First, some notes. The Vector type’s += operator takes time O(1) to run. The square brackets on the Vector type select a single element out of its underlying array, which takes time O(1) as well.

The Vector::remove() function, on the other hand, takes time proportional to the distance between the element being removed and the last element of the Vector. The reason for this is that whenever a gap opens up in the Vector, it has to shift all the elements after the gap down one spot. As a result, removing from the very end of a Vector is quite fast – it runs in time O(1) – but removing from the very front of a Vector takes time O(n).

1. Look at the implementation of our RandomBag::removeRandom function. What is its worst-case time complexity? How about its best-case time complexity? Its average-case time complexity?

   Solution

   The worst-case time complexity of an operation is O(n), which happens when we remove the very first element from the Vector. Our best-case complexity is O(1) if we remove from the end of the Vector. On average, the runtime is O(n), since on average n/2 elements need to get shifted over.

   ---

2. Based on your answer to the previous part of this question, what is the worst-case time complexity of removing all the elements of an n-element RandomBag? What’s the best-case time complexity? How about its average case?

   Solution

   The worst-case complexity would be O(n²), which would happen if we get very unlucky and always remove the very first element of the Vector, making the total work done roughly equal to(n-1) + (n-2) + (n-3) + … + 2 + 1 = O(n²). The best-case complexity would be O(n), which happens if we always remove the last element of the Vector (n × O(1) = O(n). The average-casetime complexity is O(n²), since on average each removal does O(n) work and we do it n times.

   ---

3. In the preceding discussion, we mentioned that removing the very last element of a Vector is much more efficient that removing an element closer to the middle. Rewrite the member function RandomBag::removeRandom so that it always runs in worst-case O(1) time.

   Solution

   There a couple of different ways to do this. One option is based on the insight that removing from the very end a Vector is an O(1)-time operation, so if we remove the last element of the Vector at each step we’ll get an O(1) worst-case bound. The problem is that the last element is decidedly not a random element, since it always holds the last thing added. However, we can easily fix this by simply choosing a random element of the array and swapping it with the one at the end. This makes the element at the end randomly-chosen, which we still need to do, but makes deletions run in time O(1). Here’s some code for this.

   int RandomBag::removeRandom() {
       if (isEmpty()) {
           error("That which is not cannot be!");
       }
       int index = randomInteger(0, size() - 1);
       int result = elems[index];
       swap(elems[index], elems[elems.size() - 1]);
       elems.remove(elems.size() - 1);
       return result;
   }
   
   

   ---

4. The Stack and Queue types each have peek member functions that let you see what element would be removed next without actually removing anything. How might you write a member function RandomBag::peek that works in the same way? Make sure that the answer you give back is actually consistent with what gets removed next and that calling the member function multiple times without any intervening additions always gives the same answer.

   Solution

   Part of the challenge here is that we need to find a way to determine what the next element to be removed is going to be, but we have to do so in way that gives consistent results from call to call.

   There are many different ways we can do this. One option, which guarantees a uniformly-random selection of elements from the RandomBag, is to store an extra variable keeping track of the index of the nextelement to remove. Every time we add or remove an element, we’ll update this value to hold a new random value. Here’s one way we can do this. First, the changes in the header:

   class RandomBag {
   public:
       void add(int value);
       int removeRandom();
       int peek() const; // <-- Don't forget to make this const!
       int size() const;
       bool isEmpty() const;
   private:
       Vector<int> elems;
       int nextIndex;
   };
   

   Next, the changes to the .cpp file. We’ve moved a lot of the logic out of RandomBag::removeRandom into RandomBag::peek in order to unify the code paths and avoid duplicating our logic.

   void RandomBag::add(int value) {
       elems += value;
   
       /* Stage a new element for removal. */
       nextIndex = randomInteger(0, elems.size() - 1);
   }
   int RandomBag::peek() const {
       if (isEmpty()) {
           error("That which is not cannot be!");
       }
       return elems[nextIndex];
   }
   int RandomBag::removeRandom() {
       int result = peek();
   
       swap(elems[nextIndex], elems[elems.size() - 1]);
       elems.remove(elems.size() - 1);
   
       /* Stage a new element for removal. */
       nextIndex = randomInteger(0, elems.size() - 1);
       return result;
   }
   

   ---

Problem Six: The Two-Stack Queue

In lecture, we saw how to build a stack using only the built-in C++ language features. How might we implement a queue? There are many ways to do this, but one particularly clever and elegant one involves nothing more than two stacks.

Here's how this will work. We'll maintain two stacks of elements, an in stack and an out stack. To enqueue an element, we just push it onto the in stack. For example, here's what happens if we enqueue the values 1, 2, 3, and 4:

To dequeue from this queue, we need to access the item that's currently at the bottom of the in stack. To address this, we'll pop all the items from the in stack and push them into the out stack. As you can see, this makes the items accessible in the order in which they were enqueued.

Now, we can dequeue by popping off the out stack. And more generally, as long as the out stack is nonempty, we dequeue items by popping from it. We can do that even as more items are getting enqueued into the queue.

The general rule works like this:

• To enqueue, push onto the in stack.
• To dequeue, if the out stack is not empty, pop from the top of that stack. Otherwise, pop all the items from the in stack, moving them to the out stack, and then pop from the out stack.

Although this might seem somewhat inefficient, it turns out that this is a very fast way to implement a stack. Every item gets pushed and popped at most twice, so the average cost of each operation is $O(1)$.

Using this idea, implement a class called TwoStackQueue that represents a queue made from two stacks. You should support enqueue and dequeue, as well as functions to determine the size of the queue and tell whether the queue is empty.

#pragma once
#include "stack.h"

class TwoStackQueue {
public:
    /* No constructor or destructor is needed, since we don't do
     * any memory management of our own.
     */
    
    /* Adds a new item to the back of the queue. */
    void enqueue(int value);
    
    /* Removes and returns the front item of the queue. If the queue is
     * empty, this calls error().
     */
    int dequeue();
    
    /* Returns how many items are in the queue. */
    int size() const;
    
    /* Returns whether the queue is empty. */
    bool isEmpty() const;

private:
    /* Our 'in' and 'out' stacks. */
    Stack<int> in, out;
};

#include "TwoStackQueue.h"
#include "error.h"
using namespace std;

void TwoStackQueue::enqueue(int value) {
    /* Just add to the `in` stack. */
    in.push(value);
}

int TwoStackQueue::dequeue() {
    /* If we're empty, there's nothing to dequeue. */
    if (isEmpty()) {
        error("Sorry, we're fresh out of that!");
    }
    
    /* Make sure the out stack has something in it. */
    if (out.isEmpty()) {
        while (!in.isEmpty()) {
            out.push(in.pop());
        }
    }
    
    /* Take from the out stack, which is definitely not empty now. */
    return out.pop();
}

int TwoStackQueue::size() const {
    /* Add up how many items are in both stacks. */
    return in.size() + out.size();
}

bool TwoStackQueue::isEmpty() const {
    /* It's nice how size handles all this for us. */
    return size() == 0;
}

Dynamic Memory Allocation

Problem Seven: Pointed Points about Pointers

Pointers to arrays are different in many ways from Vector or Map in how they interact with pass-by-value and the = operator. As a reminder, copying a pointer just makes another pointer to the same objects. It does not copy the objects being pointed at.

To better understand how they work, trace through the following program. What is its output? Identify any memory leaks.

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;
}

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

Problem Eight: Cleaning Up Your Messes

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.

int main() {
    int* baratheon = new int[3];
    int* targaryen = new int[5];

    baratheon = targaryen;
    targaryen = baratheon;

    delete[] baratheon;
    delete[] targaryen;

    return 0;
}

int main() {
    int* stark     = new int[6];
    int* lannister = new int[3];

    delete[] stark;
    stark = lannister;

    delete[] stark;

    return 0;
}

int main() {
    int* tyrell = new int[137];
    int* arryn  = tyrell;

    delete[] tyrell;
    delete[] arryn;

    return 0;
}

Problem Nine: Put a Ring (Buffer Queue) On It

In an earlier problem, you saw how to build a queue out of two stacks. In this problem, you'll see an alternative way to build a queue using a structure called a ring buffer.

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:

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

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:

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:

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 methods that do the following:

• Enqueue an element if the queue isn't full.
• Dequeue an element if one exists.
• Look at the front element of the queue, if one exists.
• Return whether the queue is empty.
• Return how many elements are 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 methods that check for emptiness, report the size of the queue, and look at the first item in the queue. 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 other methods you've written to reduce redundancy? Would using modular math help with wrapping around? Should either of these methods be const?

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. More on that later.)

#pragma once

class RingBufferQueue {
public:
    /* Creates a new, empty, RingBufferQueue. */
    RingBufferQueue();
    
    /* Cleans up all memory used by the RingBufferQueue. */
    ~RingBufferQueue();
    
    /* Enqueues an item. If there is no space left, this function calls
     * error().
     */
    void enqueue(int value);
    
    /* Looks at, but does not remove, the first element of the queue.
     * If the queue is empty, calls error().
     */
    int peek() const;
    
    /* Removes and returns the first element of the queue. If the queue
     * is empty, calls error().
     */
    int dequeue();
    
    /* Returns how many elements are in the queue. */
    int size() const;
    
    /* Returns whether the queue is empty. */
    bool isEmpty() const;
    
private:
    int* elems;         // Pointer to array of elements
    int  allocatedSize; // Number of slots in that array
    int  logicalSize;   // How many are used
    int  head;          // Head position; see above diagrams    
};

#include "RingBufferQueue.h"
#include "error.h"
using namespace std;

/* Capacity of a RingBufferQueue. */
const int kNumSlots = 5; // Matches diagram above

RingBufferQueue::RingBufferQueue() {
    /* Create our array. */
    elems = new int[kNumSlots];
    allocatedSize = kNumSlots;
    
    /* We're logically empty at this point; no items have been added. */
    logicalSize = 0;
    
    /* Head begins at the beginning - though it in principle could go
     * anywhere within the array.
     */
    head = 0;
}

RingBufferQueue::~RingBufferQueue() {
    delete[] elems;
}

/* Adds a value right after the last position. */
void RingBufferQueue::enqueue(int value) {
    /* If we're at full capacity, there's no room left. */
    if (size() == allocatedSize) {
        error("Already packed like sardines in here!");
    }
    
    /* Determine where this element goes. If we didn't have any wraparound,
     * we would go at position head + size(). However, we have to account
     * for the fact that this might walk off the end of the array, in which
     * case we need to wrap around to the beginning. The modulus operator
     * is our friend here. By computing (head + size()) % allocatedSize,
     * one of the two things happen:
     *
     *   1. If head + size() < allocatedSize, then the remainder when we
     *      do the division is head + size().
     *   2. If head + size() >= allocatedSize, then the remainder of the
     *      division will be what we get when we subtract out as many
     *      copies of allocatedSize as we can.
     *
     * More generally, modding by an array size essentially says "wrap me
     * around to the right position."
     */
    elems[(head + size()) % allocatedSize] = value;
    logicalSize++;
}

int RingBufferQueue::peek() const {
    /* Make sure there's something here to return. */
    if (isEmpty()) {
        error("Nothing to see here folks, move along.");
    }
    
    /* Look at the position given by the head. */
    return elems[head];
}

int RingBufferQueue::dequeue() {
    /* This also does error-checking for us. Nifty! */
    int result = peek();
    
    /* The head needs to move forward a step, possibly wrapping around. Above,
     * we did this using the mod operator. Just to show another strategy, we'll
     * use if statements here.
     */
    head++;
    if (head == allocatedSize) head = 0;
    
    /* As usual, we don't actually get rid of the integer we're removing. We
     * just pretend it doesn't exist.
     */
    logicalSize--;
        
    return result;
}

int RingBufferQueue::size() const {
    return logicalSize; // Number of slots used
}

bool RingBufferQueue::isEmpty() const {
    return size() == 0;
}

Problem Ten: Pack Stacks For Low Slack

Some applications, like the two-stack queue from above, require the use of two stacks. Let's take a minute to review our implementation of a stack from lecture. We maintain an array of slots, then store the items in the stack such that items on the bottom of the stack use low indices, while items on top of the stack get higher indices. The unused slots are then purely "slack space" so we have some room to put items during future push and pop operations.

To reduce the amount of slack space used by the two stacks, we can combine the two stacks together into a single array. The first stack will grow from the left to the right, and the second stack will grow from the right to the left, as shown here:

Using this insight, implement the following class TwoStacks, which represents two separate stacks.

class TwoStacks {
public:
    /* Creates two new empty stacks. */
    TwoStacks();
    
    /* Cleans up the memory used by the stacks. */
    ~TwoStacks();
    
    /* Pushes an item onto a stack. If there is no space left, these function call
     * error() to report an error.
     */
    void pushFirst(int value);
    void pushSecond(int value);
    
    /* Pops and item from one of the stacks. If the relevant stack is empty, these
     * functions call error() to report an error.
     */
    int popFirst();
    int popSecond();
    
    /* Looks at, but does not remove, the top of one of the stacks. These functions
     * call error() to report an error.
     */
    int peekFirst() const;
    int peekSecond() const;
    
    /* Returns the size of the relevant stack. */
    int sizeFirst() const;
    int sizeSecond() const;
    
    /* Returns whether the relevant stacks are empty. */
    bool isFirstEmpty() const;
    bool isSecondEmpty() const;
    
private:
    /* Up to you! */
};

#pragma once

class TwoStacks {
public:
    /* Creates two new empty stacks. */
    TwoStacks();
    
    /* Cleans up the memory used by the stacks. */
    ~TwoStacks();
    
    /* Pushes an item onto a stack. If there is no space left, these function call
     * error() to report an error.
     */
    void pushFirst(int value);
    void pushSecond(int value);
    
    /* Pops and item from one of the stacks. If the relevant stack is empty, these
     * functions call error() to report an error.
     */
    int popFirst();
    int popSecond();
    
    /* Looks at, but does not remove, the top of one of the stacks. These functions
     * call error() to report an error.
     */
    int peekFirst() const;
    int peekSecond() const;
    
    /* Returns the size of the relevant stack. */
    int sizeFirst() const;
    int sizeSecond() const;
    
    /* Returns whether the relevant stacks are empty. */
    bool isFirstEmpty() const;
    bool isSecondEmpty() const;
    
private:
    int* elems;             // Elements array
    int  allocatedSize;     // Number of slots in that array
    int  logicalSizeFirst;  // Number of elements in the first stack
    int  logicalSizeSecond; // Number of elements in the second stack
    
    /* Unified implementation of push/pop/peek to avoid code duplication.
     *
     * These functions take by reference which logicalSize variable is being
     * used, a base index (0 for the first stack, allocatedSize - 1 for the
     * second), and a direction (+1 for the first stack since we grow up,
     * -1 for the second stack since we grow up).
     */
    void push(int& logicalSize, int baseIndex, int direction, int value);
    int  peek(int  logicalSize, int baseIndex, int direction) const;
    int  pop (int& logicalSize, int baseIndex, int direction);
};

#include "TwoStacks.h"
#include "error.h"
using namespace std;

const int kInitialSize = 10; // Matching the images from above

TwoStacks::TwoStacks() {
    /* Form our array. */
    elems = new int[kInitialSize];
    allocatedSize = kInitialSize;
    
    /* No elements, initially. */
    logicalSizeFirst = logicalSizeSecond = 0;
}

TwoStacks::~TwoStacks() {
    /* Reclaim memory. */
    delete[] elems;
}

/* Most functions forward to the relevant helpers. */
void TwoStacks::pushFirst(int value) {
    push(logicalSizeFirst, 0, +1, value);
}

void TwoStacks::pushSecond(int value) {
    push(logicalSizeSecond, allocatedSize - 1, -1, value);
}

int TwoStacks::peekFirst() const {
    return peek(logicalSizeFirst, 0, +1);
}

int TwoStacks::peekSecond() const {
    return peek(logicalSizeSecond, allocatedSize - 1, -1);
}

int TwoStacks::popFirst() {
    return pop(logicalSizeFirst, 0, +1);
}

int TwoStacks::popSecond() {
    return pop(logicalSizeSecond, allocatedSize - 1, -1);
}

/* These ones just return the proper fields. */
int TwoStacks::sizeFirst() const {
    return logicalSizeFirst;
}

int TwoStacks::sizeSecond() const {
    return logicalSizeSecond;
}

bool TwoStacks::isFirstEmpty() const {
    return sizeFirst() == 0;
}

bool TwoStacks::isSecondEmpty() const {
    return sizeSecond() == 0;
}

/* Unified push implementation. */
void TwoStacks::push(int& logicalSize, int baseIndex, int direction, int value) {
    /* Make sure there's room. */
    if (sizeFirst() + sizeSecond() == allocatedSize) {
        error("Two stacks, one array, zero remaining space.");
    }
    
    /* Place the item at the next position. To find that spot, begin at the
     * base index, then move logicalSize steps in the correct direction.
     */
    elems[baseIndex + logicalSize * direction] = value;
    logicalSize++;
}

/* Unified peek implementation. */
int TwoStacks::peek(int logicalSize, int baseIndex, int direction) const {
    /* See if there even is something to peek at. */
    if (logicalSize == 0) {
        error("Two stacks, one array, zero elements in that stack.");
    }
    
    /* Return the item at the next position. To find this, start at the
     * base index, then move forward (logicalSize - 1) steps in the
     * correct direction.
     */
    return elems[baseIndex + (logicalSize - 1) * direction];
}

/* Unified pop implementation. */
int TwoStacks::pop(int& logicalSize, int baseIndex, int direction) {
    /* Also does bounds-checking. Nice! */
    int result = peek(logicalSize, baseIndex, direction);
    
    /* Decrement the logical size. This has the effect of pulling us toward
     * the sides of the array.
     */
    logicalSize--;
    
    return result;
}

Problem Eleven: Implementing a Grid

Let's begin with a refresher on pointers and arrays. An int is an actual, honest-to-goodness integer. An int* is a pointer that points at an array of ints. You can think of an int*, in a sense, as pointing at a 1D array of integers.

Now for something new: an int** is a pointer that points at an array of int*s. In other words, it's a pointer that points at an array of other pointers, which in turn point to arrays of integers.

1. Draw what memory looks like after executing the following C++ code. Identify any memory leaks, uninitialized integers, and uninitialized pointers.

   int** khulna = new int*[3];
   khulna[0] = new int[2];
   khulna[2] = new int[3];
   
   khulna[0][0] = 0;
   
   delete[] khulna[2];
   delete[] khulna;
   

   Solution

   Here's an animation tracing out each step of the process.

   

   At the end, there's a memory leak: the array of two items we allocated in the second line is never cleaned up. Also, its second element is never initialized.

   ---

We've used the Grid<int> type extensively this quarter. Now, you'll see one way of implementing a basic version of a grid type that holds integers. Conceptually, we think of a Grid as a 2D array. Internally, one way of implementing a Grid of integers uses an int**, where memory looks like this:

That is, the top-level int** points to an array of int*s, one for each row in the grid. The int*s in that array then point to the contents of each row.

2. Using your newfound knowledge of int** and arrays of pointers, finish the implementation of the OurGrid type given below.

   class OurGrid {
   public:
       /* Creates a new grid of size numRows x numCols. If either numRows or
        * numCols is negative, this calls error(). Initially, all values in the
        * Grid are set to 0.
        */
       OurGrid(int numRows, int numCols);
       
       /* Cleans up all memory allocated by our grid. */
       ~OurGrid();
       
       /* Returns whether the given point is in bounds. */
       bool inBounds(int row, int col) const;
       
       /* Returns the value at the given (row, col) index. If the index is out of
        * bounds, calls error().
        */
       int get(int row, int col) const;
       
       /* Sets the value at (row, col) to the specified value. If the index is out
        * of bounds, calls error().
        */
       void set(int row, int col, int value);
       
       /* Returns the number of rows or columns in the grid, respectively. */
       int numRows() const;
       int numCols() const;
   
   private:
       /* Pointer to an array of pointers. Each of those pointers then points to
        * the contents of a row.
        */
       int** elems;
       
       // The rest is up to you!
   };
   

   Solution

   First, our header file:

   #pragma once
   
   class OurGrid {
   public:
       /* Creates a new grid of size numRows x numCols. If either numRows or
        * numCols is negative, this calls error(). Initially, all values in the
        * Grid are set to 0.
        */
       OurGrid(int numRows, int numCols);
       
       /* Cleans up all memory allocated by our grid. */
       ~OurGrid();
       
       /* Returns whether the given point is in bounds. */
       bool inBounds(int row, int col) const;
       
       /* Returns the value at the given (row, col) index. If the index is out of
        * bounds, calls error().
        */
       int get(int row, int col) const;
       
       /* Sets the value at (row, col) to the specified value. If the index is out
        * of bounds, calls error().
        */
       void set(int row, int col, int value);
       
       /* Returns the number of rows or columns in the grid, respectively. */
       int numRows() const;
       int numCols() const;
   
   private:
       /* Pointer to an array of pointers. Each of those pointers then points to
        * the contents of a row.
        */
       int** elems;
       
       int rows; // Number of rows
       int cols; // Number of columns
   };
   

   Now, our .cpp file.

   #include "OurGrid.h"
   #include "error.h"
   using namespace std;
   
   OurGrid::OurGrid(int numRows, int numCols) {
       /* Validate input. */
       if (numRows < 0 || numCols < 0) {
           error("Don't be so negative!");
       }
       
       /* Stash rows and columns for later. */
       rows = numRows;
       cols = numCols;
       
       /* Construct the array of pointers to rows. */
       elems = new int*[numRows];
       
       /* For each row, construct an array of the contents of that row. */
       for (int row = 0; row < numRows; row++) {
           elems[row] = new int[numCols];
       }
       
       /* Fill everything with 0s. */
       for (int row = 0; row < numRows; row++) {
           for (int col = 0; col < numCols; col++) {
               set(row, col, 0);
           }
       }
   }
   
   /* Destructor needs to clear all the arrays for the rows, then the top-level
    * array of pointers to rows.
    */
   OurGrid::~OurGrid() {
       for (int row = 0; row < numRows(); row++) {
           delete[] elems[row];
       }
       
       /* Now, clear the top-level array. */
       delete[] elems;
   }
   
   /* Bounds-checking. */
   bool OurGrid::inBounds(int row, int col) const {
       return row >= 0 && col >= 0 && row < numRows() && col < numCols();
   }
   
   /* Return grid size. */
   int OurGrid::numRows() const {
       return rows;
   }
   int OurGrid::numCols() const {
       return cols;
   }
   
   /* Retrieve element at a given position. */
   int OurGrid::get(int row, int col) const {
       if (!inBounds(row, col)) {
           error("Not a good time to think outside the box.");
       }
       
       /* elems is the pointer to the array of pointers.
        * elems[row] is a pointer to the elements of row number row.
        * elems[row][col] is the element we want.
        */
       return elems[row][col];
   }
   
   /* Set a value at a given position. */
   void OurGrid::set(int row, int col, int value) {
       if (!inBounds(row, col)) {
           error("Can't put something nowhere.");
       }
       
       elems[row][col] = value;
   }
   

   ---