Walking through the basics of C++ by building the standard vector class from scratch (P3)

Previous: Walking through the basics of C++ by building the standard vector class from scratch (P2)

Milestone 2: A container that can shrink and expand in size automatically and upon request

Let's first layout our objectives from this milestone:

• Vector's size and capacity can expand and shrink
• We can push elements to the end of the vector.
• We can pop elements from the end of the vector.

We need to highlight something crucial here related to capacity and size operations, the vector class have 2 kinds of functions:

• Functions that manipulate the size of the vector - it only expands the memory attached to the vector but it doesn't shrink it even if a smaller size is requested.
• Functions that manipulate the capacity only, thus, it directly changes the capacity of the memory attached to the vector without losing any existing data, it doesn't allow shrinking the memory to a capacity that is less than the size of data.

Here are the functions that we will add to the vector interface:

class Vector {
public:
    // constructors and destructors
    // ...

    // accessors
	// ...

    // Capacity
    // ...
    void shrink_to_fit();
    void reserve(size_t);

    // Modifiers
	void push_back(double);
	void pop_back();
    void resize(size_t);
    void resize(size_t, double);
	// ...

private:
    // ...
};

Let's detail exactly what our new functions are supposed to accomplish:

reserve

void reserve( size_t new_cap );

• Increase the capacity of the vector (the total number of elements that the vector can hold without requiring reallocation) to a value that's greater or equal to new_cap. If new_cap is greater than the current capacity(), new storage is allocated, otherwise the function does nothing.
• reserve() does not change the size of the vector.
• After a call to reserve(), insertions will not trigger reallocation unless the insertion would make the size of the vector greater than the value of capacity().

Implementation

void Vector::reserve(size_t new_cap) {
    if (new_cap == 0 || new_cap <= capacity())
        return;

    double* temp = new double[new_cap];
    std::copy(_data, _data + capacity(), temp);
    delete[] _data;
    _data = temp;
    _capacity = new_cap;
}

shrink_to_fit

void shrink_to_fit();

• Requests the removal of unused capacity.

Implementation

void Vector::shrink_to_fit() {
    if (_capacity == _size)
        return;

    double* temp = new double[_size];
    std::copy(_data, _data + _size, temp);
    delete[] _data;
    _data = temp;
    _capacity = _size;
}

resize

(1) void resize(size_t new_size);
(2) void resize(size_t new_size, double val);

• Resizes the container to contain new_size elements, does nothing if new_size == size().
• If the current size is greater than new_size, the container is reduced to its first new_size elements. This case doesn't trigger memory reallocation.
• If the current size is less than new_size which triggers reallocation, (1) additional default-inserted elements are appended. (2) additional copies of val are appended.

Implementation

void Vector::resize(size_t new_size) {
    if (_size == new_size)
        return;
    else if (_size > new_size)
        _size = new_size;
    else {
        double* temp = new double[new_size];
        std::copy(_data, _data + _size, temp);
        delete[] _data;
        _data = temp;

        for (size_t i = _size; i < new_size; i++)
        {
            *(_data + i) = {};  // fill with default value
        }

        _capacity = _size = new_size;
    }
}

• void Vector::resize(size_t new_size, double val) will have the same exact implementation, except that instead of filling extra space with default value, you will fill it val.

push_back

void push_back(double val);

• Appends the given element val to the end of the container.
• If size() == capacity(), we will increase the capacity to be twice the size.

Implementation

Now that we have the memory expansion facility implemented, implementing this function should be a piece of cake!

void Vector::push_back(double val) {
    if (_size == _capacity)
        reserve(2*_size);

    *(_data+_size) = val;
    ++_size;
}

pop_back

void pop_back()

• Removes the last element of the container.
• Calling pop_back on an empty container results in undefined behavior.
• Note that, pop_back doesn't actually delete the last element, rather, it just decrement the size only! So, the element is still accessible if you use operator[] but an error is thrown if you used at due to a proper bound checking.

Capacity is not affected by popping elements

Implementation

void Vector::pop_back() {
    --_size;
}

Next: Implementing Vector Operations