Generic vector class, follow up

Question

This is a follow up from a post I made here. I am creating a generic vector class. I have changed the code around considerably since I had so many errors (decided to just re-do it from scratch).

I just want to check to see if there is additional errors I made or certain parts that I can improve or add upon this class I made. Following the three/zero/five rule, I may need to add a move constructor to my class, but I just want to first see what you all think.

Here is my header file:

#ifndef Vector_h
#define Vector_h

#include <initializer_list>
#include <iostream>

template <class T>
class Vector {
private:

    static const int INITIAL_CAPACITY = 100;

    // Instance variables
    int capacity;        // capacity of vector
    int size;
    T* data;

    // Method: deepCopy
    void deepCopy(const Vector<T> & source) {
        capacity = source.size + INITIAL_CAPACITY;
        this->data = new T[capacity];
        for (int i = 0; i < source.size; i++) {
            data[i] = source.data[i];
        }
        size = source.size;
    }

    // Method: expandCapacity
    void expandCapacity() {
        T *oldData = data;
        capacity *= 2;
        data = new T[capacity];
        for (int i = 0; i < size; i++) {
            data[i] = oldData[i];
        }
        delete[] oldData;
    }

public:

    // Constructors
    Vector();                           // empty constructor
    Vector(int n, const T& value);      // constructor
    Vector(Vector const& vec);          // copy constructor
    ~Vector();                          // destructor


    // Overloading operators
    T& operator[](int index);
    bool operator==(Vector&) const;
    Vector<T>& operator=(Vector<T> const& rhs);

    friend Vector<T>& operator+(Vector<T>& source1, Vector<T>& source2) {
        int n = source1.getSize() + source2.getSize();
        static Vector<T> newSource(n, 0);
        for (int i = 0; i < source1.getSize(); i++) {
            newSource[i] = source1[i];
        }
        for (int i = 0; i < source2.getSize(); i++) {
            newSource[i + source1.getSize()] = source2[i];
        }
        return newSource;
    }

    friend std::ostream& operator<<(std::ostream& str, Vector<T>& data) {
        data.display(str);
        return str;
    }


    // Member functions
    void display(std::ostream& str) const;
    int getSize() const;
    int getCapacity() const;
    bool isEmpty() const;
    void clear();
    T get(int index) const;
    void set(int index, const T& value);
    void set(int index, T&& value);
    void insert(int index, const T& value);
    void insert(int index, T&& value);
    void remove(int index);
    void push_back(const T& value);
    void pop_back();

};

template <class T>
Vector<T>::Vector() {
    capacity = INITIAL_CAPACITY;
    size = 0;
    data = new T(capacity);
}

template <class T>
Vector<T>::Vector(int n, const T& value) {
    capacity = (n > INITIAL_CAPACITY) ? n : INITIAL_CAPACITY;
    data = new T[capacity];
    size = n;
    for (int i = 0; i < n; i++) {
        data[i] = value;
    }
}

template <class T>
Vector<T>::Vector(Vector const& vec) {
    deepCopy(vec);
}

template <class T>
Vector<T>::~Vector() {
    delete[] data;
}

template <class T>
T& Vector<T>::operator[](int index) {
    if(index < 0 || index >= size) {
        throw std::invalid_argument ("[]: index out of range");
    }
    return data[index];
}

template <class T>
bool Vector<T>::operator==(Vector& rhs) const {
    if(getSize() != rhs.getSize()) {
        return false;
    }
    for(int i = 0; i < getSize(); i++) {
        if(data[i] != rhs[i]) {
            return false;
        }
    }
    return true;
}

template <class T>
Vector<T>& Vector<T>::operator=(const Vector<T> &rhs) {
    if(this != &rhs) {
        delete[] data;
        deepCopy(rhs);
    }
    return *this;
}

template <class T>
void Vector<T>::display(std::ostream& str) const {
    for(int i = 0; i < size; i++) {
        str << data[i] << "\t";
    }
    str << "\n";
}

template <class T>
int Vector<T>::getSize() const {
    return size;
}

template <class T>
int Vector<T>::getCapacity() const {
    return capacity;
}

template <class T>
bool Vector<T>::isEmpty() const {
    return (size == 0);
}

template <class T>
void Vector<T>::clear() {
    size = 0;
}

template <class T>
T Vector<T>::get(int index) const {
    if(index < 0 || index >= size) {
        throw std::invalid_argument ("get: index out of range");
    }
    return data[index];
}

template <class T>
void Vector<T>::set(int index, const T& value) {
    if(index < 0 || index >= size) {
        throw std::invalid_argument ("set: index out of range");
    }
    data[index] = value;
}

