Making CoordVector Dynamic

Your maze solver works great on small mazes, but it crashes on larger ones because CoordVector can only hold 256 coordinates. Time to fix that! We'll transform our fixed-size vector into a dynamically sized one that can grow as needed.

The Plan: Three Careful Steps

Rather than trying to do everything at once (a recipe for disaster), we'll proceed in three stages:

1. Dynamic allocation: Replace the fixed array with a heap-allocated array.
2. Add infrastructure: Implement swap() and track capacity.
3. Dynamic resizing: Automatically grow the array when needed.

Each step will compile and pass tests before moving to the next. This way, if something breaks, you know exactly where the problem is.

Your Task, Step 1: From Stack Frame to Heap

First, let's replace our fixed-size array (which typically lived inside a function's stack frame) with a dynamically allocated one. The size will still be fixed for now, but it will live on the heap.

Update the Header File, Phase 1: Eliminate MAX_SIZE

First, in the header coordvector.hpp, replace

static constexpr size_t MAX_SIZE = 256;   // Arbitrary fixed maximum size

with

size_t capacity_ = 256;                   // Capacity of the array

and also do a search-and-replace to change all occurrences of MAX_SIZE to capacity_ in the implementation file (coordvector.cpp). With these small changes, everything should still build and work exactly as before, but now the capacity is stored in a member variable instead of a static constant.

Update the Header File, Phase 2: Change the data_ Data Member

Now for the big change. We're going to replace the fixed-size array with a pointer to a dynamically allocated array. Remember that array operations rely on a pointer to the first element of the array, so we can use a pointer to that first element (on the heap) instead of a fixed array.

So we'll change

Coord data_[MAX_SIZE];                // The underlying array

to

Coord* data_ = nullptr;               // Pointer to dynamically allocated array

Update the Header File, Phase 3: Add a Destructor

One rule with the heap is that every new must be matched with a delete to avoid memory leaks. So we'll need a destructor to clean up the array when the CoordVector is destroyed. So add a destructor declaration in the public section (adding appropriate documentation):

~CoordVector();

Update the Implementation, Phase 1: Revise the Constructors

Our delegating default constructor can stay the same, but we need to update the parameterized constructor to allocate the array on the heap. So in coordvector.cpp, update the parameterized constructor to

CoordVector::CoordVector(size_t initialSize)
    : capacity_{XXXCAPACITYXXX},
      data_{XXXPOINTERXXX},
      size_{initialSize} {
    if (initialSize > capacity_) {
        throw std::overflow_error("Initial size exceeds capacity");
    }
}

This code has placeholders XXXCAPACITYXXX and XXXPOINTERXXX that you'll need to replace with the appropriate expressions.

For XXXCAPACITYXXX, let's just start with our existing fixed capacity of 256. We'll hard code it as a magic number for now because it's just a placeholder that we'll change soon. You can add it as 256 /* FIXME */ to remind yourself to change it later if you like.

For XXXPOINTERXXX, we need to allocate a new array of Coord objects on the heap. The syntax for allocating an array on the heap is new TypeName[arraySize], which will return a pointer to the first element of the array (thus it returns a TypeName*). For example, new int[10] allocates an array of ten integers on the heap and returns an int* pointing to the first element.

Update the Implementation, Phase 2: Implement the Destructor

Now we need to implement the destructor to clean up the array when the CoordVector is destroyed. The syntax for deallocating an array allocated with new is delete[] pointer, where pointer is a pointer to the first element of the array.

Test Step 1

Compile and run the tests:

make coordvector-test
./coordvector-test

Everything should still work exactly as before. If not, debug before continuing!

Your Task, Step 2: Adding Useful Features

One thing that's cool about our switch to having a pointer to a heap-allocated array is that it now becomes incredibly efficient to swap two CoordVector objects. Previously, if we wanted to swap two CoordVectors, we'd have to swap all 256 elements between the two arrays one-by-one. Now we can just swap the pointers and sizes, which is a constant-time operation.

We'll also let users query the current capacity of the vector. Both of these features are present in std::vector, so it's good practice to implement them here, and they'll turn out to be very useful in our later code.

Edit the Header

In the public section of coordvector.hpp, add (with appropriate documentation):

void swap(CoordVector& other);
size_t capacity() const;

Implement the New Functions

At the top of coordvector.cpp, add

#include <utility>  // for std::swap at the top

so that we can use std::swap. This is a very handy utility function that swaps two values of any built-in type, such as integers, pointers, and so on.

Your implementation of swap() should just go through each data member and swap it with the corresponding data member of other. For example, to swap the size_ members, you can write std::swap(size_, other.size_);. Do the same for all three data members, data_, size_, and capacity_.

The capacity() function is straightforward: it just returns the capacity_ member variable.

Update the Test File

In coordvector-test.cpp, we've used the preprocessor to “comment out” the test_swap() function. To enable it, just remove the #if 0 and #endif lines surrounding it. Then uncomment the call to test_swap() in main() as well.

