Custom Vector Implementation in C++

Question

I am relearning data structures while trying to implement them on my own while also trying to get better at C++ as although I have knowledge of C, OOP is still non-inituitive to me.

In this simple Vector implementation, I double the array size if it becomes equal to the capacity and half it when it becomes less than a quarter of the capacity. I have also added the main() function that I used to test. Please let me know how I can improve it and what other functionalities to add to get better at C++.

#include <iostream>
#include <cassert>

const int MIN_CAPACITY = 16;
const int GROWTH_FACTOR = 2;
const int SHRINK_FACTOR = 4;

template <class T>
class Vector {

private:
    int _size;
    int _capacity;
    T * _data;

    // Check if resize needed. If yes, do accordingly.
    bool resize() {
        bool resized = false;

        if (_size >= _capacity) {
            _capacity *= GROWTH_FACTOR;
            resized = true;
        } else if (_capacity > MIN_CAPACITY &&
                _size <= _capacity / SHRINK_FACTOR) {
            _capacity /= GROWTH_FACTOR;
            resized = true;
        }

        if (resized) {
            T *tmp = _data;
            _data = new T[_capacity];
            std::copy(tmp, tmp+_size, _data);
            delete [] tmp;
        }

        return resized;
    }

public:
    Vector() : _size(0), _capacity(MIN_CAPACITY), _data(new T[MIN_CAPACITY]) {}

    // create vector with given initial size and default value.
    Vector(int n, T default_val) {
        assert (n > 0);

        _size = 0;
        int capacity = MIN_CAPACITY;
        while (capacity < n)
            capacity *= GROWTH_FACTOR;
        _capacity = capacity;
        _data = new T[_capacity];

        while (_size < n)
            _data[++_size] = default_val;
    }


    Vector(const Vector& src) : _size(src._size), _capacity(src._capacity) {
        _data = new T[_capacity];
        std::copy(src._data, src._data + _size, _data);
    }

    ~Vector() {
        delete [] _data;
    }

    int size() const {
        return _size;
    }

    int capacity() const {
        return _capacity;
    }

    void insert(const int index, const T obj) {
        assert(index >= 0 && index <= _size);
        resize();

        for (int i = _size; i > index; --i)
            _data[i] = _data[i-1];

        _data[index] = obj;
        ++_size;
    }

    void push_back(const T obj) {
        insert(_size, obj);
    }

    T erase(const int index) {
        assert(index >= 0 && index < _size);
        resize();

        T tmp = _data[index];
        for (int i = index; i < _size-1; ++i)
            _data[i] = _data[i+1];
        --_size;

        return tmp;
    }

    T pop_back() {
        return erase(_size-1);
    }

    T get(const int index) const {
        assert(index >= 0 && index < _size);
        return _data[index];
    }

    void set(const int index, const T obj) {
        assert(index >= 0 && index < _size);
        _data[index] = obj;
    }

    void print() {
        std::cout << "Size: " << size() << ", Capacity: " <<
                capacity() << std::endl;
        for (int i = 0; i < size(); ++i)
            std::cout << _data[i] << ", ";
        std::cout << std::endl;
    }
};

int main() {
    Vector<int> v;
    v.push_back(1000);
    v.print();
    v.pop_back();
    v.print();

    for (int i = 0; i < 25; ++i)
        v.push_back(i);
    v.print();
    for (int i = 0; i < 10; ++i)
        v.insert(i, i+25);
    v.print();

    Vector<int> v1 = v;

    for (int i = 0; i < 10; ++i)
        std::cout << "Popped " << v.pop_back() << std::endl;
    v.print();
    for (int i = 0; i < 12; ++i)
        std::cout << "Erased " << v.erase(i) << " from index " << i << std::endl;
    v.print();

    std::cout << "Starting element: " << v.get(0) << std::endl;
    std::cout << "Ending element: " << v.get(v.size() - 1) << std::endl;

    v1.print();

    std::cout << "Starting element: " << v1.get(0) << std::endl;
    std::cout << "Ending element: " << v1.get(v1.size() - 1) << std::endl;

    Vector<char> v2(20, 'a');
    v2.print();

    for (int i=0; i < 12; ++i)
        v2.set(i, 'a'+1+i);
    v2.print();

    std::cout << "Starting element: " << v2.get(0) << std::endl;
    std::cout << "Ending element: " << v2.get(v2.size() - 1) << std::endl;

    return 0;
}

Answer 1

