1
\$\begingroup\$

I have decided to rewrite what I did here, following the suggestions to use smart pointers. I will rewrite the other data structures as well using smart pointers where appropriate.

I just want to see how my code stands now, I am sure there are still areas I need to improve or fix. I again want to thank this community in their effort in evaluating my code, I really appreciate it and I believe it is slowly but surely taking my coding skills to the next level.

Here is my header file:

#ifndef Vector_h
#define Vector_h



template <class T>
class Vector {
private:

    static constexpr int initial_capacity = 100;

    // Instance variables
    int capacity = 0;
    int size = 0;
    std::unique_ptr<T[]> data = nullptr;

    void deepCopy(const Vector<T> &source) {
        capacity = source.size + initial_capacity;
        data = std::make_unique<T[]>(capacity);
        for (int i = 0; i < source.size; i++) {
            data[i] = source.data[i];
        }
        size = source.size;
    }

    void expandCapacity() {
        auto oldData = std::move(data);
        capacity *= 2;
        data = std::make_unique<T[]>(capacity);
        for (int i = 0; i < size; i++) {
            data[i] = oldData[i];
        }
    }

public:

    // Constructors
    Vector();                                           // empty constructor
    Vector(int n, const T &value);                      // constructor
    Vector(Vector<T> const &vec);                       // copy constructor
    Vector<T>& operator=(Vector<T> const &rhs);         // assignment operator

    // Rule of 5
    Vector(Vector<T> &&move) noexcept;                  // move constructor
    Vector& operator=(Vector<T> &&move) noexcept;       // move assignment operator
    ~Vector();                                          // destructor

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

    Vector<T>& operator+=(const Vector<T> &other) {
        Vector<T> newValue(size + other.size);

        std::copy(this->data, this->data + this->size, newValue.data);
        std::copy(other.data, other.data + other.size, newValue.data + this->size);

        newValue.swap(*this);
    }

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