Test Step 2

Rebuild and test:

make coordvector-test
./coordvector-test

The swap test should now pass!

Your Task, Step 3: Dynamic Resizing

Now for the exciting part: making the vector grow automatically! The heart of our dynamic resizing will be a new function called reserve(), which will let us expand the capacity of the vector—when you call reserve(new_capacity), if the capacity is already at least new_capacity, nothing happens; otherwise, we allocate a new array with the requested capacity, copy over the existing elements, and deallocate the old array.

To help with that copying process, we have a special private constructor that takes another CoordVector and a new capacity, and creates a new CoordVector with the specified capacity, copying over the elements from the other vector.

Update the Header to Add the Private Copying Constructor and reserve()

First, add this function to the public section of coordvector.hpp (don't forget the documentation):

void reserve(size_t new_capacity);

And add this special private constructor to the private section of coordvector.hpp:

// Helper copy constructor with specified capacity
CoordVector(const CoordVector& other, size_t new_capacity);

Implement the Private Copying Constructor

You need to implement the private copying constructor in coordvector.cpp. It should create a new CoordVector with the specified capacity, copy over the elements from other (throwing an exception if new_capacity is less than other.size_).

Here are some tips for implementing it:

• Although you can do it directly by hand, it's easier to delegate to the public constructor that takes an initial size. You can do this by using a member-initialization list that calls CoordVector{other.size_}. This will create a default-initialized array of the right capacity and size.
• After delegating to that constructor, you can then copy over the elements from other using a simple loop. Except…

It's super tempting to write the loop as

    // Do NOT do this!
    for (size_t i = 0; i < other.size_; ++i) {
        data_[i] = other.data_[i];
    }

But earlier on we warned you to always use logicalToPhysical() to convert logical indices to physical indices. One way to do that is to just write other_[i] instead of other.data_[i] and use your operator[] (which in turn will use logicalToPhysical()). Or you can just call logicalToPhysical(i) on both sides of the assignment. Either way is fine, as long as you remember to do it!

Implement reserve()

The job of the reserve() function is to ensure that the vector has at least the specified capacity. If the current capacity is already at least new_capacity, it does nothing. Otherwise, it needs to allocate a new array with the requested capacity, copy over the existing elements, and deallocate the old array.

We can do this task easily using the functionality we've already built. Here's the pseudocode:

if new_capacity < size_:
    throw an exception  // we can't shrink the vector
else if new_capacity ≤ capacity_:
    return              // having done nothing
else:
    create a new temporary CoordVector using our private copying constructor, passing *this and new_capacity
    swap *this with the new temporary vector

Update Constructor and pushBack

Update the parameterized constructor to start with a reasonable capacity. Replace the placeholder 256 /* FIXME */ with std::max(initialSize, size_t{1}) or similar code that achieves the same effect. The rule is

if initialSize is 0:
    capacity_ is initialized to 1    // we never want a zero-capacity vector
else:
    capacity_ is initialized to initialSize

(But we can't write an if statement in a member-initialization list, so we need to use an expression that achieves the same effect.)

Using std::max() is probably the most readable approach, but if you choose that option, you'll need to add #include <algorithm> at the top of coordvector.cpp. There are other equally valid and widely-used approaches, including using condition ? true-case : false-case (a.k.a. the ternary operator) to directly replicate the above conditional code, or you can use a simple helper function. But you must do the computation inside the member-initialization list, not in the body of the constructor, because the initialization of data_ depends on capacity_ having the right value.

In the code for pushBack(), replace the line that threw an exception when the vector was full with a call to reserve() to double the capacity instead. That should be the only change you need to make to pushBack(), as the code path after the if continues on and adds the new element.

Add a Public Copy Constructor

Given that we already have a private copying constructor, it's super easy to implement a public copy constructor. Amend the header file to remove the = delete from the copy-constructor declaration, and then implement it in coordvector.cpp by delegating to the private copying constructor with the same size as the other vector. That's it.

Final Testing

Uncomment test_realloc() in the test file (i.e., delete both the #if 0 … #endif lines and uncomment the lines in main) and run all tests:

make coordvector-test
./coordvector-test

The result should look like

CoordVector basics passed!
CoordVector swap passed!
CoordVector pushBack loop passed!
CoordVector reallocation passed!

All tests passed! Summary of affirmations:
----
Fails   / Total Issue
0       / 24    [CoordVector basics]
0       / 5     [CoordVector swap]
0       / 602   [CoordVector pushBack loop]
0       / 801   [CoordVector reallocation]

Now try the big maze:

make
./amaze mazes/maze-91x43.txt

If all is well, it'll work! Your vector now grows dynamically as needed.

valgrind ./coordvector-test

valgrind --leak-check=full ./coordvector-test

(When logged in, completion status appears here.)