CS 70

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.

  • Horse speaking

    Hay! I thought vectors were just things like velocities and accelerations.

  • LHS Cow speaking

    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.

  • Duck speaking

    So we're making our own version of std::vector?

  • LHS Cow speaking

    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 prefer camelCase).

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
  • Hedgehog speaking

    That looks like a lot of member functions!

  • LHS Cow speaking

    Don't worry—most of them are quite short.

  • RHS Cow speaking

    The interface looks larger than it really is because of all the comments.

  • LHS Cow speaking

    And the implementation is straightforward, so it's not as scary as it looks.

  • Cat speaking

    I see logicalToPhysical in the private section. What's that about?

  • LHS Cow speaking

    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(), and back().
  • 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.

  • Goat speaking

    Meh. 256 seems arbitrary.

  • LHS Cow speaking

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

  • RHS Cow speaking

    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:

  1. A constructor that takes an initial size.
  2. 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.

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.

  • LHS Cow speaking

    Quick reminder: In the implementation file, every function needs to be prefixed with CoordVector:: to indicate that it's a member function of the CoordVector 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.
}
  • Goat speaking

    Meh. We've written the word CoordVector three times in a row. That's not crazy at all.

  • Bjarne speaking

    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 that size_ is the number of valid elements, so valid indices are 0 through size_-1.
  • Return the valid physical index.
  • Duck speaking

    Why ptrdiff_t instead of int for the negative index?

  • LHS Cow speaking

    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() and isEmpty()
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 use logicalToPhysical(), the code should be a simple one-liner, so the code duplication isn't too bad.
clear()
Reset the size to 0.
  • Hedgehog speaking

    Wait, in pushBack(), should we increment size before or after adding the element?

  • LHS Cow speaking

    Because we're going to use logicalToPhysical() with -1, the size needs to be correct when we call it. So increment size_ first, then add the element at the new last position.

  • Goat speaking

    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?

  • LHS Cow speaking

    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

  1. Handles negative indices correctly.
  2. Performs bounds checking.
  3. Keeps all the index logic in one place.
  4. 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() and back().
  • Not using logicalToPhysical() consistently.
  • Off-by-one errors with size and indices.
  • Goat speaking

    Meh. This feels like a lot of boilerplate for what's basically an array.

  • LHS Cow speaking

    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's ArrayList work. Admittedly, this version has some limitations, but we'll fix them shortly.

  • Hedgehog speaking

    What limitations?

  • LHS Cow speaking

    The big one: It can only hold 256 elements. What if we need more? Stay tuned…

  • Pig speaking

    I need MORE! I always need MORE! I'm totally staying tuned!

  • Hedgehog speaking

    I just know it's going to involve new and delete.

Why CoordVector Isn't an Array of Pointers

  • Cat speaking

    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?

  • Hedgehog speaking

    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 two int16_ts, it's only 4 bytes total, whereas a pointer on our system is a 64-bit value, which is 8 bytes. So storing no Coord at all (nullptr) would cost 8 bytes, and having a pointer to a Coord on the heap would cost at least 12 bytes (8 for the pointer plus 4 for the Coord, 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 Cows in the lesson, here the cost of default-constructing unused Coords that are just (-1, -1) is negligible. (It's likely one processor instruction to set two int16_ts to -1.)
  • 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's Coords or ints or Elephants, 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.
  • Cat speaking

    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 Cows that we might not use. And now it seems like you're saying that std::vector<Cow> wouldn't work the way we did it in the lesson, so it is going to waste time and space with unused Cows.

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 Cows 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.

  • Hedgehog speaking

    Gah! So there's more machinery underneath new and delete? I don't think I want to know about that.

  • Goat speaking

    Meh. Me neither.

  • LHS Cow speaking

    We won't go any further down this rabbit hole! Let's focus on our CoordVector which just uses an array of Coords on the heap, allocated with new in the normal way. No need to make things more complicated than we have to!

To Complete This Part of the Assignment...

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)