CS 70

Applying Theory: Two Designs for an IntVector Class

Let's consider two designs for a class like C++'s std::vector, which we'll call IntVector.

Design 1

In the first design, the class contains the following code:

Vector Encoding

 private:
    // Data members
    int* arr_;              // Contains the elements of the vector
    size_t capacity_;       // Actual size of underlying array
    size_t size_;           // Number of elements actually stored

Indexing Operation (operator[])

int& IntVector::operator[](size_t index) {
    assert(index < size_);              // Detect improper use

    return arr_[index];
}

The pop_front() Function

int IntVector::pop_front() {
    assert(size_ > 0);                  // Detect improper use

    int firstVal = arr_[0];             // Save value to return

    // From front to back, shift items over
    for (size_t i = 1; i < size_; ++i) {
        arr_[i - 1] = arr_[i];
    }

    --size_;
    downsizeIfNeeded();

    return firstVal;
}
  • push_front() is coded analogously to pop_front().
  • Notice that the iterator is encoded as a pointer into the underlying primitive array.

Design 2

The second design is the same as the one you used for CoordVector in the previous assignment, and also the approach used in the provided IntVector code for this assignment. Recall that the technique, known as a circular buffer, requires us to go to some effort in the indexing operation to incorporate an offset and wrap around (handled by logicalToPhysical in the previous assignment), but we do not need to shift items when we pop_front() or push_front().

Questions

(When logged in, completion status appears here.)