4
\$\begingroup\$

Looking forward to get your feedback on my attempt to replicate vector class functionality. Especially I have doubts about copy constructor and resize methods. I think that copy constructor could potentially cause memory leak, but I don't know how to make it better. I implemented two resize methods and they both seem to work, but which is actually better?

#include <iostream>
#include <type_traits>
#include <math.h>

template <typename T>
class Vector {
private:
    T* m_Data;
    size_t m_Size, m_Capacity;
public:
    Vector(size_t cap = 2)
        : m_Size(0), m_Capacity(cap) {
        m_Data = new T[cap];
    }
    
    Vector(size_t size, size_t cap)
        : m_Size(size), m_Capacity(cap) {
        m_Data = new T[cap];
    }

    Vector(const std::initializer_list<T>& il)
        : Vector(il.size(), il.size() * 2) {
        int cnt = 0;
        for (const auto& el : il)
            m_Data[cnt++] = el;
    }
   
    // copy constructor, makes deep copy
    Vector(const Vector& v)
        : m_Size(v.size()), m_Capacity(v.capacity()) {
        m_Data = new T[m_Capacity];
        for (size_t i = 0; i < m_Size; i++) {
            m_Data[i] = v[i];
        }
    }
    
    ~Vector() {
        delete[] m_Data;
    }

//    void resize(size_t newCapacity) {
//        T* newData = new T[newCapacity];
//        m_Size = std::min(m_Size, newCapacity);
//
//        for (size_t i = 0; i < m_Size; i++)
//            newData[i] = std::move(m_Data[i]);
//
//        delete[] m_Data;
//        m_Data = newData;
//        m_Capacity = newCapacity;
//    }
    
    void resize(size_t newCapacity) {
        char* newData = new char[sizeof(T) * newCapacity];
        m_Size = std::min(m_Size, newCapacity);
        
        T* dst = reinterpret_cast<T*>(newData);
        for (size_t i = 0; i < m_Size; i++)
            new (dst + i) T(m_Data[i]);
        
        delete[] m_Data;
        m_Data = reinterpret_cast<T*>(newData);
        m_Capacity = newCapacity;
    }
    

        
    void push_back(const T& n) {
        if (m_Capacity <= m_Size)
            resize(m_Capacity * 2);
    
        m_Data[m_Size++] = n;
    }
    
    void push_back(const T&& n) {
        if (m_Capacity <= m_Size)
            resize(m_Capacity * 2);
    
        m_Data[m_Size++] = std::move(n);
    }
    
    void pop_back() {
        if (m_Size > 0)
            m_Data[--m_Size].~T();
    }

    void clear() {
        for (size_t i = 0; i < m_Size; i++)
            m_Data[i].~T();
        m_Size = 0;
    }
    
    size_t size() const {
        return m_Size;
    }
    
    size_t capacity() const {
        return m_Capacity;
    }
    
    bool empty() const {
        return m_Size == 0;
    }
    
    const T& operator[](size_t index) const {
        if (index >= m_Size)
            throw "Index out of bounds";
        
        return m_Data[index];
    }
    
    T& operator[](size_t index) {
        if (index >= m_Size)
            throw "Index out of bounds";
        
        return m_Data[index];
    }
    
    Vector<T> operator+(const Vector& other) {
        if (m_Size != other.size())
            throw "Vectors are of different size";
        
        Vector<T> v(m_Size);
        for (size_t i = 0; i < m_Size; i++) {
            v.push_back(m_Data[i] + other[i]);
        }
        
        return v;
    }
    
};

template <
typename T,
typename = typename std::enable_if<std::is_arithmetic<T>::value, T>::type>
int norm(const Vector<T> v) {
    int nrm = 0;
    size_t n = v.size();
    
    for (int i = 0; i < n; i++) {
        nrm += v[i]*v[i];
    }
    
    return sqrt(nrm);
}

template <typename T>
std::ostream& operator<<(std::ostream& s, const Vector<T>& v) {
    s << "[";
    size_t n = v.size();
    for (size_t i = 0; i < n; i++) {
        s << v[i] << (i < n - 1 ? ", " : "");
    }
    s << "]";
    return s;
}

int main(int argc, const char * argv[]) {
    Vector<int>* a = new Vector<int> {1, 2, 3, 4, 5};
    Vector<int> b = {5, 4, 3, 2, 6};
    Vector<int> c = b;

    return 0;
}

Thank you.

