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

Note: In all parts of this question, assume the array has capacity such that it does not need to be upsized or downsized.

Question 1.1

Question 1.1 – IntVector Design 1, Indexing

Look at the code for operator[] in Design 1 for a vector class.

Either by inspection, or by taking an operation counting approach counting the number of accesses to the arr_ array, what is the time complexity of operator[] on a vector of length $$n$$?

Question 1.2

Question 1.2 – IntVector Design 1, pop_front

Look at the code for pop_front in Design 1 for a vector class.

Either by inspection, or by taking an operation counting approach counting the number of accesses to the arr_ array, what is the time complexity of pop_front on a vector of length $$n$$ (assuming no downsizing of the underlying array is needed):

Question 1.3

Question 1.3 – IntVector Design 2, Indexing

Look at the code for operator[] in Design 2 for a vector class.

Either by inspection, or by taking an operation counting approach counting the number of accesses to the arr_ array, what is the time complexity of operator[] on a vector of length $$n$$?

Question 1.4

Question 1.4 – IntVector Design 2, pop_front

Look at the code for pop_front in Design 2 for a vector class.

Either by inspection, or by taking an operation counting approach counting the number of accesses to the arr_ array, what is the time complexity of pop_front on a vector of length $$n$$ (assuming no downsizing of the underlying array is needed):

Question 1.5

Question 1.5 – IntList, Indexing

Now consider your IntList class. It does not have an operator[], but in principle you could write one (without making any changes to the encoding of the list).

Either by inspection, or by taking an operation counting approach counting the number of times we follow a Node* pointer, what is the worst-case time complexity of an implementation of operator[] on a list of length $$n$$?

Question 1.6

Question 1.6 – IntList, pop_front

Consider your code for pop_front in the IntList class.

Either by inspection, or by taking an operation counting approach counting the number of times we follow a Node* pointer, what is the time complexity of an implementation of pop_front on a list of length $$n$$?

(When logged in, completion status appears here.)