Implementation of Vector in C++

Question

I recently wrote an implementation of STL Vector as a programming exercise. The program compiles but I receive a strange error saying:

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

I've never come up with this error before and am not sure what exactly should be changed within my implementation to make it function correctly.

Can someone take a look through my code and see if anything jumps out at them as wrong in this specific case? Sorry I can't be more specific, I'm not sure where to look myself, thanks in advance.

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

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);      
   ~Vector();

   unsigned int capacity() const;
   unsigned int size() const;
   bool empty() const;
   iterator begin();
   iterator end();
   T & front();
   T & back();
   void push_back(const T & value); 
   void pop_back();  

   void reserve(unsigned int capacity);   
   void resize(unsigned int size);   

   T & operator[](unsigned int index);  
   Vector<T> & operator=(const Vector<T> &);

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

// Your code goes here ...
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-size;
    my_capacity = size;
    buffer = new T [size];
    for (int i = 0; i < size; i++)
        buffer[i] = initial;
        T();
}

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;
    }    
    T * buffer = new T [capacity];
    assert(buffer);
    copy (buffer, buffer + my_size, buffer);
    my_capacity = capacity;
    delete[] buffer;
    buffer = 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);
    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";
}

You should run your program with a debugger so you can see where that exception is raised. — tibur, Mar 01 '11 at 19:04
can you narrow down the line in main() after which you get the error? — Dan, Mar 01 '11 at 19:06
I'd suggest you create a unit test for at least each method. — ronag, Mar 01 '11 at 19:14
on `Vector::Vector(unsigned int size, const T & initial)` Whats that `T()` you have over there ? — , Mar 01 '11 at 19:18

score 26 · Answer 1 · edited Dec 26 '14 at 03:39

Here is the complete source code, updated from your source:

    #pragma once


//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);      
    ~Vector();

    unsigned int capacity() const;
    unsigned int size() const;
    bool empty() const;
    iterator begin();
    iterator end();
    T & front();
    T & back();
    void push_back(const T & value); 
    void pop_back();  

    void reserve(unsigned int capacity);   
    void resize(unsigned int size);   

    T & operator[](unsigned int index);  
    Vector<T> & operator=(const Vector<T> &);
    void clear();
private:
    unsigned int my_size;
    unsigned int my_capacity;
    T * buffer;
};

// Your code goes here ...
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 (unsigned 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 = size;
    my_capacity = size;
    buffer = new T [size];
    for (unsigned int i = 0; i < size; i++)
        buffer[i] = initial;
    //T();
}

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 (unsigned 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>::front()
{
    return buffer[0];
}

template<class T>
T& Vector<T>::back()
{
    return buffer[my_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;
    }    
    T * Newbuffer = new T [capacity];
    //assert(Newbuffer);
    unsigned int l_Size = capacity < my_size ? capacity : my_size;
    //copy (buffer, buffer + l_Size, Newbuffer);

    for (unsigned int i = 0; i < l_Size; i++)
        Newbuffer[i] = buffer[i];

    my_capacity = capacity;
    delete[] buffer;
    buffer = Newbuffer;
}

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;
}
template <class T>
void Vector<T>::clear()
{
    my_capacity = 0;
    my_size = 0;
    buffer = 0;
}

`return buffer[size-1];` should be `return buffer[my_size-1];` in the `T& Vector::back()` method. — Fredrick Gauss, Mar 10 '13 at 15:00
`pop_back` should make sure to release any resources that last element was having, otherwise you're doom to a memory leak. Make it `buffer[my_size]->~T(); --my_size;` — Nelson Vides, Dec 05 '18 at 13:06
should the clear() function call the destructor of all the elements to prevent memory leak? — olu, Dec 17 '22 at 12:07
Assignment operator is incorrect. You are potentially setting the capacity to something higher than what you are actually allocating. — OTheDev, Feb 05 '23 at 07:37

score 2 · Answer 2 · answered Apr 26 '12 at 01:53

This code didn't compile for me. Clang complained that line 114 (the implementation of back() ) expected "size" to be called.

I think the line was intended to be "return buffer[size() -1];"

It also gives warnings about the implementation of this constructor: template Vector::Vector(unsigned int size, const T & initial)

The first line was probably supposed to be "my_size = size;" The last line (of this constructor) should probably be deleted.

Next it fails the assertion at line 209: assert(v3.size() == 1);