\$\endgroup\$
3
  • \$\begingroup\$ I don't think that std::vector<T> has operator+ overload. And I don't think that yours is working as you meant it to.... Also iterators are missing. \$\endgroup\$ – slepic Sep 14 '20 at 7:44
  • \$\begingroup\$ I know that, it was part of the assignment. I passed it, but I want to know how to improve it. Thank you for iterators suggestion though. Also, can you elaborate on why you think that operator+ is not working as I mean it to? \$\endgroup\$ – Serghey Hmeli Sep 14 '20 at 8:40
  • 1
    \$\begingroup\$ Aha sorry it works alright. I incorrectly assumed that Vector<T>(size_t) works the same as std::vector<T>(size_t). Which is btw another divergence from standard vector. Another one may be that the container should define member types such as size_type, value_type, reference, pointer, etc. en.cppreference.com/w/cpp/container/vector \$\endgroup\$ – slepic Sep 14 '20 at 8:50
7
\$\begingroup\$

About the copy constructor and resize()

In the copy constructor (and the other constructors as well), you allocate memory using new T[...], but in resize() you allocate memory with new char[sizeof(T) * ...] and then use placement new to copy the old elements. The former is safe, but potentially calls more constructors than expected, the latter has the problem that you can have unused capacity that was never properly initialized, but when you delete it you will call the destructor on all reserved elements.

To be safe and to avoid calling the constructor of T for reserved elements, do the following consistently:

  • Use char *m_Data to keep track of the allocated memory (you could keep it as T *m_Data, but you have to be careful not to never call delete[] m_Data directly)
  • Always use placement new when adding actual elements to the vector
  • Always use "placement delete" when deleting actual elements from the vector

Also, ideally you want to std::move elements during resize(), but that is tricky, especially if T's move constructor can throw exceptions.

Divergence from std::vector

As already discussed in the comments, your vector class is slightly different from std::vector. This is due to the requirements of the assignment. Outside of class assignments, there are also real scenarios where you cannot use std::vector, but where you have to implement it yourself. In that case you do want to keep the interface as much as possible the same as std::vector's, to ensure your own class is a drop-in replacement, and there are no surprises.

Constructor reserving space vs. allocating elements

Your constructor that takes a size_t argument uses it to reserve space, but doesn't add any elements to the vector. However, the corresponding constructor from std::vector uses the argument to allocate actual elements which are default initialized. Also, with your class:

Vector<int> v(4, 2);

This allocates only space for two elements, which are not initialized, and sets m_Size to 4, making the sizes inconsitent with each other, and allowing a subsequent call to operator[]() read out of bounds without throwing an error. Contrast this with:

std::vector<int> v(4, 2);

This allocates a vector of 4 elements which are all initialized to the value 2. So a quite different behavior.

Use size_t for counters

In the constructor that takes an initializer list, you use int cnt, but an int might not be big enough. Use size_t consistently for sizes, counts and indices.

You can allocate memory in the member initializer list

Just a note that you can have more complex expressions in the member initializer list, including those with side effects such as allocating memory. So you can write:

Vector(size_t size, size_t cap)
    : m_Data(new T[cap]), m_Size(size), m_Capacity(cap) {}

It doesn't really matter in this case, but it is good practice to do this, as there are benefits in some cases.

Throw using a proper exception type

Don't throw random strings, but use a proper type for the exception. If you were to use the standard library, select a suitable type from <exception>, for example:

if (index >= m_Size)
    throw std::out_of_range("Index out of bounds");

If you cannot use the standard library, then at least define your own exception type, so a caller can use specific catch-blocks. For example, consider that you might want to do the following:

try {
    Vector<int> v(100000); // might throw std::bad_alloc if `new` fails
    Vector<int> w(10000);
    v[100000] = 10;   // out of range error
    v += w;           // vectors of different size
}
catch (std::bad_alloc &e) {
    // out of memory
}
catch (std::out_of_bounds &e) {
    // handle index out of bounds
}
catch (std::invalid_argument &e) {
    // handle operator+[] with an argument of the wrong size
}

If you just throw a string, you can only have one catch-block, which then has to parse the string to figure out what is going on.

Consider not doing bounds check in operator[]()

The standard library does not do bounds checks when using operator[](), since it has a significant impact on performance. There is a separate function, at(), that does do bounds checks.

No need to write Vector<T> inside Vector

Inside the class definition you don't need to write Vector<T>, just write Vector.

Missing iterators

Your class does not implement iterators, so you cannot write something like:

Vector<int> v(10);
...
for (auto el: v) {
    std::cout << el << "\n";
}

It's a good excercise to try to implement iterators for your class.

\$\endgroup\$
1
  • \$\begingroup\$ I know that you should not write comments like "thank you", but I want to let you know that your review was extremely useful and contains a lot of useful things besides vector implementation itself. Thanks. \$\endgroup\$ – Serghey Hmeli Sep 14 '20 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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