4
\$\begingroup\$

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;
}
\$\endgroup\$
9
  • \$\begingroup\$ Wow, I just found out that std::vector also has insert and erase methods. What an ineffective methods they are. Consider the example from cpp reference - erase odd numbers from vector of integers - doing it using erase method in a loop makes it an O(n²) algorithm where it really can be solved in O(n). You better avoid insert/erase on a vector as much as you can, or at least always think about it before you use them. \$\endgroup\$
    – slepic
    May 4, 2021 at 5:07
  • 1
    \$\begingroup\$ Btw I have recently read this post codereview.stackexchange.com/questions/260004/… and there is a brilliant answer which touches the topic of beginners implementing standard template containers (and other things), I suggest you read it. On other hand, as a learning excersise, I suggest you try to implement the "remove odds from vector" algorithm I mentioned above without using the erase method. It might give you a little insight on why those methods are not a good pick and why you might consider using a different container if you need to insert/erase often. \$\endgroup\$
    – slepic
    May 4, 2021 at 5:37
  • \$\begingroup\$ @slepic "You better avoid insert/erase on a vector as much as you can" IIRC, insertion and deletion on a vector often turn out to be faster than those on a list, as the advantage of continuous storage dominates the moving of elements, so std::vector should still be the default choice, as mentioned at the end of this answer. The cppreference example for erase, of course, is just a demonstration of its usage; actually removing elements of a vector calls for the erase-remove idiom. \$\endgroup\$
    – L. F.
    May 4, 2021 at 6:42
  • 1
    \$\begingroup\$ Hi @slimmsady - looks like a problem here if (_size >= _capacity) { _capacity *= GROWTH_FACTOR; .. it assumes that GROWTH_FACTOR will be sufficient to make capacity bigger than size .. Your ctor does the right thing, but resize doesn't \$\endgroup\$
    – Mr R
    May 4, 2021 at 6:47
  • 1
    \$\begingroup\$ Worth a read: lokiastari.com/series Look at the series on vector. \$\endgroup\$ May 4, 2021 at 21:53

3 Answers 3

3
\$\begingroup\$
  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.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the detailed answer. Currently I am using assert statements to check bounds. But yes, this will fail for other exceptions. Still not added proper operator overloading, but that will handle [] and <<. I have checked _resize() and it works fine. SHRINK_FACTOR just checks if _size is a quarter of _capacity, array is still shrinked by GROWTH_FACTOR. Seems to be an issue with naming. \$\endgroup\$
    – slimmsady
    May 5, 2021 at 2:52
  • \$\begingroup\$ For the point 7, my stupid mind thought that if I pass by reference and change it from the calling function afterwards, then the instance variables will also be changed. I am still little confused about how to handle default initialization when I don't have an idea about the constructor of the data type of T. Please point me towards an article or guide. \$\endgroup\$
    – slimmsady
    May 5, 2021 at 2:52
  • \$\begingroup\$ Elaborated on what you wanted. The cppreference page I linked also has a bit of playing around with the allocator. They curently use the allocator directly too much. Fixed that by properly going through allocator_traits. \$\endgroup\$ May 5, 2021 at 13:55
1
\$\begingroup\$
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:

\$\endgroup\$
4
  • \$\begingroup\$ I am still not comfortable with smart pointers. Will definitely update this code once I am decent at using them. Is there any difference between const and constexpr in this context? Also, thanks for pointing me towards Catch2. Will definitely try it. \$\endgroup\$
    – slimmsady
    May 5, 2021 at 3:02
  • 1
    \$\begingroup\$ In 2011, the catch phrase was "constexpr is the new static const". While a variable declared const with global lifetime might be useful for array bounds and template arguments, depending on whether it was a suitable type and the initializer was a constant expression, writing constexpr will ensure it and give you an error if the initializer is not know at compile time. \$\endgroup\$
    – JDługosz
    May 5, 2021 at 14:01
  • 1
    \$\begingroup\$ Post C++11, the right way of teaching is smart pointers first, and new/delete is an advanced topic. It's easy: just use make_unique instead of new, and forget about having to delete manually. \$\endgroup\$
    – JDługosz
    May 5, 2021 at 14:03
  • 1
    \$\begingroup\$ BTW, something like a vector (I called it vararray) was my go-to collection from the early days of C++, before STL existed, long before standardization. I had several versions over the years. \$\endgroup\$
    – JDługosz
    May 5, 2021 at 14:05
1
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Why can't you put constants in a header? It's only a ODR violation if they are changed between different translation units, but that's true for everything in the header. \$\endgroup\$
    – JDługosz
    May 6, 2021 at 14:30
  • \$\begingroup\$ @JDługosz yeah, I got it mixed with the C language. In C++, const int also implies constexpr, so it's fine. I'll remove that part \$\endgroup\$ May 6, 2021 at 16:56
  • \$\begingroup\$ In C, you just need to use static with the const. Whether or not it's constexpr depends on the initializer. Even for complex types, const has internal linkage by default in C++. \$\endgroup\$
    – JDługosz
    May 6, 2021 at 22:26
  • \$\begingroup\$ Yes, but OP doesn't have static there. Const references have external linkage iirc. \$\endgroup\$ May 7, 2021 at 5:49
  • 1
    \$\begingroup\$ @JDługosz, yes I know C++ is different in this respect. I simply got it mixed up with C since I don't often create global const variables in headers :) C would require a static which OP didn't have. Thank you for pointing out. \$\endgroup\$ May 7, 2021 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.