        for (int i = 0; i < source2.size; 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 swap(Vector<T> &other) noexcept;
    void display(std::ostream &str) const;
    int getSize() const { return size; }
    int getCapacity() const { return capacity; }
    bool empty() const { return size == 0; }
    void clear() { size = 0; }
    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 = std::make_unique<T[]>(capacity);
    size = n;
    for (int i = 0; i < n; i++) {
        data[i] = value;
    }
}

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

template <class T>
Vector<T>::Vector(Vector<T> &&move) noexcept {
    move.swap(*this);
}

template <class T>
Vector<T>& Vector<T>::operator=(Vector<T> const &rhs) {
    Vector<T> copy(rhs);
    swap(copy);
    return *this;
}

template <class T>
Vector<T>& Vector<T>::operator=(Vector<T> &&move) noexcept {
    move.swap(*this);
    return *this;
}

template <class T>
Vector<T>::~Vector() {
    while (!empty()) {
        pop_back();
    }
}

template <class T>
T& Vector<T>::operator[](int index) {
    return data[index];
}

template <class T>
T const& Vector<T>::operator[](int index) const {
    return data[index];
}

template <class T>
bool Vector<T>::operator==(const Vector<T> &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>
void Vector<T>::swap(Vector<T> &other) noexcept {
    using std::swap;
    swap(capacity, other.capacity); 
    swap(size, other.size);
    swap(data, other.data);
}

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>
T Vector<T>::get(int index) const {
    if (index < 0 || index >= size) {
        throw std::out_of_range("[]: 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();
    }

    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:

#include <algorithm>
#include <initializer_list>
#include <iostream>
#include <cassert>
#include <ostream>
#include "Vector.h"


int main() {

    ///////////////////////////////////////////////////////////////////////
    ///////////////////////////// VECTOR //////////////////////////////////
    ///////////////////////////////////////////////////////////////////////
    Vector<int> nullVector;                        // Declare an empty Vector
    assert(nullVector.getSize() == 0);                 // Make sure its size is 0
    assert(nullVector.empty());                    // 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
    }

    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;



    std::cin.get();
}
\$\endgroup\$
4
\$\begingroup\$

#include every necessary header

or your code won't compile and is technically unfit for review here. So don't forget <memory> and <ostream> in your .h.

Memory management

That's what's most disappointing in an otherwise quite well written code. Memory management is the core of a vector class. Using smart pointers is a good practice, of course, but only solves part of the problem: it prevents memory leaks, but not other mismanagements of this rare resource.

Why would you initialize all your vectors with room for at least 100 elements? Your own example vectors contain only 20 elements, and it isn't rare at all to find smaller vectors. They're the most basic, most often used container in C++, so you can't waste that much memory in empty vectors. If you think I'm doing too much about this, just consider this:

std::vector<std::vector<std::vector<float>>>> temperatures; // occupies 3*sizeof(void*) bytes
Vector<Vector<Vector<float>>> temperatures // occupies more than 100**3*sizeof(float)

I'm not saying it's good to have nested vectors, I'm just saying it's something you should expect.

In the same way, don't add this initial_capacity to the capacity of the vector you're copying (in deepCopy), it's a waste of memory. For instance, let's say you want to compute the number of unique elements in your vector, you could write a function like this one:

int number_of_unique_elements(Vector v);

where the vector is taken by value because you'll have to reorder it when looking for duplicates and don't want to modify the original.

Constructors should be more coherent

I find a bit weird to assign 0 as a default value to the capacity variable:

template <class T>
class Vector {
    // ...
    int capacity = 0;
    // ...
};

only to set it at initial_capacity in your default constructor:

template <class T>
Vector<T>::Vector() : capacity(initial_capacity), size(0), data{ new T[capacity] }

It is misleading and even a bit worrisome since the 0 initialization is follow by expandCapacity, which multiplies the previous capacity by 2.

Use <algorithm> whenever you can

There are more than a few functions in which you use for loops over std::copy. Just don't.

Separate memory management and operations on data

Your interface doesn't include meaningful memory management methods (reserve, shrink_to_fit, resize) but is cluttered by external, and sometimes obscure operations.

operator<< has nothing to do here. Provide a way to access your data, and enjoy the power of algorithms:

Vector<int> data;
// fill data
std::copy(data.begin(), data.end(), std::ostream_iterator<int>(cout, ", "));

operator+ is worse, because it has no obvious meaning. It could mean concatenation as well as element-wise addition. Concatenation isn't a problem from outside either:

Vector<float> result{srv_vec1};
result.reserve(result.size()+src_vec2.size());
result.insert(src_vec2.begin(), src.vec2.end());

Providing iterators is the best way to offer an access into the vector's data. If you don't want to, or at least not now, just provide a pointer to your data.

Respect conventions

get and set aren't part of the vector vocabulary. Use at instead, and make it return a reference to the element!

Use specific exceptions

std::invalid_argument isn't very explicit, all the more when std::out_of_range is available.

Conclusion

Code reviews are more about what is wrong, but your code is quite good. I believe that you should aim higher though, and think more deeply about memory management. There are two main aspects about this:

  1. how much memory to allocate: how much memory in an empty vector? how much more memory in a full vector? You've already thought of this even if you have to refine your approach.

  2. when do I initialize the allocated memory? A new[] operation not only allocates memory for n objects but also initializes them. It isn't necessary optimal. You may rather allocate uninitialized storage and construct only when necessary. You may even leverage this to construct new elements directly inside your vector from their constructors' arguments.

There are also some other optimizations you could consider, but they can be more complex to implement.

The first that comes to my mind is to allow for custom allocation functions: like every std::container, add Allocator to your template arguments and rely on the allocator interface to allocate memory.

Another one is to provide a Vector<bool> specialization.

Still another one would to implement a "small Vector<char>" optimization: memory for small Vector<char> could be allocated on the stack rather than on the heap.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your answer. For the memory management section, for the comment "Why would you initialize all your vectors with room for at least 100 elements?", what do you suggest I do to fix this issue? On the same section, you say "don't add this initial_capacity to the capacity of the vector you're copying (in deepCopy), it's a waste of memory." Do you suggest I take I change it to just capacity = source.size? \$\endgroup\$ – Snorrlaxxx Aug 8 '18 at 23:01
  • \$\begingroup\$ @Snorrlaxxx: an empty vector shouldn't use memory beyond the bare minimum (data, capacity, size). So initialize data as a null pointer, and don't grow the buffer before elements are pushed back into it. / indeed, capacity = source.size() should be good. \$\endgroup\$ – papagaga Aug 9 '18 at 8:56
3
\$\begingroup\$
data = std::make_unique<T[]>(capacity);
size = n;

Putting aside that this should be actually done in an init-list, here you create 100 objects yet claim you only have n of them. While being okay for simple types, this may not always be a good case (imagine an object that, by default, creates a TCP connection to a default address overseas.) It would probably make more sense to make data an uninitialized storage, storing objects in it as needed.

\$\endgroup\$

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.