template <class T>
void Vector<T>::set(int index, T&& value) {
    if(index < 0 || index >= size) {
        throw std::invalid_argument ("set: index out of range");
    }
    data[index] = std::move(value);
}

template <class T>
void Vector<T>::insert(int index, const T& value) {
    if(size == capacity) {
        expandCapacity();
    }

//    if(index < 0 || index >= size) { // commented this out because I was        getting a sigbart1 error that I could not fix
//        throw std::invalid_argument ("insert: index out of range");
//    }
//    
    for(int i = size; i > index; i--) {
        data[i] = data[i-1];
    }
    data[index] = value;
    size++;
}

template <class T>
void Vector<T>::insert(int index, T&& value) {
    if(size == capacity) {
        expandCapacity();
    }

    if(index < 0 || index >= size) {
        throw std::invalid_argument ("insert: index out of range");
    }

    for(int i = size; i > index; i--) {
        data[i] = data[i-1];
    }
    data[index] = std::move(value);
    size++;
}

template <class T>
void Vector<T>::remove(int index) {
    if(index < 0 || index >= size) {
        throw std::invalid_argument ("insert: index out of range");
    }

    for(int i = index; i < size - 1; i++) {
        data[i] = data[i+1];
    }
    size--;
}

template<class T>
void Vector<T>::push_back(const T& value) {
    insert(size, value);
}

template<class T>
void Vector<T>::pop_back() {
    remove(size - 1);
}

#endif /* Vector_h */

Here is the main.cpp file that tests this class:

#include <cassert>
#include <iostream>
#include "Vector.h"


int main(int argc, const char * argv[]) {

    ///////////////////////////////////////////////////////////////////////
    ///////////////////////////// VECTOR //////////////////////////////////
    ///////////////////////////////////////////////////////////////////////
    Vector<int> nullVector;                         // Declare an empty Vector
    assert(nullVector.getSize() == 0);              // Make sure its size is 0
    assert(nullVector.isEmpty());                   // Make sure the vector is empty
    assert(nullVector.getCapacity() == 100);        // Make sure its capacity is greater than 0

    Vector<int> source(20, 0);                      // Declare a 20-element zero Vector
    assert(source.getSize() == 20);                 // Make sure its size is 20
    for (int i = 0; i < source.getSize(); i++) {
        source.set(i, i);
        assert(source.get(i) == i);                 // Make sure the i-th element has value i
    }



    source.remove(15);                              // Remove the 15th element
    assert(source[15] == 16);                       // Make sure the 15th element has value 16
    source.insert(15, 15);                          // Insert value 15 at the index 15
    assert(source[15] == 15);                       // Make sure the 15th element has value 15

    source.pop_back();                              // Remove the last element
    assert(source.getSize() == 19);                 // Make sure its size is 19
    source.push_back(19);                           // Insert value 20 at the bottom
    assert(source.getSize() == 20);                 // Make sure its size is 20
    assert(source.get(19) == 19);                   // Make sure the 19th element has value 19

    Vector<int> copyVector(source);                 // Declare a Vector equal to source
    for (int i = 0; i < source.getSize(); i++) {
        assert(copyVector[i] == source[i]);         // Make sure copyVector equal to source
    }

    // Vector<int> newSource = copyVector + source;
    std::cout << "source: \n"<< source;             // Print out source
    std::cout << "copyVector: \n" << copyVector;    // Print out copyVector
    Vector<int> newSource = source + copyVector;    //  Concatenate source and copyVector
    std::cout << "newSource: \n" << newSource;      // Print out source + copyVector

    source.clear();                                 // Clear source
    assert(source.getSize() == 0);                  // Make sure its size is 0

    std::cout << "Vector unit test succeeded." << std::endl;



    return 0;
}

Answer 1

Design

Your bigest mistake (in my opinion) is that you are not doing capacity correctly. When you create a vector with a capacity greater than its size you are actually constructing all those extra objects into your new vector.

The problem here is that:

1. The class T may not be default constructible.
2. This can be very expensive (if T is expensive to create)
3. You may never use these object (so why create them).

Yes you should have a capacity that is different from the size, but you should not be instantiating these objects until you need them.

See the section: Version-3 Lazy Construction of elements in Vector Resource Management

The other problem I see is that you are always double constructing the objects. You always create T objects with the default constructor and then you copy over them using the assignment operator. This can make the code inefficient.

You should learn about "Placement new" (see my article for details).

Code Review

You don't put your code in its own namespace. Create a namespace that you always use Istomin seems like a good unique namespace name.

