9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ By tagging C++11, are you targeting C++11? \$\endgroup\$ – L. F. Jun 5 at 8:33
  • \$\begingroup\$ yes I must. Although, I cant figure out if there would be any change in my code if I use C++11 or C++ 14? \$\endgroup\$ – MFCDev Jun 5 at 8:36
  • \$\begingroup\$ Your code doesn't even compile. Your Vector::operator[] return a vector&. Your insert is empty and uses an undefined type iterator. You have a data member and a member function sharing the same name size. Your destructor is ~vector instead of ~Vector. And there are a lot of compile errors left. \$\endgroup\$ – L. F. Jun 5 at 8:38
  • 5
    \$\begingroup\$ Code Review reviews working code. Fix the errors, do some tests, and try your best to ensure that your code is working. \$\endgroup\$ – L. F. Jun 5 at 8:43
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Jun 6 at 11:03
12
\$\begingroup\$
  1. You tagged , but your code is not at all C++11. You have no move constructor and no brace-initializers. 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 constructor.

  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++, when both do the same thing. See Difference between i++ and ++i in a loop?.

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

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

    Can be replaced by

    std::copy(v.arr, 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 makes no sense at all. 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].

\$\endgroup\$
  • 3
    \$\begingroup\$ I highly doubt that 3. is still a major concern for modern compilers. At least in the example I checked on godbolt (link), the generated assembly is the same for pre- and post-increment. \$\endgroup\$ – AlexV Jun 5 at 9:49
  • 4
    \$\begingroup\$ @AlexV "This is mainly only a problem when the variable being incremented is a user defined type with an overridden ++ operator. For primitive types (int, etc) there's no performance difference. But, it's worth sticking to the pre-increment operator as a guideline unless the post-increment operator is definitely what's required." — Scott Langham \$\endgroup\$ – L. F. Jun 5 at 9:50
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks. These are good suggestions too. I have not used move ctor or assignment operator ever before so I did not know it's usage. One question: Do I need to have both move and copy constructor in the Vector class? As well as both move assignment and copy assignment operator? \$\endgroup\$ – MFCDev Jun 5 at 17:47
  • \$\begingroup\$ It doesn't make much sense to have a defined assignment operator without the corresponding constructor - they are normally implemented as a pair. You may find it easiest to implement the move constructor and assignment operator using a swap() member - most decent tutorials will demonstrate that, so I won't elaborate further. \$\endgroup\$ – Toby Speight Jun 5 at 20:43

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.