Vector implementation, which received unhelpful negative feedback from professor

Question

I've just finished a homework assignment to implement a simple Vector class.

-Kindly ignore the following two paragraphs if you don't want to read someone whining about their professor

Yadda, yadda, same old stuff. Here's where it gets interesting though; My professor is a bit... strange in his preferences. He's a retired cabinet maker who learned programming in his 50's, and decided that teaching at a local Community College would be a great way to make a decent amount of money without working.

I'm a 'do your own research' kinda guy, and the more I read (here on stackexchange, as well as in various paper books), the more I notice that some of his instructions/requirements are suboptimal to say the least. For example: using namespace std in every header file he requires us to implement without modifying. Typical feedback on my assignments have been "too many errors to list" and "This code is... odd." I've been getting A's on exams, and solid 70% C's on my assignments. Unfortunately, he doesn't allow us to email him regarding assignments and I'm a full-time student/full-time fast-food worker, so his 5 office-hours per week are really hard to pencil into my schedule.

This is where you kind folks come in. I really, really want to learn how to be a solid programmer. I aspire to one day have header files void of any using namespace whatsoever. That's why I'd love some input into how I can improve this particular assignment, as well as good practices in general that I can adopt.

-Whining is over, relevant information starts here.

The assignment was to implement a Vector class using the function definitions that my professor provided. Unfortunately, I can't change those and I'm also unable to add any public functions that were not included in his list of definitions. Additionally, I'm not allowed to #include anything besides <iostream>.

My Vector.h is as follows:

#ifndef _VECTOR_H_
#define _VECTOR_H_

#include <iostream>

template <class T> class Vector
{
    int _index_offset;
    unsigned _size;
    unsigned _length;
    T* _array;

    void Double();
    void Halve();

    public:
    Vector (int i = 0);
    Vector (const T*, unsigned s, int i = 0);
    Vector (const Vector&);
    virtual ~Vector();

    Vector& operator=(const Vector&);

    template <class P>
    friend std::ostream& operator<< (std::ostream&, const Vector<T>&);
    template <class P>
    friend std::ostream& operator<< (std::ostream&, const Vector<T>*);

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

    Vector operator() (int first, int last) const;

    Vector& operator+= (const T&);
    Vector& operator+= (const Vector&);

    unsigned Length() const;

    void Delete (const int i);
    void Delete (int first, int last);
    void Delete();

    void Insert (const T&, int i);
    void Insert (const T&);
};


template <class T>
Vector<T>::Vector (int i) : _index_offset(i), _size(0), _length(0)
{
    _array = new T[_size];
}

template <class T>
Vector<T>::Vector (const T* first_element, unsigned s, int i) : Vector(i)
{
    while (s < _size)
    {
        Double();
    }

    for (unsigned i = 0; i < s; i++)
    {
        _array[i] = first_element[i];
    }
}

template <class T>
Vector<T>::Vector (const Vector& other) : _index_offset(other._index_offset),  _size(other._size), _length(other._length)
{
    _array = new T[_size];

    for (unsigned i = 0; i < _length; i++)
    {
        _array[i] = other._array[i];
    }
}

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

template <class T>
void Vector<T>::Double()
{
    T* new_array;

    if (_size == 0)
    {
        _size = 1;
        new_array = new T[1];
        delete[] _array;
        _array = new_array;
    }

    else
    {
        _size *= 2;
        new_array = new T[_size];

        for (int i = 0; i < _length; i++)
        {
            new_array[i] = _array[i];
        }

        delete[] _array;
        _array = new_array;
    }
}

template <class T>
void Vector<T>::Halve()
{
    if (_size >= _length * 2)
    {
        _size /= 2;
        T* new_array = new T[_size];

        for (int i = 0; i < _length; i++)
        {
            new_array[i] = _array[i];
        }

        delete[] _array;
        _array = new_array;
    }
}

template <class T>
Vector<T>& Vector<T>::operator= (const Vector& other)
{
    if (this != other)
    {
        _index_offset = other._index_offset;
        _size = other._size;
        _length = other._length;

        delete[] _array;
        _array = new T[_size];

        for (int i = 0; i < _length; i++)
        {
            _array[i] = other._array[i];
        }
    }

    return *this;
}

template <class T>
std::ostream& operator<< (std::ostream& os, const Vector<T>& vec)
{
    os << "{";
    for (int i = 0; i < (vec.Length() - 1); i++)
    {
        os << vec[i] << ", ";
    }
    os << vec[(vec.Length() - 1)] << "}";

    return os;
}

