Errors while creating a dynamic array in a vector class for project

Question

I am running into a few errors, a memory error with the back function and failing to pass many of the tests that the program checks for.

I need to get this code working, which is in Vector.cpp:

#include <stdexcept>
#include "Vector.h"

using namespace std;

void Vector::grow()
{
    const int GROWER = 1.6;
    capacity = capacity * GROWER;
}

Vector::Vector()
{
    capacity = CHUNK;
    n_elems = 0;
    data_ptr = new int[capacity];
    for (size_t i = 0; i < capacity; i++)
    {
        data_ptr[i] = 0;
    }
}

Vector::Vector(const Vector& v)
{
    n_elems = 0;
    capacity = v.capacity;
    data_ptr = new int[capacity];
    for (size_t i = 0; i < capacity; i++)
    {
        data_ptr[i] = v.data_ptr[i];
        n_elems++;
    }
}

Vector& Vector::operator=(const Vector& v)
{
    capacity = v.capacity;
    data_ptr = new int[capacity];
    for (size_t i = 0; i < capacity; i++)
    {
        data_ptr[i] = v.data_ptr[i];
    }
    return *this;
}

Vector::~Vector()
{
    delete[] data_ptr;
}

int Vector::front() const
{
    if (n_elems != 0)
    {
        return data_ptr[0];
    }
    else
    {
        return -1;
        throw range_error("Range Error");
    }
}

int Vector::back() const
{
    if (n_elems != 0)
    {
        return data_ptr[n_elems - 1];
    }
    else
    {
        throw range_error("Range Error");
    }
}

int Vector::at(size_t pos) const
{
    if (pos >= 0 && pos < capacity)
    {
        return data_ptr[pos];
    }
    else
    {
        throw range_error("Range Error");
    }
}

size_t Vector::size() const
{
    return n_elems;
}

