Having Trouble With Two Functions In An Implementation of Vector in C++

Question

I wrote an implementation of vector, which compiles but is not working properly according to the test main() program I was given.

I'm sure the error is in my push_back() function or my reserve() function but I'm not sure what exactly it is that's wrong.

Can someone please look through the two functions and tell me if something is missing or needs to be changed?

#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
#include <cstring>



// Vector.h

using namespace std;

template <class T>
class Vector
{
public:

   typedef T * iterator;

   Vector();
   Vector(unsigned int size);
   Vector(unsigned int size, const T & initial);
   Vector(const Vector<T> & v);           // copy constructor//Done
   ~Vector();

   unsigned int capacity() const;         // return capacity of vector (in elements)//Done
   unsigned int size() const;             // return the number of elements in the vector//Done
   bool empty() const;

   iterator begin();                      // return an iterator pointing to the first element // Done
   iterator end();                        // return an iterator pointing to one past the last element //Done
   T & front();                           // return a reference to the first element //Done
   T & back();                            // return a reference to the last element //Done
   void push_back(const T & value);       // add a new element //Done
   void pop_back();                       // remove the last element //Done

   void reserve(unsigned int capacity);   // adjust capacity //Done
   void resize(unsigned int size);        // adjust size //Done

   T & operator[](unsigned int index);    // return reference to numbered element
   Vector<T> & operator=(const Vector<T> &);

private:
   unsigned int my_size;
   unsigned int my_capacity;
   T * buffer;
};

template<class T>//
Vector<T>::Vector()
{
    my_capacity = 0;
    my_size = 0;
    buffer = 0;
}

template<class T>
Vector<T>::Vector(const Vector<T> & v)
{
    my_size = v.my_size;
    my_capacity = v.my_capacity;
    buffer = new T[my_size]; 
    for (int i = 0; i < my_size; i++)
        buffer[i] = v.buffer[i];  
}

template<class T>//
Vector<T>::Vector(unsigned int size)
{
    my_capacity = size;
    my_size = size;
    buffer = new T[size];
}

template<class T>//
Vector<T>::Vector(unsigned int size, const T & initial)
{
    my_size;
    my_capacity = size;
    buffer = new T [size];
    for (int i = 0; i < size; i++)
        buffer[i] = initial;
}

template<class T>//
Vector<T> & Vector<T>::operator = (const Vector<T> & v)
{
    delete[ ] buffer;
    my_size = v.my_size;
    my_capacity = v.my_capacity;
    buffer = new T [my_size];
    for (int i = 0; i < my_size; i++)
        buffer[i] = v.buffer[i];
    return *this;
}

template<class T>//
typename Vector<T>::iterator Vector<T>::begin()
{
    return buffer;
}

template<class T>//
typename Vector<T>::iterator Vector<T>::end()
{
    return buffer + size();
}

template<class T>//
T& Vector<T>::Vector<T>::front()
{
    return buffer[0];
}

template<class T>//
T& Vector<T>::Vector<T>::back()
{
    return buffer[size - 1];
}

template<class T>
void Vector<T>::push_back(const T & v)
{
    if (my_size >= my_capacity)
    reserve(my_capacity +5);
    buffer [my_size++] = v;
}

template<class T>//
void Vector<T>::pop_back()
{
    my_size--;
}

template<class T>//
void Vector<T>::reserve(unsigned int capacity)
{
    if(buffer == 0)
    {
        my_size = 0;
        my_capacity = 0;
    }    
    if (capacity <= my_capacity)
    return;
    T * new_buffer = new T [capacity];
    assert(new_buffer);
    copy (buffer, buffer + my_size, new_buffer);
    my_capacity = capacity;
    delete[] buffer;
    buffer = new_buffer;

}

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

template<class T>//
void Vector<T>::resize(unsigned int size)
{
    reserve(size);
    my_size = size;
}

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

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

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

