Segmentation fault - new and delete have been used. Lots of arrays are being created during runtime (unbounded array)

Question

I'm trying to implement an unbounded array: What is an unbounded array?

More details on this page: http://www.cs.cmu.edu/~fp/courses/15122-s11/lectures/12-ubarrays.pdf

This is the code:

#include <iostream>
#include <cstdlib>

using namespace std;

class UBArray
{
public:

    int *arr, *arrN, j, *pos; //Initial array is arr. The position of arr is stored in pos. arrN is the new array created when size = limit.
    int size, limit; //size is the current size of the array and limit is the total size available untill a new array is created.

    UBArray()
    {
        size = 0;
        limit = 10;
        arr = new int[10];
        pos = arr;
    }

private:

    void increment()
    {
        // New array arrN is created and then the values in the old arrays is put into the new array.
        // Limit is increased by 10 - this is the extra space the new array contributres.
        // pos which carries the address of the current array now carries the address of the new array.
        // Later when a new array is created its address will be on the heap which is empty. This address is replace the address stored
        // in the arrN. The older array can still be accessed for the array updation process by using the variable pos.

        // IMPORTANT: I had initially tried to delete the older array to space space but while trying to debug the segmentation fault, I have
        // removed it. I will be adding it again once the error has been fixed.

        arrN = new int[size + 10];
        for (j = 0; j < size; j++)
        {
            arrN[j] = pos[j];
        }
        limit = limit + 10;
        pos = arrN;
    }

public:

    void push(int n)
    {
        if (size<limit)
        {
            size++;
            pos[size-1]=n;
        }
        else
        {
            increment();
            push(n);
        }
    }
    int pop()
    {
        int p = pos[size-1];
        size--;
        return p;
    }
};


int main()
{
    UBArray array;
    int num;
    cout << "Enter 36 elements: ";
    for (int k = 0; k<36; k++)
    {
        cin >> num;
        array.push(num);
    }
    cout <<  endl << "The last element is : " << array.pop();
}

I have tried to give comments in the code to make it understandable to the reader. I'm copying some of it here:

Initial array is arr. The position of arr is stored in pos. arrN is the new array created when size = limit.

size is the current size of the array and limit is the total size available until a new array is created.

New array arrN is created and then the values in the old array are put into the new array.

Limit is increased by 10 - this is the extra space the new array contributres.

pos which carries the address of the current array now carries the address of the new array.

Later when a new array is created its address will be on the heap which is empty. This address is replaced the address of arrN. The older array can still be accessed for the array updation process by using the variable pos which will be updated by the old values have been copied to the new one.

I get segmentation fault during execution. I have tried to use cout statements to debug the code but it seems really confusing. I could see loops both inside and outside the for loop inside the increment method. I'm unable to figure out much. Any help is appreciated.

UPDATE: As pointed out by jrok, I changed the code and the seg fault is gone. But I'm getting seg fault again at the creation of the 3rd array.

UPDATE 2 Everything fixed now. Thank you.

Answer 1

arr = new int(10*sizeof(int));

That creates a single int, initialized to the value of 10*sizeof(int). The loop you wrote right after this statement runs out of bounds and it's cause of segmentation fault.

What you want is the array form of new:

arr = new int[10]; // note 10 only, new expression knows the size
                   // of the type it allocates

Note that when you assign the pointer to the new array to the pointer to the old array you lose the handle to it and create a memory leak:

int* arr = new int[10];
int* new_arr = new  int[20];
arr = new_arr;  // original array at arr has leaked

You need to delete[] arr before you reassign it. Also, I see no use for the third (pos) pointer. Not even for arrN, for that matter. One will do. Create a local pointer inside increment and assign it to arr when you're done deallocating the old array.

Finally, what people have been telling you in the comments, unless this is a learning exercise, don't try to reinvent the wheel and use std::vector instead.

Answer 2

An unbounded array only needs 3 data members (rather than 6): the address of the beginning of the data buffer, the capacity of the buffer, and the actual size (of the part of the buffer used so far). When expanding, you will temporarily need to hold the address of the new buffer in an automatic variable. Also, you should avoid leaking the memory of previous buffers. A simple layout is like this:

struct ua
{
  int size,capacity,*buff;                   // 3 data members only
  ua(int n)                                  // constructor: n = initial capacity
  : size(0)                                  //   initially empty
  , capacity(n<0?0:n)                        //   guard against n<0
  , buff(capacity?new int[capacity]:0) {}    //   only allocate if n>0
  ~ua() { delete[] buff; }                   // destructor: note: delete[] 0 is ok
  void empty() const { return size==0; }     // is array empty?
  void push(int x)                           // add another datum at back
  {
    if(size==capacity) {                     //   buffer is full: we must expand
      if(capacity) capacity+=capacity;       //     double capacity
      else capacity=1;                       //     but ensure capacity>0
      int*nbuff=new int[capacity];           //     obtain new buffer
      if(size)
        memcpy(nbuff,buff,size*sizeof(int)); //     copy data from old to new buffer
      delete[] buff;                         //     free memory form old buffer
      buff=nbuff;                            //     set member buff to new buffer
    }
    buff[size++]=x;                          //   write; increment size (post-fix)
  }
  int pop()                                  // ill-defined if empty()
  { return buff[--size]; }                   //   read; decrement size (pre-fix)
  int operator[](int i) const                // ill-defined if i<0 or i>=size
  { return buff[i]; }
  int&operator[](int i)                      // ill-defined if i<0 or i>=size
  { return buff[i]; }

  // you may add more functionality, for example:
  void shrink();                             // reduces capacity to size
  void reserve(int n);                       // extends capacity to n, keeping data
  ua(ua const&other);                        // copy buffered data of other
  void swap(ua&other);                       // swap contents with other (no copying!)
};