new int[] throws 'Access Violation' exception

Question

I've been working on custom Vector class. Everything works perfectly fine on Microsoft compiler, however when I try it on Borland I'm getting a really strange error.

Borland throws the exception inside the insert function; Exactly when calling the copy constructor "Vector temp(*this);" at the

"array_ = new int[rhs.size_];" line

void Vector::insert(int value, unsigned position) throw(SubscriptError)
{
    check_bounds(position);
    Vector temp(*this);
    int tmpSize= size_;
    temp.size_++;
    size_++;
    for (unsigned int i=tmpSize; i > position; i--)
    {
        temp[i] = temp[i-1];
    }
    temp[position] = value;

   //array_= temp.array_;
    for(unsigned int i = 0; i < size_; i++)
    {
        array_[i]= temp.array_[i];
    }
}

and here is my copy constructor;

Vector::Vector(const Vector& rhs)
{
    array_ = new int[rhs.size_];
    size_ = rhs.size_;
    for(unsigned int i = 0; i < rhs.size_; i++)
    {
        array_[i] = rhs.array_[i];
    }
}

and finally this is the main();

 std::cout << "push_back 5 integers:\n";
 for (int i = 0; i < 5; i++)
 {
  a.push_back(i);
   Print(a);
 }

std::cout << "insert(99, 3):\n";
a.insert(99, 3);
Print(a);
std::cout << "insert(98, 0):\n";
a.insert(98, 0);
Print(a);
std::cout << "insert(97, 6):\n";
a.insert(97, 6);
Print(a);

The strange thing is first insert call(a.insert(99, 3)) works fine, it crashes when it comes to the second call(a.insert(98, 0))

Here's the full header file

namespace CS170
 {
    class SubscriptError
    {
     public:
       SubscriptError(int Subscript) : subscript_(Subscript) {};
       int GetSubscript(void) const { return subscript_; }

     private:
    int subscript_;
    };

class Vector
{
public:

    static const int NO_INDEX = -1;

    struct SortResult
    {
        unsigned compares;
        unsigned swaps;
    };

    // Default constructor
    Vector(void);

    // Destructor
    ~Vector();

    // Copy constructor
    Vector(const Vector& rhs);

    // Constructor to create a Vector from an array
    Vector(const int array[], unsigned size);

    // Adds a node to the front of the list
    void push_back(int value);

    // Adds a node to the end of the list
    void push_front(int value);

    // Removes the last element. Does nothing if empty.
    void pop_back(void);

    // Removes the first element. Does nothing if empty.
    void pop_front(void);

    // Inserts a new node at the specified position. Causes an
    // abort() if the position is invalid. (Calls check_bounds)
    void insert(int value, unsigned position) throw(SubscriptError);

    // Removes an element with the specified value (first occurrence)
    void remove(int value);

    // Deletes the underlying array and sets size_ to 0
    void clear(void);

    // Return true if the vector is empty, otherwise, false
    bool empty(void) const;

    // Assignment operator
    Vector& operator=(const Vector& rhs);

    // Concatenates a vector onto the end of this vector.
    Vector& operator+=(const Vector& rhs);

    // Concatenates two Vectors.
    Vector operator+(const Vector& rhs) const;

    // Subscript operators.
    int operator[](unsigned index) const throw(SubscriptError);
    int& operator[](unsigned index) throw(SubscriptError);

    // Returns the number of elements in the vector.
    unsigned size(void) const;

    // Returns the size of the underlying array
    unsigned capacity(void) const;

    // The number of memory allocations that have occurred
    unsigned allocations(void) const;

    // This searches the vector using a binary search instead
    // of a linear search. The data must be sorted. Returns
    // the index. If not found, returns CS170::Vector::NO_INDEX.
    // DO NOT SORT THE DATA IN THIS FUNCTION!!    
    int bsearch(int value) const;

    // Sorts the elements using a selection sort. 
    // Returns the number of swaps/comparisons that occurred.
    SortResult selection_sort(void);

    // Sorts the elements using a bubble_sort.
    // Returns the number of swaps/comparisons that occurred.
    SortResult bubble_sort(void);

    void swap(int &a, int& b);

    void swapv(Vector &other);

    void reverse(void);

    bool operator==(const Vector& rhs) const;

    void shrink_to_fit(void);

private:
    int *array_;        // The dynamically allocated array
    unsigned size_;     // The number of elements in the array
    unsigned capacity_; // The allocated size of the array
    unsigned allocs_;   // Number of allocations (resizes)

    // Private methods...
    void check_bounds(unsigned index) const throw(SubscriptError);
    void grow(void);

    // Other private methods...
};

   }// namespace CS170

        #endif // VECTOR_H

Answer 1

You are not (visibly) resizing array_ inside insert(). This means that you will always write one element past the end of its allocated memory.

Copying the entire array (twice) makes for a very expensive insertion. What are you trying to achieve that can't be done in std::vector?

Answer 2

In my opinion, damage is done when you call the insert() for the first time. When you insert an element, you also have to increase the allocated bytes to your member array_. You are simply increasing the size_, but what about increasing the size of actual array_ ?

For example, something like below is happening in your insert():

int size = 5;
int *p = new int[size];
// ... populate p[i] (i = 0 to i = size - 1)
size ++;
p[size - 1] = VALUE; // oops ... incremented 'size' but before that reallocate to 'p'

After calling, first insert your stack will be already corrupt. So 2nd time it's crashing. Just verify with according code changes.

On side note,

• I feel that you can write insert(), more optimized. I don't feel need to copy the full Vector<> in temporary.
• Also, try to allocate more number of bytes to array_ than actual need. So that you don't have to reallocate many times
• Try seeing the source code of actual vector from STL for better efficiency.

Answer 3

In your insert function you don't allocate memory for the newly inserted item and after the first insert the copy ctr tries to read unallocated memory on the line it is throwing the exception. The solution would be to allocate more memory initially (that's why capacity is used for typical vector implementations) or to increase the allocated array on every insert. You have to implement the reallocation on both solutions but in the first one it will be called less often.