1. Your code labors under the assumption that exceptions cannot happen. Unfortunately, they do.

2. You default initialize all your elements on allocation.

   Not only is that potentially a big waste of time, it also might be impossible (compile-error) or flat-out wrong (silently wrong behavior).

   To fix that, separate allocation from constructing the elements.

   By all means, call operator new (the function) to get space, and operator delete (dito) to release it, but use placement-new and explicit dtor invocation to manage object lifetimes. Alternatively, defer to std::allocator, which doubles as a first step to get full allocator-awareness.

3. Your default-ctor allocates memory. Wherever possible, the default-ctor should be trivial, which simplifies especially construction of static instances. Use in-class-initializers on the non-static members as needed.

4. The standard provides a member-function .resize() with somewhat vaguely related semantics. Your variant adjusting the backing-store to what seems needed (soon?) is quite surprising. Did you verify that it actually always does the adjustment you need or want? Because especially how you use it seems a bit arcane. Also, .reserve() should not be forgotten.

   Also, the current code can only adjust by shrinking or growing one step per call.

5. In order to allow for re-use, depending on the underlying memory-allocator, a growth-factor smaller than 2 is recommended.

6. Consider not shrinking at all, unless requested, and then shrinking all the way. That means removing the minimum.

7. Vector::Vector(int n, T default_val) should accept the second argument by constant reference to avoid needless copies.

8. All ctors should delegate allocation to the same function. That would be easier if the default-ctor was trivial and non-allocating.

9. .get() and .set() are curious member-functions. I would expect just operator[]() used for both, maybe accompanied by .at() for bounds-testing.

10. Printing the vector should not be done by a member-function, especially not hard-wired to std::cout. Provide an iterator-interface (begin, end) and potentially a stream-inserter if you must.

Answer 2

const int MIN_CAPACITY = 16;
const int GROWTH_FACTOR = 2;
const int SHRINK_FACTOR = 4;

these should be part of the class, not global variables that affect everything and pollute the namespace when your header is included.

And use constexpr now.

---

_data(new T[MIN_CAPACITY]

No naked new!

Use a unique_ptr<T[]> instead of a bare pointer for _data.

---

           T *tmp = _data;
            _data = new T[_capacity];
            std::copy(tmp, tmp+_size, _data);
            delete [] tmp;

again, using a unique_ptr you won't need to delete manually.
But rather than copying the old vector, you want to move the elements. Consider if T is something that is expensive to copy (like a string) or cannot be duplicated!

I suspect the same for insert and delete as well. Test it with T that has a deleted copy constructor and assignment operators, but does have a move constructor.

---

For testing, try the "Catch2" library:

Answer 3

Constants

const int MIN_CAPACITY = 16;
const int GROWTH_FACTOR = 2;
const int SHRINK_FACTOR = 4;

These are polluting the global scope. I would put them into the class as named constants:

template <class T>
class Vector {
    enum {
        MIN_CAPACITY = 16,
        GROWTH_FACTOR = 2,
        SHRINK_FACTOR = 4,
    };

// ...

operator= and friends.

Your compiler supplied operator= does the wrong thing currently. You definitely want to overload it yourself to do proper copying. Aside from that, you should consider adding a move constructor and a move assignment operator.

get returns by value.

get() should probably return a refence to the element instead of a copy. Aside from being inefficient, it doesn't allow mutating elements after insertion. On that note, many of the arguments you take by value should either be taken by reference, or moved.

Calculating capacity with a loop

The way you calculate capacity in the two-argument constructor with a while loop is confusing and likely inefficient. Either do capacity = n or capacity = n * GROWTH_FACTOR. Either is fine but I would say you don't want to over-allocate in this case.

noexcept

Some of your functions should definitely be noexcept. size(), capacity() are the ones I spot.

Minimal capacity

Allocating memory in default construction seems like a bad idea. A better idea would be to create some buffer inside the vector for a "small vector optimization". Then, you can possibly make that constructor noexcept as well as constexpr.

Use of int

int is often 32 bits wide. This is limiting and it's a better idea to use ptrdiff_t instead.

Misc

I didn't talk about these since others already have, but here are a couple more points. Your functions are not exception safe. That is very important indeed. And the way you use new and delete is just wrong. They default initialize everything. This is very inefficient and limiting. Some objects are just move-only. What you want to do is to allocate raw memory (with allocators, operator new, malloc or however else) and construct/destruct elements on demand.