Section 5. Class Design and Dynamic Memory Allocation

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.

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.

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.

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.

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.

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

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

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 persistoutside the function because you have only changed the copy of the pointer, not the original pointer it-self

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

baratheon = targaryen;

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 baratheon and targaryen 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.

The ordering is as follows:

• A constructor is called when elem is declared in main.
• A constructor is then called to initialize the temp variable in printStack.
• When printStackexits, a destructor is called to clean up the temp variable.
• When main exits, a destructor is called to clean up the elems variable.