template <class T>
std::ostream& operator<< (std::ostream& os, const Vector<T>* vec)
{
    Vector<T> vec_ref = *vec;
    os << vec_ref;

    return os;
}

template <class T>
T& Vector<T>::operator[] (int i)
{
    int index = i - _index_offset;

    return _array[index];
}

template <class T>
const T& Vector<T>::operator[] (int i) const
{
    int index = i - _index_offset;

    return _array[index];
}

template <class T>
Vector<T> Vector<T>::operator() (int first, int last) const
{
    int first_index = first - _index_offset;
    int last_index = last - _index_offset;
    int new_size = ((last_index - first_index) - 1);

    T selection[new_size];
    for (int i = 0; i < new_size; i++)
    {
        selection[i] = _array[first_index + i];
    }

    return *(new Vector<T>(selection, new_size));
    /* TODO: How am I supposed to clean up this Vector? When will Destructor get called?
    Will it be destructed as operator() exits, thus returning a pointer to an unreserved location? */
}

template <class T>
Vector<T>& Vector<T>::operator+= (const T& value)
{
    if (_size == _length)
    {
        Double();
    }

    _array[_length] = value;
    _length++;

    return *this;
}

template <class T>
Vector<T>& Vector<T>::operator+= (const Vector& vec)
{
    for (int i = 0; i < vec._length; i++)
    {
        *this += vec._array[i];
    }
}

template <class T>
unsigned Vector<T>::Length() const
{
    return _length;
}

template <class T>
void Vector<T>::Delete (const int i)
{
    int index = i - _index_offset;

    if (0 <= index && index < _length)
    {
        _length--;

        for (int i = index; i < _length; i++)
        {
            _array[i] = _array[i+1];
        }

        if (_size >= _length * 2)
        {
            Halve();
        }
    } else std::cerr << "Error - Vector<T>::Delete(const int i): i cannot be less than 0, or greater than or equal to Vector._length" << std::endl;
}

template <class T>
void Vector<T>::Delete (int first, int last)
{
    int first_index = first - _index_offset;
    int last_index = last - _index_offset;

    if ((first_index >= 0 && last_index < Length()) && (first_index < last_index))
    {
        for (int num_deleted = 0; num_deleted < (last_index - first_index); num_deleted++)
        {
            Delete(first_index);
        }
    } else std::cerr << "Error - Vector<T>::Delete(int first, int last): Invalid arguments." << std::endl;
}

template <class T>
void Vector<T>::Delete()
{
    Delete(0);
}

template <class T>
void Vector<T>::Insert(const T& value, int i)
{
    int index = i - _index_offset;

    if (index < _length)
    {
        if (_length == _size)
        {
            Double();
        }

        for (int j = _length; j > index; j--)
        {
            _array[j] = _array[j - 1];
        }

        _array[index] = value;
        _length++;
    } else std::cerr << "Error - Vector<T>::Insert(const T& value, int i): i cannot be greater than or equal to Vector._length" << std::endl;
}

template <class T>
void Vector<T>::Insert(const T& value)
{
    Insert(value, _index_offset);
}

#endif

Some explanation: The assignment requires that the user be able to specify a starting index for the Vector besides 0 if they so choose. For example, if they declare Vector<int> vec = new Vector<int>(10), the initial element of the Vector will be at vec[10], and vec[9] or anything lower would be out of bounds. He said this would be one of the greatest challenges of the assignment, but the _index_offset solution seemed pretty obvious to me so I'm concerned that it's a terrible solution. _size and _length, if it's not obvious, refer to the current reserved memory of the array and its number of occupied elements, respectively.

My professor's unhelpful (and to my sensitive heart, frankly hurtful) feedback has given me a burning, vindictive desire to submit an assignment that is unimpeachable in its implementation. I'm highly confident that my current implementation could do with a huge amount of improvement, and I'd be extremely grateful for any suggestions you fine folks could offer.

Answer 1

I understand that some of this class is predicated by your professor; However I will review the code as a whole and you can then choose what can be changed and what cannot be changed.

Interface/High-level comments

Use of leading underscore _ has severe limitations.

The C and C++ standards reserve the use of certain patterns of leading underscores for implementation purposes. If you use leading underscore in a way that is reserved for the implementation you may get undefined behavior. Unless you are 100% certain that every one working on the project know these rules by heart. I suggest to simply avoid leading underscore in identifiers.