This opens quite a can of worms, but the obvious problem is in resize() at the line: "size = size;" which is probably meant to be "my_size = size;"

With this change we now crash on line 121 which is in push_back() called from line 231 "v6.push_back(100);"

This is failing because of problems in reserve(). We are creating a local variable "buffer" with the same name as a member variable. Let's change the name to temp_buffer. Note: Do not assert() run time errors. assert() is for logic errors. This assert() cannot fail. new will never return 0. It will throw instead.

After making the obvious fixes in reserve() (there are other issues), we are now crashing in the copy() in reserve() in the call from resize() called from lin3 208 in main(), "v3.resize(1);".

We see that reserve is actually allocating a new buffer when we are reducing capacity. This is both a loss of performance and a loss of reliability (memory allocation can fail). But we should still not crash, so we'll try to prevent the crash without addressing the obvious design flaw.

The crash is coming because we are copying all of the items that exist in the container into the newly allocated array. This would be correct if we were only do this when we need to increase our capacity, but in this case, we have more items than our new capacity can hold. The code should set my_size to the new capacity if it was greater than that value.

Now the test code reports "SUCCESS."

However there are still many issues with this code.

One of the biggest issues is that we are not using uninitialized memory in the allocated array. Doing this is required by the standard for std::vector and it has both performance and reliability advantages. But it also complicates the code and so this may be a shortcut we can live with for what is obviously an intellectual exercise.

Constructors: Use initializer syntax to initialize data members.

With your copy constructor and your constructor from initial value, you'll leak the allocated array if any of your looped assignments throw an exception.

The assignment operator should allocate a new buffer of size "my_capacity" not "my_size" although there is an obvious optimization that if the size of the right-hand-side object is not greater than the "this" object, we shouldn't be allocating at all.

If allocating the new array fails in the assignment operator, we've already deleted the buffer, so we will eventually (when our Vector object is destroyed) have a double delete of the buffer and we may have all hell breaking loose before then.

In push_back(), in order to support the performance guarantees of the standard, we need to increase capacity by some constant fraction of the size of the existing capacity. For example something like: "reserve(my_capacity * 1.5);"

score 2 · Answer 3 · answered Mar 01 '11 at 19:04

2

Maybe it's this typo?

Vector<T>::Vector(unsigned int size, const T & initial)
{
    my_size-size;

answered Mar 01 '11 at 19:04

Mark Ransom

299,747
42
398
622

@ Mark Ransom, no, that still leaves me with the same error. Thanks though, that was wrong. – UndefinedReference Mar 01 '11 at 19:06
@Meursault: There's also a `size = size;` in `resize` that should probably be `my_size = size;`. And `buffer = buffer;` in `reserve` that should be `this->buffer = buffer;`. – casablanca Mar 01 '11 at 19:09

score 2 · Answer 4 · answered Mar 01 '11 at 19:07

2

Your "reserve" is broken. Use another variable name for the local buffer.

answered Mar 01 '11 at 19:07

Erik

88,732
13
198
189

1

to be more clear, you never set the this.buffer because your local variable is named buffer. So you never actually reserve space but you keep leaking memory on each call to reserve. – Kevin Mar 01 '11 at 19:11

score 2 · Answer 5 · answered Mar 01 '11 at 19:29

In addition to needing to fix your reserve function, your copy-constructor and copy-assignment-operator have an interesting problem:

Vector<T> t1 = t2;

This will set the capacity of t1 equal to the capacity (variable) of t2, but the actual capacity of t1 will be the size of t2; Thus, as you start pushing elements onto the vector after the copy-constructor/assignment-operator, you'll have a buffer overrun problem.

You need to change it to

template<class T>
Vector<T>::Vector(const Vector<T> & v)
{
    my_size = v.my_size;
    my_capacity = v.my_capacity;
    buffer = new T[my_capacity];
    memcpy(buffer, v.buffer, my_size * sizeof(T));  
}

OR (if you want to allow it to resize to a smaller array)

template<class T>
Vector<T>::Vector(const Vector<T> & v)
{
    my_size = v.my_size;
    my_capacity = v.my_size;
    buffer = new T[my_size];
    memcpy(buffer, v.buffer, my_size * sizeof(T));  
}

Should you be using `memcpy` there? – Paul Sanders May 11 '22 at 08:35 — Paul Sanders, May 11 '22 at 08:35

Implementation of Vector in C++

5 Answers5

Linked