A First Draft of the CoordVector
Class
We're not quite ready to dive into solving mazes just yet. When we do tackle that problem, we'll find that we need a way to represent a list of coordinates. (For example, the solution to a maze is a list of coordinates that you would follow to get from the start to the end.)
In practical code, you might just use std::vector<Coord>
to represent such a list, as it is an array-like class that can grow and shrink as needed. But in CS 70, we don't just want to use data structures, we want to build them ourselves. So in this part of the assignment, you'll build your own version of a vector class that can hold Coord
objects.
Hay! I thought vectors were just things like velocities and accelerations.
Mathematically speaking, any one-dimensional collection of values, however huge, is a vector. Thus it's not an unreasonable term for an array-like data structure.
So we're making our own version of
std::vector
?Sort of! We'll start simple with a fixed maximum size, then improve it in later parts. We'll also stick to CS 70–style naming conventions (the standard library likes
snake_case
, but we prefercamelCase
).
Starting Point: The CoordVector
Interface
We're providing you with a complete header file (coordvector.hpp
) to get started.
/**
* \file coordvector.hpp
* \author CS 70 Provided Code
* \brief Declares the CoordVector class for managing an array of 2D coordinates
*
*/
#ifndef COORDVECTOR_HPP_INCLUDED
#define COORDVECTOR_HPP_INCLUDED
#include "coord.hpp"
#include <utility> // technicall unnecessary, but makes CPPLINT happy, :-P
/**
* \class CoordVector
* \brief A simple vector-like class for storing Coord objects
* \details The CoordVector class provides a simple array-like structure for
* storing Coord objects. It supports basic operations such as adding
* and removing elements, accessing elements by index, and checking
* the size of the vector.
* \note This implementation uses a fixed-size array with a maximum capacity.
* It does not support dynamic resizing. (Yet!)
*/
class CoordVector {
public:
/**
* \brief Default constructor creates an empty vector
*/
CoordVector();
/**
* \brief Constructs a coord vector with an optional
* initial number of default-constructed elements
* \param initialSize Number of elements to initially create.
* \post The vector is created with the specified number of
* default-constructed Coord elements
*/
explicit CoordVector(size_t initialSize);
// Disable copy and assignment for simplicity
CoordVector(const CoordVector&) = delete;
CoordVector& operator=(const CoordVector&) = delete;
/**
* \brief Returns the number of elements in the vector
* \returns Number of elements in the vector
*/
size_t size() const;
/**
* \brief Checks if the vector is empty
* \returns True if the vector is empty, false otherwise
*/
bool isEmpty() const;
/**
* \brief Adds a new element to the end of the vector
* \param coord The coordinate to add
* \throws An exception if the vector is full (for now!)
*/
void pushBack(const Coord& coord);
/**
* \brief Removes the last element from the vector
* \throws An exception if the vector is empty
*/
void popBack();
/**
* \brief Returns a const reference to the last element in the
* vector
* \returns A const reference to the last element in the vector
* \throws An exception if the vector is empty
*/
const Coord& back() const;
/**
* \brief Returns a (mutable) reference to the element at the
* specified index
* \param index The index of the element to access
* \returns A reference to the element at the specified index
* that allows the element to be modified
* \note Allows Python-style negative indexing. This version
* requires the target object to be non-const.
* \throws std::out_of_range if index is out of bounds
*/
Coord& operator[](ptrdiff_t index);
/**
* \brief Returns a (const) reference to the element at the
* specified index
* \param index The index of the element to access
* \returns A constant reference to the element at the
* specified index
* \note Allows Python-style negative indexing. This version
* is for const objects.
* \throws std::out_of_range if index is out of bounds
*/
const Coord& operator[](ptrdiff_t index) const;
/**
* \brief Removes all elements from the vector
*/
void clear();
private:
static constexpr size_t MAX_SIZE = 256; // Arbitrary fixed maximum size
Coord data_[MAX_SIZE]; // The underlying array
size_t size_; // Current number of elements
// Helper to map user-provided index to physical array index
size_t logicalToPhysical(ptrdiff_t index) const;
};
#endif // COORDVECTOR_HPP_INCLUDED
That looks like a lot of member functions!
Don't worry—most of them are quite short.
The interface looks larger than it really is because of all the comments.
And the implementation is straightforward, so it's not as scary as it looks.
I see
logicalToPhysical
in the private section. What's that about?That's a helper function that handles index conversion, including support for Python-style negative indexing where
-1
means the last element.
Understanding the Interface
Before implementing anything, let's understand what this class provides:
- Storage: A fixed-size array of
Coord
objects (up to 256 elements). - Size tracking: Keeps track of how many elements are actually in use.
- Stack-like operations:
pushBack()
,popBack()
, andback()
. - Array-like access:
operator[]
for accessing elements by index. - Python-style indexing: Negative indices count from the end (-1 is the last element).
Notice that the copy constructor and assignment operator are disabled to keep things simpler for now—we don't need to worry about deep copying.
Meh. 256 seems arbitrary.
It is! But it'll do for now. Starting with a fixed size lets us focus on the core functionality without the complexity of dynamic memory management… yet.
Your Task: Create the CoordVector
Class
Step 1: Create the Header File
Create a new file called coordvector.hpp
in your maze
directory and paste the code given above into it. (You can just click the code snippet to copy it to your clipboard.)
Getting filenames right in assignments really matters since we have autograders that expect specific filenames. It's
coordvector.hpp
, all lowercase, no spaces, dashes, or underscores.
Step 2: Create the Implementation File
Create a new file called coordvector.cpp
and add the necessary includes:
#include "coordvector.hpp"
#include "coord.hpp"
#include <stdexcept> // for std::out_of_range
#include <cstddef> // for ptrdiff_t
Step 3: Implement the Constructors
The class has two constructors:
- A constructor that takes an initial size.
- A default constructor that creates an empty vector (equivalent to calling the first constructor with an initial size of 0).
The first constructor should
- Set
size_
to the provided initial size. - Throw an exception if the initial size exceeds
MAX_SIZE
.- Hint: The syntax for throwing an appropriate exception is
throw std::length_error("Oh noes!");
— you can (and should) choose your own (better) error message.
- Hint: The syntax for throwing an appropriate exception is
Note that the array data_
will be default-initialized automatically with default-initialized Coord
objects. (We don't care that some of them are unused; they just sit there doing nothing. The default constructor initializes them to (-1, -1), which will help detect if you somehow access a location you didn't store a value into.)
Also, remember that any initialization you do in C++ constructors should use a member-initialization list if you possibly can.
Quick reminder: In the implementation file, every function needs to be prefixed with
CoordVector::
to indicate that it's a member function of theCoordVector
class.
We could write the second constructor from scratch, but there is a better way! C++ supports constructor delegation, where one constructor can call another constructor in the same class. This technique is a great way to avoid duplicating code.
Here, we want the default constructor to just delegate to the first constructor with an initial size of 0. The syntax for delegation is that instead of listing member initializers after the colon, you write a single call to another constructor in the same class. Because this usage might be a bit unfamiliar, we'll just give you the code for the default constructor:
CoordVector::CoordVector() : CoordVector(0) {
// Nothing else to do; we've delegated all the work to the other
// constructor.
}
Meh. We've written the word
CoordVector
three times in a row. That's not crazy at all.It is what it is.
Step 4: Implement the Helper Function
Here's the key insight: many of our functions need to validate and convert indices. Rather than duplicate this logic everywhere, we use a helper function that takes a signed logical index (which can be negative just like in Python, with -1
meaning the last element) and converts it to an unsigned physical index (which is always non-negative).
Here's what this function needs to do:
- If the index is negative, add
size_
to it to convert it to a positive index. - Now that the index is non-negative, it's convenient to transfer the index value to a
size_t
variable for further checks (which avoids annoying compiler warnings about comparing signed and unsigned values). - If the resulting value is out-of-bounds, throw an exception (i.e.,
throw std::out_of_range("Index out of range")
). Remember thatsize_
is the number of valid elements, so valid indices are0
throughsize_-1
. - Return the valid physical index.
Why
ptrdiff_t
instead ofint
for the negative index?ptrdiff_t
is the standard type for signed array indices in C++. It's guaranteed to be large enough to represent the difference between any two memory addresses, which makes it safer for indexing.
Step 5: Implement the Remaining Functions
Now implement the rest of the member functions.
Important: Use logicalToPhysical()
every place you access the data_
array (i.e., write data_[logicalToPhysical(index)]
). Doing so will ensure that all index handling is consistent and correct, and also make future changes easier.
Here are some hints for each function:
size()
andisEmpty()
- These should be one-liners.
pushBack()
- Check for overflow, increment
size_
, then add the element. popBack()
- Check for underflow, then decrement
size_
. back()
- Return the last element (hint: use
logicalToPhysical(-1)
). operator[]
- Use
logicalToPhysical()
to get the actual array index.operator[]
may seem like a very strange name for a function, but implementing it allows you to use the familiar square-bracket syntax (e.g.,vec[0]
).- There are two basically identical implementations here: one for
const
objects and one for non-const
objects. Because we uselogicalToPhysical()
, the code should be a simple one-liner, so the code duplication isn't too bad.
clear()
- Reset the size to 0.
Wait, in
pushBack()
, should we increment size before or after adding the element?Because we're going to use
logicalToPhysical()
with-1
, the size needs to be correct when we call it. So incrementsize_
first, then add the element at the new last position.Meh. Do we actually have to throw exceptions like it says in the comments? Can't we just say going out of bounds is against the rules and if you do it's undefined behavior and you get what you deserve?
People often think that C++ is inherently dangerous because guardrails are optional. But it's often a choice. Given a choice between nanoseconds of extra speed and catching bugs early, the latter is usually the better choice. So yes, we require the exceptions as specified and the testcases will check for them.
Step 6: Update the Makefile
One of the existing files, solver.cpp
is going to need to use your new CoordVector
class. It has a #include "coordvector.hpp"
line already, but it's commented out. Uncomment that line.
Add rules to compile coordvector.o
and build coordvector-test
:
coordvector.o: coordvector.cpp coordvector.hpp coord.hpp
$(CXX) -c $(CXXFLAGS) coordvector.cpp
coordvector-test.o: coordvector-test.cpp coordvector.hpp coord.hpp
$(CXX) -c $(CXXFLAGS) coordvector-test.cpp
coordvector-test: coordvector-test.o coordvector.o coord.o
$(CXX) -o $@ $^ -ltestinglogger
Also, because you uncommented the #include "coordvector.hpp"
line in solver.cpp
, its dependencies have changed. You can work out what they are by hand or just run clang++ -MM solver.cpp
to see what it says. Update the Makefile accordingly.
Finally, don't forget to add coordvector-test
to your TARGETS
variable!
Step 7: Test Your Implementation
Once everything compiles, run the tests:
make coordvector-test
./coordvector-test
The test file exercises all the member functions, including edge cases such as empty vectors and negative indexing. It should produce output similar to
CoordVector basics passed!
CoordVector pushBack loop passed!
All tests passed! Summary of affirmations:
----
Fails / Total Issue
0 / 24 [CoordVector basics]
0 / 602 [CoordVector pushBack loop]
(Note that some tests are currently commented out; we'll enable them later.)
Step 8: Fix any Issues
If any tests fail, debug your implementation. Using print statements (i.e., std::cerr << ...
) is probably the simplest way to figure out what's going wrong, but remember that valgrind
can also help you find memory errors.
Helpful Hints
Why logicalToPhysical()
Matters
You might be tempted to directly access data_[index]
in your operator[] implementation. Don't! Always use logicalToPhysical()
, which
- Handles negative indices correctly.
- Performs bounds checking.
- Keeps all the index logic in one place.
- Will make future improvements much easier. (Trust us on this!).
Testing Edge Cases
Make sure your implementation handles
- Empty vectors (size 0).
- Single-element vectors.
- Full vectors (at maximum capacity).
- Negative indices such as
-1
,-2
, etc. - Out-of-bounds access (should throw exceptions).
Common Mistakes
- Forgetting to check for overflow in
pushBack()
. - Forgetting to check for underflow in
popBack()
andback()
. - Not using
logicalToPhysical()
consistently. - Off-by-one errors with size and indices.
Meh. This feels like a lot of boilerplate for what's basically an array.
That's the point! By building it yourself, you can understand what
std::vector
does behind the scenes, and also how Python's “lists” and Java'sArrayList
work. Admittedly, this version has some limitations, but we'll fix them shortly.What limitations?
The big one: It can only hold 256 elements. What if we need more? Stay tuned…
I need MORE! I always need MORE! I'm totally staying tuned!
I just know it's going to involve
new
anddelete
.
Why CoordVector
Isn't an Array of Pointers
In this week's lesson, we discussed how to make an array that can have empty slots by using an array of pointers. Why don't we do that here?
Gah! That
Cow**
stuff made my head spin!
As usual, you can skip this “deeper dive” section, but read on if you're curious and want to peer down this particular rabbit hole.
There are a few good reasons why the homework code is different from what's in the lesson:
Coord
objects are small and cheap to construct and copy.- In fact, on our system, because a
Coord
is made from twoint16_t
s, it's only 4 bytes total, whereas a pointer on our system is a 64-bit value, which is 8 bytes. So storing noCoord
at all (nullptr
) would cost 8 bytes, and having a pointer to aCoord
on the heap would cost at least 12 bytes (8 for the pointer plus 4 for theCoord
, plus whatever bookkeeping overhead the heap allocator needs). So using pointers would be a big waste of space. - While we might be concerned about the wasted effort of default-constructing unused
Cow
s in the lesson, here the cost of default-constructing unusedCoord
s that are just (-1, -1) is negligible. (It's likely one processor instruction to set twoint16_t
s to -1.)
- In fact, on our system, because a
- It's more faithful to the behavior of
std::vector
(and C++'s primitive arrays) where all the elements are in contiguous memory—whether it'sCoord
s orint
s orElephant
s, they're all sitting right next to each other in memory in the standard C++ array-like data structures. - Avoiding arrays of pointers makes everything easier to think about and implement.
- And finally, if the assignment was exactly like the lesson, you wouldn't gain as much new experience by doing it.
I see. But I did like how it worked in the lesson. It made a good point about not needing to default-construct a bunch of
Cow
s that we might not use. And now it seems like you're saying thatstd::vector<Cow>
wouldn't work the way we did it in the lesson, so it is going to waste time and space with unusedCow
s.
The truth is, the real industrial-strength C++ std::vector
implementation uses some pretty sophisticated techniques to avoid unnecessary work. When you make a std::vector<Cow>
, it really uses an array of Cow
s on the heap, but it keeps track of which ones are actually initialized and only constructs and destructs them as needed. To do that, it can't actually use new Cow[n]
to allocate the array, because that would default-construct all of them. It uses more primitive memory allocation mechanisms that give it more flexibility.
Gah! So there's more machinery underneath
new
anddelete
? I don't think I want to know about that.Meh. Me neither.
We won't go any further down this rabbit hole! Let's focus on our
CoordVector
which just uses an array ofCoord
s on the heap, allocated withnew
in the normal way. No need to make things more complicated than we have to!
(When logged in, completion status appears here.)