The code has undefined behavior on the first line:

#ifndef _VECTOR_H_

Speaking of which, the include guard as written it is susceptible to name collision as it is rather short and VECTOR is kind of a common name for a file. If a name collision happens the build will in best case break or in worst case whatever header happened to have the same include guard may provide a class with identical signatures but different behavior (unlikely I know, but has happened to me) and you could have crashes during runtime. A much better include guard would be #ifndef GUARD_MYPROJECT_VECTOR_H.

As a personal side note, I personally dislike the style of trailing underscores as well. I use m_ as a prefix for mutable members and c_ for constant members but other conventions are just as good.

Ordering of public, protected, private

This is of course very much up to personal preference but I prefer to always have the different visibility fields ordered as: public, protected, private. The reason is that the code will by definition be used more often than it is written (hopefully!) and by that reason you should write the code to be as easy as possible to read and use. For this reason I sort the fields in order of interest to the user. The user is most often interested in the public API, then possibly the protected stuff if they'll inherit from the class. And rarely are they interested in the private implementation.

Add member type definitions used

Typically in template container classes we add a few type definitions, normally I'd expect at least the following:

using value_type = T;
using size_type = std::size_t;

But prefer to have most of the member types of for example std::vector.

The reason is that for example if you do:

std::vector<X> v;
for(??? i = 0; i < v.size(); ++i){
    ....
}

what is the correct type to put into ???? Well in this case we know that it is size_t because this is what is std::vector is specified to return from size(). But what if it wasn't std::vector but some other template class we have no idea of, or what if the class itself is a template? Like so:

 template<typename Container>
 void foo(){
     Container c;
     for(??? i = 0; i < c.size(); ++i){

     }
 }

Yes, you could use iterators and probably should but it's not always possible. But we can use std::vector<X>::size_type or Container::size_type to always get the proper type for this and other similar purposes.

Naming

It is very unfortunate that the class shares it's name with std::vector, has the same purpose and similar signatures. But different semantics. For example if I hadn't read your question properly I would have believed that Vector v = Vector(32); would create a dynamic Vector with initial size of 32 elements. The class should be named OffsetVector or something to that tune instead to avoid confusion.

The name Delete is also very unfortunate as it carries the connotation of keyword delete it just looks wrong. Typically we use Erase or Remove for this type of method. Also Delete() is typically called Clear.

Single responsibility

A class should do one thing and do it well, see Single Responsibility Principle. Your class has two responsibilities, manage a dynamic memory region AND add keep track of an offset.

In fact this class should really be split into two. There should be one class that manages the dynamic memory, this would just be a clone of std::vector. And another class that adds an offset to a container. Maybe something like this:

template<typename Container>
class OffsetContainer{
public:
    using value_type = Container::value_type;
    using reference_type = Container::reference_type;
    using size_type = Container::size_type;
    // add others

    OffsetContainer(Container&& c, size_type offs)
        : container(std::move(c)), offset(offs)
    {}

    reference_type operator [](size_type i){
        return container[i + offset];
    }

private:
    Container container;
    size_type offset;
};

and you would use it like so:

OffsetContainer<std::vector<X>> c(offset);

Managing raw memory

I understand that this is probably an exercise in handling memory and remembering to implement the rule of three but in practice you would use std::unique_ptr instead.

Don't abuse operator overloads

Operator overloads are easy to abuse. In general you should only overload operators if the conventional usage of the operator is well established and well understood.

For example Vector operator() (int first, int last) const; I imagine this is a deep copy, slice operator but it could just as well be considered double indexing. This operator would much better be a method called copySlice(int first, int last).

Also Vector& operator+= (const Vector&); is also a less than ideal operator. Does it perform vector addition, or concatenation, how does it concatenate? At the front? At the end? If this class was modeling a mathematical vector, it would be obvious that it was vector addition. But here it isn't. There's a reason that std::vector doesn't have this overload.

Implementation

Avoid unnecessary work or memory (re)allocation

Why are you doing all this extra work by growing the vector repeatedly when you know the size? Not only are you causing unnecessary memory allocations but initializing the vector this way is causing lots of unnecessary copying of the elements as well.

