Implement Own Vector Class in C++

Question

I am preparing for an interview and came to know about this question: implement a vector class in C++. I thought of how I would write it an interview and included the code below. The things I know I did not cover already are: 1) No use of templates for different data types 2) No use of iterators for iterating. My point is I wanted to write a simple code and I want to know if that would be sufficient to crack the interview round or not? Can you please go through the below code and point out the things that I must cover from an interview perspective. Thanks.

class Vector{
        int capacity;
        int sizet;
        int *arr;
    public:
        Vector():capacity(0),sizet(0),arr(new int){}
        Vector(int size):capacity(size),sizet(size),arr(new int[sizet]()){}
        Vector(const Vector &v){            //copy ctor 
                capacity = v.capacity;
                sizet = v.sizet;
                arr = new int[sizet];
            for(int i=0;i<sizet;i++)
                arr[i] = v.arr[i];

        }
        int &operator [](int index){            //overloading index[] operator
            return arr[index];
        }
        Vector &operator==(const Vector& v){        //overloading assignment operator
        if(this != v){
                capacity = v.capacity;
                sizet = v.sizet;
                arr = new int[sizet];
            for(int i=0;i<sizet;i++)
                arr[i] = v.arr[i];
            }
            return *this;
        }
        void push_back(int elem){
            if(sizet == capacity){
                if(capacity ==0)
                    capacity++;
                else
                    capacity = 2*capacity;
            }
            arr[sizet++]=elem;
        }
        void pop_back(){
            sizet--;
        }
        void insert(iterator it,int size=1,int val=0){

        }
        int size(){
            return sizet;
        }
        void resize(int n){
        if(sizet < n){                  //if increasing the size
            for(int i=sizet;i<n;i++)
                arr[sizet++]=0;
        }
        else                            //decreasing the size
            sizet = n;
        }
        int at(int index){
            return arr[index];
        }
        int front(){
            return arr[0];
        }
        int back(){
            return arr[sizet];
        }

        ~Vector(){              //dtor
        delete arr[];
        }
    };

Edit: Resolved the naming conflict as was suggested.

Answer 1

1. You tagged c++11, but your code does not look like C++11. You do not implement move construction and move assignment. You should implement them. Here's a sample implementation using the copy-and-swap idiom.

   friend void swap(Vector& a, Vector& b)
   {
       using std::swap;
       swap(a.capacity, b.capacity);
       swap(a.sizet, b.sizet);
       swap(a.arr, b.arr);
   }
   
   Vector(Vector&& v)
       :Vector{}
   {
       swap(*this, v);
   }
   
   Vector& operator=(Vector v)
   {
       swap(*this, v);
       return *this;
   }
   

   This way, you don't have to define a separate copy assignment operator.

2. Your default constructor sets arr to new int. This makes no sense and cannot be handled by the destructor. You should set arr to nullptr.

3. Use ++i, not i++, in discarded-result expressions. See Difference between i++ and ++i in a loop?.

4. Consider using standard algorithms instead of hand-crafted loops when plausible. For example:

   for (int i = 0; i < sizet; i++)
       arr[i] = v.arr[i];
   }
   

   Can be replaced by

   std::copy_n(v.arr, sizet, arr);
   

   You will need to #include <algorithm> for this to work.

5. Your copy constructor uses assignment instead of member initializer clauses. You should use member initializer clauses uniformly. Now your copy constructor should look like this:

   Vector(const Vector& v)
       :capacity{v.capacity},
        sizet{v.sizet},
        arr{new int[v.sizet]} // to avoid dependence on member declaration order
   {
       std::copy(v.arr, v.arr + sizet, arr);
   }
   

6. Where is the const overload for operator[], at, front, and back?

7. Your push_back is incorrect. It does not allocate any memory. You will get an out-of-range error when capacity exceeds the actual capacity. Same applies to resize.

8. size() should be const.

9. Your at does the same job as operator[]. at should check for out-of-range errors and raise an exception if index >= sizet.

10. front and back should return a reference instead of a value.

11. The implementation of back is wrong. It should return arr[sizet - 1].

Answer 2

It's great that you provide a test program. Although it doesn't yet test very much, running it under Valgrind uncovers a few wild accesses:

==17803== Invalid write of size 4
==17803==    at 0x109773: Vector::resize(int) (221707.cpp:68)
==17803==    by 0x10938A: main (221707.cpp:103)
==17803==  Address 0x4d74c94 is 0 bytes after a block of size 20 alloc'd
==17803==    at 0x483650F: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17803==    by 0x109508: Vector::Vector(int) (221707.cpp:11)
==17803==    by 0x1091FE: main (221707.cpp:92)
==17803== 
==17803== Invalid read of size 4
==17803==    at 0x1093CE: main (221707.cpp:105)
==17803==  Address 0x4d74c98 is 4 bytes after a block of size 20 alloc'd
==17803==    at 0x483650F: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17803==    by 0x109508: Vector::Vector(int) (221707.cpp:11)
==17803==    by 0x1091FE: main (221707.cpp:92)
==17803== 
==17803== Invalid read of size 4
==17803==    at 0x1097FD: Vector::at(int) const (221707.cpp:77)
==17803==    by 0x109406: main (221707.cpp:106)
==17803==  Address 0x4d74ca8 is 20 bytes after a block of size 20 alloc'd
==17803==    at 0x483650F: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17803==    by 0x109508: Vector::Vector(int) (221707.cpp:11)
==17803==    by 0x1091FE: main (221707.cpp:92)
==17803== 

One of the problems is that resize() doesn't allocate new capacity when necessary. In fact, there seems to be quite some confusion between size and capacity throughout the code; size should be the number of objects we're logically storing, and capacity is how many we could store before we need to re-allocate.

When we do re-allocate, I would expect to use standard algorithms (std::move()) to copy the elements from old to new storage; there's no need to hand-code a loop.

I'd advise against writing using namespace - that defeats the very benefits that namespaces were invented to give us.