int main()
{  

   Vector<int> v;

   v.reserve(2);
   assert(v.capacity() == 2);

   Vector<string> v1(2);
   assert(v1.capacity() == 2);
   assert(v1.size() == 2);
   assert(v1[0] == "");
   assert(v1[1] == "");

   v1[0] = "hi";
   assert(v1[0] == "hi");

   Vector<int> v2(2, 7);
   assert(v2[1] == 7);

   Vector<int> v10(v2);
   assert(v10[1] == 7);

   Vector<string> v3(2, "hello");
   assert(v3.size() == 2);
   assert(v3.capacity() == 2);
   assert(v3[0] == "hello");
   assert(v3[1] == "hello");

   v3.resize(1);
   assert(v3.size() == 1);
   assert(v3[0] == "hello");

   Vector<string> v4 = v3;
   assert(v4.size() == 1);
   assert(v4[0] == v3[0]);
   v3[0] = "test";
   assert(v4[0] != v3[0]);  
   assert(v4[0] == "hello");

   v3.pop_back();
   assert(v3.size() == 0);

   Vector<int> v5(7, 9);
   Vector<int>::iterator it = v5.begin();
   while (it != v5.end())
   {
      assert(*it == 9);
      ++it;
   }

   Vector<int> v6;
   v6.push_back(100);
   assert(v6.size() == 1);
   assert(v6[0] == 100);
   v6.push_back(101);
   assert(v6.size() == 2);
   assert(v6[0] == 100);
   v6.push_back(101);

   cout << "SUCCESS\n";
}

Answer 1

I think that your problem is in this code:

template<class T>//
Vector<T>::Vector(unsigned int size, const T & initial)
{
    my_size;
    my_capacity = size;
    buffer = new T [size];
    for (int i = 0; i < size; i++)
        buffer[i] = initial;
}

Notice that this first line

my_size;

has no effect. I think you meant to write

my_size = size;

When I did this on my machine, it resolved the problem and all the tests pass. Valgrind confirms no leaks or memory corruption.

However, there are a few other parts of this code you might want to look into. Here's a quick checklist of things to look into:

1. In your code for reserve, you allocate a buffer by writing T* new_buffer = new T[capacity], and then use assert to confirm that the buffer is non-NULL. In C++, when you allocate memory with new or new[], you will never get back a NULL pointer; instead, the program will throw a bad_alloc exception if the allocation fails. You can explicitly request that you get memory in a way that never throws an exception, but that's probably not what you want to do here.

2. You have a one-argument constructor Vector(unsigned int size) that is not marked explicit. This means that C++ will treat it as an implicit conversion constructor and will let you write code like Vector<int> v = 137;, since the compiler will interpret this as Vector<int> v(137). This is probably not what you intended, so I'd suggest marking the constructor explicit to disallow this behavior.

3. Your code for ensuring that sufficient space exists in the Vector is valid, but your growth strategy is not very efficient. In particular, if you keep growing the vector five elements at a time, then the time required to do n push_backs will be O(n²), which is not very good. A more common strategy is to double the size of the vector when you need space. Using an amortized analysis, you can show that this means that n insertions take only O(n) time, which is substantially better than your current approach.

4. Your assignment operator (operator =) contains a bug that will result in undefined behavior if you assign a vector to itself by writing something like v = v. The reason for this is that your assignment operator delete[]s the buffer, then tries to copy from the other object. However, if the other object is identically the same as your own object, then you'll be trying to read out of the pointer just deleted. To fix this, you might want to surround your code in operator= with a check if (this != &v). This means that if you ever try assigning the Vector to itself, it will no-op instead of failing at runtime.

Hope this helps!

Answer 2

I haven't tried debugging your code to verify, but at a glance push_back and reserve look fine for your purposes (I assume you don't care about exception safety or destroying removed objects at the appropriate/expected time).

However, I see a few glaring logic problems in the implementations of:

• template<class T> Vector<T>::Vector(const Vector<T> & v) and template<class T> Vector<T> & Vector<T>::operator = (const Vector<T> & v): what happens when a default constructed and empty Vector is copied/assigned?
• template<class T> Vector<T>::Vector(unsigned int size): what happens when size == 0?
• template<class T> Vector<T>::Vector(unsigned int size, const T & initial): same as above, and my_size; as a standalone statement seems quite wrong
• resize: resize should shrink the Vector (reduce its capacity), reserve doesn't

Answer 3

At a first glance this line my_size; in Vector<T>::Vector(unsigned int size, const T & initial) strike me as very odd. You probably meant it to be my_size = size;