template <class T>
Vector<T>::Vector (const T* first_element, unsigned s, int i) : Vector(i)
{
    while (s < _size)
    {
        Double();
    }

Simply allocate the size that you know you want and some additional room to grow. Try to minimize usage of memory allocation.

Use standard algorithms

The standard library has many algorithms that you can use to make life easier and your code more readable.

For example:

for (unsigned i = 0; i < s; i++)
{
    _array[i] = first_element[i];
}

is better written as:

std::copy(first_element, first_element + s, _array);

Avoid uninitialized declaration of variables like the plague

I can not begin to tell you how many bugs I have seen caused by uninitialized variables, this is one of the most common type of errors which are also hard to catch once out in production.

template <class T>
void Vector<T>::Double()
{
    T* new_array;

    if (_size == 0)
    {
        _size = 1;
        new_array = new T[1];
        delete[] _array;
        _array = new_array;
    }

    else
    {
        _size *= 2;
        new_array = new T[_size];

        for (int i = 0; i < _length; i++)
        {
            new_array[i] = _array[i];
        }

        delete[] _array;
        _array = new_array;
    }
}

Here for example you should at least initialize new_array to nullptr. But you should also move its declaration as close as possible to where it is used, this makes the code easier to read and reason about. So the above should be:

template <class T>
void Vector<T>::Double() {  
    if (_size == 0) {
        _size = 1;
        auto new_array = new T[1];
        delete[] _array;
        _array = new_array;
    }
    else {
        _size *= calculateGrowthFactor();
        auto new_array = new T[_size];
        std::copy(_array, _array + _length, new_array);
        delete[] _array;
        _array = new_array;
    }
}

While we're looking at code, that 1 that you have there? That should be replaced by a constant MINIMUM_SIZE which probably should be like 20-30 or something like that because for small sizes of the vector you grow very frequently which is bad for performance.

Also note that if _size *= 2 is really aggressive and very wasteful once the vector is getting big. You should base the rate of growth on the current size of the vector.

Don't waste capacity on copying

In your operator = you always delete the old array and allocate a new one. This is wasteful as memory allocation takes time. Instead, you should check if the old array is large enough to old the contents of the other arrays, and then just copy the contents in.

While I'm on the subject. The way you are implementing the vector requires that your template type T be default constructible. You should verify this using a static_assert and std::is_default_constructible.

But this also has a problem with actually constructing objects of type T when you increase the capacity of the vector. If T is non-trivial then this causes a lot of work.

So this whole way of implementing as vector is rather poor, you need to manage a raw memory area and use placement new. In essence this is why you shouldn't be implementing your own containers unless you actually know what you're doing and I think that this whole exercise is poorly thought out as it teaches a bad habit.

Implement strong exception safety in copy assignment operator

In your copy assignment operator, consider what happens if the allocation of the new array fails?

template <class T>
Vector<T>& Vector<T>::operator= (const Vector& other) {
    if (this != other) {
        _index_offset = other._index_offset;
        _size = other._size;
        _length = other._length;

        delete[] _array;
        _array = new T[_size]; // new throws std::bad_alloc

        for (int i = 0; i < _length; i++) {
            _array[i] = other._array[i];
        }
    }
    return *this;
}

Then this object will be left in a broken, undefined state and will be unusable as _array is a dangling pointer. The concept of Exception Safety concerns with what guarantees can be made about the object's state if it throws an exception. Your method above has no exception safety.

You need to allocate the new, array, copy the contents and only if that succeeded, you swap the pointers and delete the old array. Like so:

template <class T>
Vector<T>& Vector<T>::operator= (const Vector& other) {
    if (this != other) {
        auto new_size = other.Length();
        auto new_array = new T[new_size];
        try {
            std::copy(other._array, other._array + new_size, new_array);
        } catch(...){
            // Catch any exception and free memory so we don't leak.
            delete new_array; 
            throw(); // Re-throw the exception to caller
        }

        _index_offset = other._index_offset;
        _size = other._size;
        _length = other._length;    

        std::swap(new_array, _array);
        delete new_array; // Delete cannot throw
    }
    return *this;
}

This guarantees "strong" exception safety. Meaning that if operator = throws, the neither any of the arguments or the object itself will have been modified.

Another way to be sneaky and obtain strong exception safety is to use the copy and swap idiom.

template <class T>
Vector<T>& Vector<T>::operator= (Vector other) { // Take by value
    swap(*this, other);
    return *this;
}

of course you'd have to implement swap but it's trivial, just swap all the members and you're done. I'll leave the explanation of why this works to the link above.

operator (int,int)

There are many problems with this code:

template <class T>
Vector<T> Vector<T>::operator() (int first, int last) const
{
    int first_index = first - _index_offset;
    int last_index = last - _index_offset;
    int new_size = ((last_index - first_index) - 1);

    T selection[new_size];
    for (int i = 0; i < new_size; i++)
    {
        selection[i] = _array[first_index + i];
    }

    return *(new Vector<T>(selection, new_size));
    /* TODO: How am I supposed to clean up this Vector? When will Destructor get called?
    Will it be destructed as operator() exits, thus returning a pointer to an unreserved location? */
}

First off, what's the deal with the parentheses? Just remove them they're cluttering the expression.

    int new_size = ((last_index - first_index) - 1);

Second, you are allocating a possibly huge amount of data on the stack:

 T selection[new_size];

This can cause the program to crash with a stack overflow if the stack isn't large enough.

And finally here:

    return *(new Vector<T>(selection, new_size));
    /* TODO: How am I supposed to clean up this Vector? When will Destructor get called?
    Will it be destructed as operator() exits, thus returning a pointer to an unreserved location? */

you are correct that you will not be able to clean up this and you will leak memory.

To see why, we need to look close at the function signature. When you have a function that returns X by value (as opposed to by reference) like:

X foo(){
   X x;
   ....
   return x;
}

and later call:

X myX = foo();

then there is some behind the scenes action going on. In the assignment myX = foo() semantically myX will first be default constructed and then the copy assignment operator (operator =) will be called with the return value of foo() which is a temporary object. I don't remember the exact rules but in some (most?) cases the compiler is allowed to change the above to a copy construction, as if you'd have written X myX(foo());.

(hidden temporary) = foo();
X myX;
myX = (hidden temporary);

In reality it isn't so bad, the compiler can do all kinds of fancy optimizations to avoid this copy. Like copy elison for example.

At any rate in your code:

T selection[new_size];
for (int i = 0; i < new_size; i++){
    selection[i] = _array[first_index + i];
}
return *(new Vector<T>(selection, new_size));

what happens is that you allocate a large buffer on the stack, copy the contents onto the stack. Then create a new vector object on the heap, and copy from the stack to the heap. You dereference this new vector and return the reference. But as the return type is a value type, not a reference type you will call the copy constructor with the reference, copy the contents a third time and then return that copy by value.

What the compiler will do for your code is the following:

Vector<T>* t = new Vector<T>(selection, new_size);
Vector<T>& r = *t;
Vector<T> copy(r); 
return copy;

And as t is never deleted you will leak memory. But the leak is inside of this function and the user cannot and must not delete the returned object as it is not dynamically allocated, it's a temporary object on the stack.

You should implement the function like this instead:

template <class T>
Vector<T> Vector<T>::operator() (int first, int last) const
{
    int first_index = first - _index_offset;
    int last_index = last - _index_offset;
    int new_size = ((last_index - first_index) - 1);

    // What should the offset of the copy be?
    // A constructor that allows creation with a reserved size would be nice.
    Vector<T> copy;
    for (int i = 0; i < new_size; i++){
        copy += _array[first_index + i];
    }    
    return copy;
}

Note that this forces repeated growth of the copy because you do not have a constructor that can specify the capacity of the vector.

Don't print from a container!

Printing error messages is not the responsibility of a container. If the error is critical and indicates a problem then you should throw an exception instead. Throwing an exception will allow your program to choose how to handle the error. You will also be able to let your debugger break on exceptions and catch the error easier. Not to mention that it is also poor from a testing perspective to print errors like that.

template <class T>
void Vector<T>::Delete (const int i)
{
    int index = i - _index_offset;

    if (0 <= index && index < _length)
    {
        _length--;

        for (int i = index; i < _length; i++)
        {
            _array[i] = _array[i+1];
        }

        if (_size >= _length * 2)
        {
            Halve();
        }
    } else std::cerr << "Error - Vector<T>::Delete(const int i): i cannot be less than 0, or greater than or equal to Vector._length" << std::endl;
}

I'm going to have to cut myself short here, this review is long enough as it already is and I think I've covered the big picture.

Final words

I do like the fact that you put curly braces ({}) even when they are not needed. This is a good habit. And while it is good that you use white space in the code to make it readable I think that too much white space is also bad for readability as I have to scroll a lot.

For this reason I would consider removing some of the empty lines, and personally I prefer to attach the opening curly brace on the end of the previous line as this saves an otherwise empty line and makes me have to scroll less.