Segmentation fault error c++ dynamic array

Question

So I'm writing an ArrayList class that internally makes use of an array and a few functions to maintain the capacity (namely the shrink and grow functions). I'm receiving a segmentation fault error, which I know means that I am trying to access memory that I don't have access to, which probably is occurring in my overloaded [] operator, however I can't really seem to figure out what's causing the issue. Any help would be appreciated!

ArrayList.cpp

#include "ArrayList.h"
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int& ArrayList::operator[](unsigned int i){
    try{
        cout << "[] called: i  = " << i << ".........return val = " << foo[i] << endl ; 
        if(i >= numElements)
            throw 1;
        return foo[i];
    }
    catch(int e){
        cout << "An error has occured. Error code " << e;
        switch(e) {
            case 1:{
                            cout << ". You may be trying to access an index that doesn't currently exist in the arraylist!" << endl;
                            break; //1 = IndexOutofBoundException
            }   
        }
    }
}
int ArrayList::size(){
    return numElements;
}
void ArrayList::shrink(){
    int* bar = new int[capacity/2]; //temp array to hold values while I decrease the size
    for(int i = 0; i < capacity/2; i++){
        bar[i] = foo[i];    
    }
    delete foo;
    foo = bar;
    capacity /=2;
}

void ArrayList::grow(){
    int* bar = new int[capacity*2]; //temp array to hold values while I increase the size
    for(int i = 0; i < capacity; i++){
        bar[i] = foo[i];
    }
    for(int i = capacity; i < capacity*2;i++){
        bar[i] = 0;
    }
    delete foo;
    foo = bar;
    capacity *=2;
}

void ArrayList::push_back(int m){
    if(numElements == capacity) //full, double foo
        grow();
    foo[numElements] = m;
    numElements++;
}

void ArrayList::erase(int m){
    bool notFound = true;   
    int i = 0;
    while(notFound){
        if(foo[i] == m){
            notFound = false;    //Ha! Found you!
            for(int j = i; j < capacity; j++){
                foo[j] = foo[j+1]; //moves everything to right of m one spot left
                numElements--;
            }
        }
        else
            i++; //keep looking
    }
    if(numElements*2<capacity)
        shrink();
}

string ArrayList::toString(){
    stringstream sobj;
    string x;
    sobj << "[";
    for(int i = 0; i < numElements; i++){
        if(i == numElements-1) //last iteration, avoids output displaying [1,2,3,4,]
            sobj << foo[i];
        else
            sobj << foo[i] << ",";
    }
    sobj << "]";
    sobj >> x;
    return x;
}

ArrayList::ArrayList(){
    capacity = 1;   
    numElements = 0;
    foo = new int[1];
    foo[0] = 0;
}

ArrayList::~ArrayList(){
    delete foo;
    cout << "Destructor called" << endl;
}

ArrayList.h

#ifndef _ARRAYLIST_H_
#define _ARRAYLIST_H_
#include <string>
class ArrayList
{
 public:
    ArrayList();
    ~ArrayList();

    int& operator[](unsigned int i);

    void push_back(int m); 
    void erase(int m);
    std::string toString();
    int size();

 private: 
  void shrink();
    void grow();

 private:
  int capacity, numElements;
    int* foo;
};

#endif

Test.cpp

#include "ArrayList.h"
#include <iostream>
using namespace std;

int main(int argc,char *argv[])
{
    ArrayList arr;

    for (int i=1;i<=50;i++)
    {
        arr.push_back(i);
    }

    cout << "Should contain numbers 1..50, is ";

    cout << arr.toString() << endl;

    for (int i=arr.size()-1;i>=1;i--)
    {
        arr.erase(arr[i]);
    }   

    cout << "Should contain only 1, is ";
    cout << arr.toString() << endl;

    arr.erase(arr[0]);

    for (int i=2;i<=50;i++)
    {
        if (i<=2)
            arr.push_back(i);
        else
        {
            int j=0;
            while ((j<arr.size()) && (i%arr[j]!=0))
                j++;

            if (j==arr.size())
            {
                arr.push_back(i);
            }
        }
    }

    cout << "Prime numbers between 1 and 50 are: " << arr.toString() << endl;

}

Off the top, you are accessing foo[i] (in order to print it) before i >= numElements check. Further, if an exception is in fact thrown in operator[], control flows off the end of the function without encountering a return statement; that exhibits undefined behavior. — Igor Tandetnik
– Igor Tandetnik, Commented Nov 12, 2015 at 4:35
delete foo What was allocated with new[] should be deallocated with delete[], as in delete[] foo; — Igor Tandetnik
– Igor Tandetnik, Commented Nov 12, 2015 at 4:40

R Sahu · Accepted Answer · 2015-11-12 04:47:20Z

You have an error in the function ArrayList::erase().

void ArrayList::erase(int m){
    bool notFound = true;   
    int i = 0;
    while(notFound){
        if(foo[i] == m){
            notFound = false;    //Ha! Found you!
            for(int j = i; j < capacity; j++){
                foo[j] = foo[j+1]; //moves everything to right of m one spot left

                //========================================
                // Problem.
                // This is in the wrong place.
                // It needs to be outside the for loop.
                //========================================
                numElements--;
            }
        }
        else
            i++; //keep looking
    }
    if(numElements*2<capacity)
        shrink();
}

Fixed function:

void ArrayList::erase(int m){
    bool notFound = true;   
    int i = 0;
    while(notFound){
        if(foo[i] == m){
            notFound = false;    //Ha! Found you!
            for(int j = i; j < capacity; j++){
                foo[j] = foo[j+1]; //moves everything to right of m one spot left
            }

            //========================================
            // It needs to be outside the for loop.
            //========================================
            numElements--;
        }
        else
            i++; //keep looking
    }
    if(numElements*2<capacity)
        shrink();
}

By the way, I was able to quickly identify the problem by adding a line to print the contents of the array immediately after erasing an item.

for (int i=arr.size()-1;i>=1;i--)
{
   arr.erase(arr[i]);
   cout << arr.toString() << endl;
}

A more robust version of the function would be:

void ArrayList::erase(int m){    
   for ( int i = 0; i < numElements; ++i )
   {
      if(foo[i] == m){

         // You need to move only the number of
         // items of the array that have user set
         // numbers.
         for(int j = i; j < numElements-1; j++){
            foo[j] = foo[j+1];
         }

         // This is strictly not necessary but is
         // in the spirit of rest of your code where
         // you initialize to zero all members that have
         // not been explicitly set by the user.
         foo[numElements-1] = 0;

         numElements--;
         break;
      }
   }

   if(numElements*2 < capacity)
      shrink();
}

If m is not in the array at all, the function (both the original and the purportedly fixed) happily walks off the end.

Collectives™ on Stack Overflow

Segmentation fault error c++ dynamic array

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related