These include guards are a bit weak.

#ifndef Vector_h
#define Vector_h

They should be all caps (as they are macros) you should probably also add the namespace to them to make sure they are unique.

I like the magic number being put into a static variable.

    static const int INITIAL_CAPACITY = 100;

But it would be nice if you added some comments on why you came up with 100? Even if this is just an arbitrary choice just say so. Then when somebody comes back to see why they can quickly decide if they can optimize your class be updating this value or not.

Your deepCopy() is what I expect to see in the copy constructor. looking at your code it is called from the copy constructor and the assignment operator (so as expected).

In expandCapacity() you don't account for problems.

    void expandCapacity() {
        T *oldData = data;
        capacity *= 2;
        data = new T[capacity];

        // At this point in your code.
        // data points at a new array (that is full of default constructed objects).
        // Which is fine.

        for (int i = 0; i < size; i++) {
            // But these assignment operations can throw.
            // What happens if an assignment operator throws?
            data[i] = oldData[i];
        }
        delete[] oldData;
    }

If any of the assignment operators throws you have two issues.

1. You leak oldData (you should be holding that in some object to destroy it).
2. Your object is now in an invalid state. It has a set of objects that could have the old values. It could have the new values you have no way to determine which values are good in data (which have been copied over and which are just default constructed).

An operation should either succeed. Or if it fails then it should preferably leave the object in its original state. I cover this topic a lot in my article.

You said you implement the rule of five.

    Vector();                           // empty constructor
    Vector(int n, const T& value);      // constructor
    Vector(Vector const& vec);          // copy constructor
    ~Vector();                          // destructor

    // Also I normally put the assignment operator
    // With the constructors as they are so intertwined.    
    Vector<T>& operator=(Vector<T> const& rhs);

I don't see the move constructor or the move assignment operator.

This is the standard operator. But what about a const version?

    T& operator[](int index);

It is quite common to pass objects by const reference (so you can read but not modify them). There is no const version of operator[] so no way to read the values of the vector when it is passed as a const reference.

I would have both versions.

    T&       operator[](int index);
    T const& operator[](int index) const;

I would also look at the std::vector at the at() method. To see the difference between the different types of accesses.

Why is the parameter not a const reference?

    bool operator==(Vector&) const;

These are all fine.
But they are also so simple you could have just defined them in-line.

    int getSize() const;
    int getCapacity() const;
    bool isEmpty() const;

I should point out that using initializer lists is the preferred way of initializing variables in the constructor. If you use it consistently you avoid the possibility of member being initialized twice.

template <class T>
Vector<T>::Vector() {
    capacity = INITIAL_CAPACITY;
    size = 0;
    data = new T(capacity);
}

Unfortunately deepCopy() causes a problem for you in the assignment operator. Just note here that it quite possible for this to fail in two places. 1) The default constructor of T and 2) the assignment operator of T. This does not matter so much in this function but when we look at the assignment operator it is an issue.

    void deepCopy(const Vector<T> & source) {
        capacity = source.size + INITIAL_CAPACITY;
        this->data = new T[capacity];
        for (int i = 0; i < source.size; i++) {
            data[i] = source.data[i];
        }
        size = source.size;
    }

No problems here:

template <class T>
Vector<T>::Vector(Vector const& vec) {
    deepCopy(vec);
}

Here we have some issues.

template <class T>
Vector<T>& Vector<T>::operator=(const Vector<T> &rhs) {

    // pessimising test for self assignment.
    if(this != &rhs) {

        // Here is your problem.
        delete[] data;

        // You have destroyed your old data
        // If the deep copy throws an exception then
        // you data is now in an invalid state (just like expand).
        deepCopy(rhs);
    }
    return *this;
}

Don't bother to test for self assignment (your code should still work for self assignment). But self assignment is vanishingly rare. Thus the extra test is pessimizing the normal operation of the assignment operator. Even though the cost for self assignment can be high the fact that it happens so rarely means that on average you are slowing your code because the normal operation has to do this extra branch.

This is why the Copy and Swap Idiom does not bother to test for self assignment. So normal you write the assignment operator like this:

Vector<T>& Vector<T>::operator=(Vector<T> const& rhs)
{
     Vector<T> copy(rhs);   // Use copy constructor to make a copy.
                            // You make a safe copy of the data without
                            // modifying this object. This means if
                            // something goes wrong your object is unchanged.
     swap(copy);            // swap the copy and this.
                            // This puts the current data into copy.
     return *this;
}
// At this point `copy` goes out of scope.
// This calls copys destructor and destroys the data.