bool Vector::empty() const
{
    if (n_elems == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int& Vector::operator[](size_t pos)
{
    return data_ptr[pos];
}

void Vector::push_back(int item)
{
    grow();
    data_ptr[n_elems - 1] = item;
}

void Vector::pop_back()
{
    if (n_elems >= 0)
    {
        --n_elems;
    }
    else
    {
        throw range_error("Range Error");
    }
}

void Vector::erase(size_t pos)
{
    if (pos >= 0 && pos < capacity)
    {
        for (size_t i = pos; i < capacity; i++)
        {
            data_ptr[i] = data_ptr[i + 1];
        }
        n_elems--;
    }
    else
    {
        throw range_error("Range Error");
    }
}

void Vector::insert(size_t pos, int item)
{
    int moveCount = n_elems - pos;
    grow();
    if (pos >= 0 && pos < capacity)
    {
        for (size_t i = n_elems; i >= 0; i--)
        {
            data_ptr[i] = data_ptr[i - 1];
        }
        data_ptr[pos] = item;
        n_elems++;
    }
    else
    {
        throw range_error("Range Error");
    }
}

void Vector::clear()
{
    n_elems = 0;
}

int* Vector::begin()
{
    if (n_elems == 0)
    {
        return nullptr;
    }
    else
    {
        return data_ptr;
    }
}

int* Vector::end()
{
    if (n_elems == 0)
    {
        return nullptr;
    }
    else
    {
        return (data_ptr + (n_elems - 1));
    }
}

bool Vector::operator==(const Vector& v) const
{
    bool flag = true;
    for (size_t i = 0; i < capacity; i++)
    {
        if (data_ptr[i] == v.data_ptr[i])
        {
            flag = true;
        }
        else
        {
            flag = false;
            break;
        }
    }
    return flag;
}

bool Vector::operator!=(const Vector& v) const
{
    bool flag = true;
    for (size_t i = 0; i < capacity; i++)
    {
        if (data_ptr[i] != v.data_ptr[i])
        {
            flag = true;
        }
        else
        {
            flag = false;
            break;
        }
    }
    return flag;
}

To pass these tests, which are located in a file called testVector.cpp:

#include "Vector.h"
#include "test.h"
#include <stdexcept>
using namespace std;

int main() {
    // Test exceptions
    Vector v;
    throw_(v.at(0), range_error);
    throw_(v.pop_back(), range_error);
    throw_(v.erase(0), range_error);
    throw_(v.front(), range_error);
    throw_(v.back(), range_error);

    // Test adding an element
    v.push_back(1);
    test_(v.size() == 1);
    test_(v.at(0) == 1);
    test_(v[0] == 1);
    test_(v.front() == 1);
    test_(v.back() == 1);
    test_(!v.empty());

    // Add another
    v.push_back(2);
    test_(v.size() == 2);
    test_(v.at(0) == 1);
    test_(v.at(1) == 2);
    test_(v[0] == 1);
    test_(v[1] == 2);
    test_(v.front() == 1);
    test_(v.back() == 2);
    test_(!v.empty());

    // Test iterators
    auto iter = v.begin();
    test_(*iter == 1);
    ++iter;
    test_(*iter == 2);
    ++iter;
    test_(iter == v.end());

    // Test copy and ==
    Vector v2 = v;
    test_(v2.size() == 2);
    test_(v2.at(0) == 1);
    test_(v2.at(1) == 2);
    test_(v2[0] == 1);
    test_(v2[1] == 2);
    test_(v2.front() == 1);
    test_(v2.back() == 2);
    test_(!v2.empty());
    test_(v == v2);

    iter = v2.begin();
    test_(*iter == 1);
    ++iter;
    test_(*iter == 2);
    ++iter;
    test_(iter == v2.end());

    // Test assignment
    Vector v3;
    v3 = v;
    test_(v3.size() == 2);
    test_(v3.at(0) == 1);
    test_(v3.at(1) == 2);
    test_(v3[0] == 1);
    test_(v3[1] == 2);
    test_(v3.front() == 1);
    test_(v3.back() == 2);
    test_(!v3.empty());

    //iter = v3.begin();
    //test_(*iter == 1);
    //++iter;
    //test_(*iter == 2);
    //++iter;
    //test_(iter == v3.end());

    // Test assignment
    v[1] = -2;
    test_(v.back() == -2);
    test_(v.at(1) == -2);
    test_(v[1] == -2);

    // Test pop_back
    v.pop_back();
    test_(v.size() == 1);
    test_(v.front() == 1);
    test_(v.back() == 1);
    test_(v.at(0) == 1);
    test_(v[0] == 1);

    // Test clear and !=
    v.clear();
    test_(v.size() == 0);
    test_(v.empty());
    throw_(v.at(0), range_error);
    throw_(v.pop_back(), range_error);
    throw_(v.erase(0), range_error);
    throw_(v.front(), range_error);
    throw_(v.back(), range_error);
    test_(v != v2);

    // Test erase
    v3.erase(0);
    test_(v3.size() == 1);
    test_(v3.at(0) == 2);
    test_(v3[0] == 2);
    test_(v3.front() == 2);
    test_(v3.back() == 2);

    // Test insert
    //v3.insert(0,1);
    test_(v3.size() == 2);
    test_(v3.at(0) == 1);
    test_(v3[0] == 1);
    test_(v3[1] == 2);
    test_(v3.front() == 1);
    test_(v3.back() == 2);

    // Test grow
    Vector v4;
    for (int i = 1; i <= 10; ++i)
        v4.push_back(i);
    test_(v4.size() == 10);
    test_(v4.front() == 1);
    test_(v4.back() == 10);
    v4.insert(10,11);
    test_(v4.size() == 11);
    test_(v4.front() == 1);
    test_(v4.back() == 11);


    report_();
}

Answer 1

Your'e missing declaration of vector here, but I can surmize its structure. First mistake you doing here:

const int GROWER = 1.6;  
capacity = capacity * GROWER; // it will never change

Reallocation doesn't happen, where it is? You just call upon dietis of Undefined Behaviour.

You either have to make GROWER float or increment size by fixed size. Also it's very unusual for a vector to grow geometrically. And very ineffective to grow on each push_back. Instead you have to have a CAPACITY and ALLOCATED SIZE. Latter may be greater and would grow if push_back would increase capacity outside of its limits. You apparently have a number of elements n_elems there, but you ignore it?

Many of those are doing too much extra work and don't do what they should. Like this could actually be

data_ptr = new int[capacity] {}; // value initialization
//for (size_t i = 0; i < capacity; i++)
//{
//    data_ptr[i] = 0;
//}

Use initialization lists, not side effects. Or you may lose them. Copy constructor also doesn't take in account n_elems of v and may copy garbage, converting it into new elements.

Comparisons simply wrong, because vectors can have different capacity. E.g.

bool Vector::operator==(const Vector& v) const
{
    // check here if either of vectors is empty, 
    // if both are empty, they are equal?
    // if their capacities are unequal, vectors are not equal. Those are shortcuts

    // capacities are same
    for (size_t i = 0; i < capacity; i++ )
        if (data_ptr[i] != v.data_ptr[i])
           return false;

    return true;
}

Answer 2

push_back() and insert() both call grow(), which fails to increase the capacity because GROWER is an int, so 1.6 truncates to 1, and multiplying capacity * 1 doesn't change its value. But even if capacity were increased properly, the data_ptr array is not being re-allocated at all to fit the new capacity.

But even if grow() were working properly, there is no need to call grow() on every insertion of a new element, that defeats the purpose of separating n_elems from capacity to begin with. You should grow the array only when n_elems has reached capacity.

There are many other problems with your class, as well:

• operator= is not testing for self-assignment, and is leaking the allocated memory of the old array. Consider using the copy-swap idiom instead.

• front() does not reach the throw statement when the array is empty.

• at() and erase() are performing bounds checking using capacity instead of n_elems.

• push_back() is inserting the new value at the wrong index, and not incrementing n_elems.

• pop_back() does not throw an error when the array is empty, causing n_elems to decrement below 0, which wraps around to the max positive value of size_t because size_t is unsigned.

• erase() and operator== go out of bounds while iterating the array.

• begin() and end() should not be returning nullptr for an empty array. And end() is returning a pointer to the last element in a non-empty array rather than returning a pointer to 1 past the last element.

• operator== and operator!= do not perform any bounds checking to make sure the 2 vectors have the same same n_elems before iterating their arrays. And they are comparing element values beyond n_elems. Also, operator!= is returning the wrong result.

With that said, try something more like this:

#include <stdexcept>
#include <algorithm>
#include "Vector.h"

void Vector::grow()
{
    static const float GROWER = 1.6f;
    size_t new_capacity = capacity * GROWER;
    if (new_capacity <= capacity)
        throw std::overflow_error("cant grow capacity");
    int *new_data_ptr = new int[new_capacity];
    std::copy(data_ptr, data_ptr + n_elems, new_data_ptr);
    delete[] data_ptr;
    data_ptr = new_data_ptr;
    capacity = new_capacity;
}

Vector::Vector()
{
    capacity = CHUNK;
    n_elems = 0;
    data_ptr = new int[capacity];
}

Vector::Vector(const Vector& v)
{
    capacity = v.capacity;
    n_elems = v.n_elems;
    data_ptr = new int[capacity];
    std::copy(v.begin(), v.end(), data_ptr);
}

Vector& Vector::operator=(const Vector& v)
{
    if (this != &v)
    {
        Vector temp(v);
        std::swap(capacity, temp.capacity);
        std::swap(n_elems, temp.n_elems);
        std::swap(data_ptr, temp.data_ptr);
    }
    return *this;
}

Vector::~Vector()
{
    delete[] data_ptr;
}

int Vector::front() const
{
    if (n_elems == 0)
        throw std::range_error("Range Error");
    return data_ptr[0];
}

int Vector::back() const
{
    if (n_elems == 0)
        throw std::range_error("Range Error");
    return data_ptr[n_elems - 1];
}

int Vector::at(size_t pos) const
{
    if (pos >= n_elems)
        throw std::range_error("Range Error");
    return data_ptr[pos];
}

size_t Vector::size() const
{
    return n_elems;
}

bool Vector::empty() const
{
    return (n_elems == 0);
}

int& Vector::operator[](size_t pos)
{
    return data_ptr[pos];
}

void Vector::push_back(int item)
{
    if (n_elems == capacity)
        grow();
    data_ptr[n_elems] = item;
    ++n_elems;
}

void Vector::pop_back()
{
    if (n_elems == 0)
        throw std::range_error("Range Error");
    --n_elems;
}

void Vector::erase(size_t pos)
{
    if (pos >= n_elems)
        throw std::range_error("Range Error");
    std::copy(data_ptr + pos + 1, data_ptr + n_elems, data_ptr + pos);
    --n_elems;
}

void Vector::insert(size_t pos, int item)
{
    if (pos > n_elems) // insert at end() is OK...
        throw range_error("Range Error");
    if (n_elems == capacity)
        grow();
    std::copy_backward(data_ptr + pos, data_ptr + n_elems, data_ptr + n_elems + 1);
    data_ptr[pos] = item;
    ++n_elems;
}

void Vector::clear()
{
    n_elems = 0;
}

int* Vector::begin()
{
    return data_ptr;
}

int* Vector::end()
{
    return data_ptr + n_elems;
}

bool Vector::operator==(const Vector& v) const
{
    return (n_elems == v.n_elems) && std::equal(v.begin(), v.end(), data_ptr);
}

bool Vector::operator!=(const Vector& v) const
{
    return !(*this == v);
}