Note: The standard version of operator[] does not check index is in range. As you normally check this externally and thus this check is a wasted operation.

template <class T>
 T& Vector<T>::operator[](int index) {
     if(index < 0 || index >= size) {
         throw std::invalid_argument ("[]: index out of range");
     }
     return data[index];
 }

If you want a checked access then you use at().

Thisnk of this situation:

  for(int loop = 0; loop < v.size(); ++loop)
  {
      std::cout << v[loop]; // we know loop is in range as
                            // we know it is smaller than v.size().
  }

Answer 2

static const int INITIAL_CAPACITY = 100;

“constexpr is the new static const”. Make this constexpr instead. Also, I think I mentioned before about using all-caps names.

T* data;
 ⋮
  this->data = new T[capacity];

You are still using a raw pointer and naked new, noted in your previous review.

Writing this-> to access your instance data is not normal. Just refer to data, not this->data.

Notwithstanding that, the loop

    for (int i = 0; i < source.size; i++) {
        data[i] = source.data[i];

should just be a call to std::copy.

    for (int i = 0; i < size; i++) {
        data[i] = oldData[i];
    }

Ditto.

---

// Method: deepCopy
void deepCopy(const Vector<T> & source) {

Well, C++ doesn’t have methods. But a comment stating the name of the function which is clearly stated on the next line is not useful.

---

friend Vector<T>& operator+(Vector<T>& source1, Vector<T>& source2) {

The canonocal way to write operator+ is to call operator+=. You shouldn't need to make it a friend since the values need to be accessible by public means (otherwise what good is the vector to anyone)?

And again, use std::copy, rather than writing loops.

---

The ability to display the contents should not be a member — that can be written using the public API of being able to ask its size and each item contained. Don’t bloat your interfaces with stuff that’s not essential to the encapsulation and abstraction.

---

Vector<T>::Vector() {
    capacity = INITIAL_CAPACITY;
    size = 0;
    data = new T(capacity);
}

Use the member initialization list, not assignments in the body of the function.

capacity = (n > INITIAL_CAPACITY) ? n : INITIAL_CAPACITY;

You mean std::max? Better use std::clamp since you are not testing for negative numbers!

for (int i = 0; i < n; i++) {
    data[i] = value;

That should be std::fill_n.

---

template <class T>
bool Vector<T>::operator==(Vector& rhs) const {
    if(getSize() != rhs.getSize()) {
        return false;
    }
    for(int i = 0; i < getSize(); i++) {
        if(data[i] != rhs[i]) {
            return false;
        }
    }
    return true;
}

Or, just use std::equal.

---

A lot of the trivial functions should just be inline in the class definition.

---

I suggest you read through and become familiar with the Standard Library Algorithms.

Good show on making unit tests! Keep it up, and good luck.

Answer 3

I think, writing vector is pretty hard exercise. Added comments in code below:

#include <iostream>
#include <string>
#include <thread>
#include <vector>
#include <cassert>
#include <cstdlib>

int main()
{
    Vector<std::string> v1(1, "hello");

    // --- will crash on some iteration...
    for(int i = 0; i < 100; ++i)
    {
        v1.push_back(v1[0]);      // just because I can
        v1.insert(0, v1[0]);      // ... this one too
    }
    // --------------


    // --- does not compile
    const auto& ref = v1;
    assert(v1 == ref); 
    // --------------------


    // --- assertion failure: guess, why?
    std::vector<std::thread> threadPool;
    for(int i = 0; i < 20; ++i)
    {
        threadPool.emplace_back([](int id) 
            {
                std::srand(id);
                Vector<int> first (std::rand() % 1000 + 1000, 1);
                Vector<int> second(std::rand() % 1000 + 1000, 2);
                Vector<int> third = first + second;

                assert(third.getSize() == (first.getSize() + second.getSize()));
                return third.getSize();
            }, 
            i);
    }

    for(std::thread& t : threadPool)
        t.join();
    // ------------------------------------


    // where is ~A() calls on clear()?
    struct A
    {
        int m_c[1024];
        A()  { std::cout << __FUNCTION__ << std::endl; }
        ~A() { std::cout << __FUNCTION__ << std::endl; }
    };

    Vector<A> v2(1000, A());
    v2.clear();
    // -------------------------------


    // --- does not compile
    struct B
    {
        int m_i;

        B() = delete;
        B(int i) : m_i(i) {}
    };

    Vector<B> v3(1000, B(1));         // does not compile
    std::vector<B> stdv(1000, B(1));  // just fine
    // -------------------------------

    return 0;
}