Object Destructor Throwing SIGSEGV

[Sh0es]

I have the following code. The destructor throws a segmentation fault when it gets called. My first instinct is that there's something screwy with the array allocation. Can you fix it with this information?

#ifndef ARRAYLIST_H
#define	ARRAYLIST_H

#include <iostream>
#include "Exceptions.h"

using namespace std;

template <class T>
class ArrayList {
public:
	...

	ArrayList();
	ArrayList(int s); //allows the ArrayList to be initialized like an array
	ArrayList(T d[], int s);
	virtual ~ArrayList();

protected:
	int size;

	void sort(T d[], int l, int r); //used recursively by the standard sorting method
	void smallSort(); //an insertion sort used by the standard sorting method to sort small (size <= 10) arrays.
	void swap(T a, T b);
};

...

template <class T>
ArrayList<T>::ArrayList() {
    data = new T[0];
    size = 0;
}

template <class T>
ArrayList<T>::ArrayList(int s) {
    size = s;
    data = new T[size];
}

template <class T>
ArrayList<T>::ArrayList(T d[], int s) {
    data = d;
    size = s;
}

template <class T>
ArrayList<T>::~ArrayList() {
    if(data != NULL) delete[] data;
}

#endif	/* ARRAYLIST_H */ 

It's specifically the memory clearance in the destructor that throws the segfault.

[Disch]

template <class T>
ArrayList<T>::ArrayList(T d[], int s) {
    data = d;
    size = s;
}

This will cause the destructor to blow up in most instances:

{
   int ar[10];
   ArrayList<int> a(ar,10);
} // <- EXPLODE... dtor is trying to delete[] ar, but ar was not allocated with new[] 

{
   int* ptr = new int[10];
   ArrayList<int> a(ptr,10);
   delete[] ptr;
} // <- EXPLODE... dtor is trying to delete[] ptr, but ptr was already deleted. 

The only way to make it work:

{
   int* ptr = new int[10];
   ArrayList<int> a(ptr,10);
   //  DO NOT DELETE 'ptr' EVER -- 'a' now owns it and will delete it
} // <- OK, dtor will delete[] 'ptr' 

Another possible problem is for this to work you also will need to overload copy-construct and the assignment operator, or those too will cause a double-delete.

[Sh0es]

Can I fix it by making my ArrayList<T>::ArrayList(T d[], int s) method take a T* rather than a T[]?

[Disch]

No. The two are identical.

You have to grasp the concept of ownership. The owner basically is whatever is in charge of cleaning up the memory. If ArrayList is owning the array and deleting it, then it also should be creating it. That way it knows it was created with new[] and it knows it can delete[] it safely.

One option would be to get rid of that ctor entirely.

Or, if you want to keep it, it simply cannot take the given pointer as-is. It will need to deep copy the data -- creating its own array with new[] and copying each element over.


Note you will need to do the same 'deep copy' thing for your copy constructor and assignment operator or they too will cause explosions.

[Sh0es]

I changed my ctor to deep-copy the array data and my dtor is still throwing a segfault.

[Disch]

I'll need to see more code. Can you post the entire class?

[Sh0es]

#ifndef ARRAYLIST_H
#define	ARRAYLIST_H

#include <iostream>
#include "Exceptions.h"

using namespace std;

template <class T>
class ArrayList {
public:
	void setData (T* d);
	T* data;
	int getSize();

	void append(T d); //adds d to the end of the ArrayList
	void insert(T d, int p); //inserts d at index p in the ArrayList
	void remove(T d); //searches for d via binary search and removes it if found
	T getSpecificData(int p); //gets the data at index p
	bool isEmpty();
	int capacity(); //returns the number of free slots in the ArrayList

	bool operator==(ArrayList<T> b); //overloaded operators
	bool operator!=(ArrayList<T> b);
	bool operator<(ArrayList<T> b);
	bool operator>(ArrayList<T> b);
	bool operator<=(ArrayList<T> b);
	bool operator>=(ArrayList<T> b);

	ArrayBoundsException abe;
	EmptyArrayException eae;

	ArrayList();
	ArrayList(int s); //allows the ArrayList to be initialized like an array
	ArrayList(T* d, int s);
	virtual ~ArrayList();

protected:
	int size;
};

template <class T>
void ArrayList<T>::setData(T* d) {
    data = d;
}

template <class T>
void ArrayList<T>::append(T d) {
    T* temp = new T[size + 1];

    for(int i = 0; i < size; i++)
        temp[i] = data[i];

    temp[size] = d;
    if(data != NULL) delete[] data;
    data = temp;
    ++size;
}

template <class T>
void ArrayList<T>::insert(T d, int p) {
    if(p < 0 || p > size-1) throw abe;

	T* temp = new T[size + 1];

    for(int i = 0; i < p; i++) {
        if(i == p) {
            temp[i] = d;
        }
        else
            temp[i] = data[i];
    }
    for(int i = p; i < size + 1; i++)
        temp[i+1] = data[i];

	delete[] data;
    data = temp;
    ++size;
}

template <class T>
T ArrayList<T>::getSpecificData(int p) {
	if(p < 0 || p > size-1) throw abe;
    return data[p];
}

template <class T>
void ArrayList<T>::remove(T d) {
    T* temp = new T[size-1];
	int i = 0;

	while(data[i] != d) {
		temp[i] = data[i];
		++i;
	}
	++i;
	while(i < size-1) {
		temp[i-1] = data[i];
	}

	delete[] data;
	data = temp;
	--size;
}

template<class T>
int ArrayList<T>::getSize() {
    return size;
}

template <class T>
int ArrayList<T>::capacity() {
    int temp = 0;
    for(int i = 0; i < size; i++) {
        if(data[i] == '\0')
            ++temp;
    }
    return temp;
}

template <class T>
bool ArrayList<T>::isEmpty() {
	return (data == NULL);
}

template <class T>
bool ArrayList<T>::operator ==(ArrayList<T> b) {
    bool equal = true;
    int i = 0;

    while(((data || b.data)) != NULL && equal == true) {
        if(data[i] != b.getSpecificData(i))
            equal = false;

        ++i;
    }

    return equal;
}

template <class T>
bool ArrayList<T>::operator !=(ArrayList<T> b) {
    bool uneq = true;
    int i = 0;

    while((data || b.data) != NULL && uneq == true) {
        if(data[i] == b.getSpecificData(i))
            uneq = false;

        ++i;
    }

    return uneq;
}

template <class T>
bool ArrayList<T>::operator <(ArrayList<T> b) {
    bool less = true;
    int i = 0;

    while((data || b.data) != NULL && less == true) {
        if(data[i] >= b.getSpecificData(i))
            less = false;

        ++i;
    }

    return less;
}

template <class T>
bool ArrayList<T>::operator >(ArrayList<T> b) {
    bool great = true;
    int i = 0;

    while((data || b.data) != NULL && great == true) {
        if(data[i] <= b.getSpecificData(i))
            great = false;

        ++i;
    }

    return great;
}

template <class T>
bool ArrayList<T>::operator <=(ArrayList<T> b) {
    bool leq = true;
    int i = 0;

    while((data || b.data) != NULL && leq == true) {
        if(data[i] > b.getSpecificData(i))
            leq = false;

        ++i;
    }

    return leq;
}

template <class T>
bool ArrayList<T>::operator >=(ArrayList<T> b) {
    bool geq = true;
    int i = 0;

    while((data || b.data) != NULL && geq == true) {
        if(data[i] > b.getSpecificData(i))
            geq = false;

        ++i;
    }

    return geq;
}

template <class T>
ArrayList<T>::ArrayList() {
    data = new T[0];
    size = 0;
}

template <class T>
ArrayList<T>::ArrayList(int s) {
    size = s;
    data = new T[size];
}

template <class T>
ArrayList<T>::ArrayList(T d[], int s) {
    data = new T[s];
    for(int i = 0; i < s; i++)
        data[i] = d[i];

    size = s;
}

template <class T>
ArrayList<T>::~ArrayList() {
    if(data != NULL)
        delete[] data;
}

#endif	/* ARRAYLIST_H */ 

[Disch]

Well right away I see you don't have a copy ctor. Nor do you have an assignment operator. I'm 99% sure that's what the problem is.

You also still have some ownership issues. Without actually looking at any of the function bodies... here are my notes... again, copy ctor and assignment operator are the main culprit here... though 'setData' would also shoot you in the foot if it is ever called:

template <class T>
class ArrayList {
public:
	void setData (T* d);    // <- Get rid of this function.  It causes ownership issues
	T* data;                // <- This should ABSOLUTELY be private.  Making this public is a disaster.
	int getSize();

	void append(T d);
	void insert(T d, int p);
	void remove(T d);
	T getSpecificData(int p);   // <- consider overloading the [] operator rather than having get/set for individual elements.
	bool isEmpty();
	int capacity();

	bool operator==(ArrayList<T> b);  // <- probably should take const references as params, rather than copies
	bool operator!=(ArrayList<T> b);  // <- ditto for all of these operator overloads
	bool operator<(ArrayList<T> b);
	bool operator>(ArrayList<T> b);
	bool operator<=(ArrayList<T> b);
	bool operator>=(ArrayList<T> b);

	ArrayBoundsException abe;           // <- don't instantiate exception objects inside the class.  Just create the exception
	EmptyArrayException eae;            //    when you throw it.

	ArrayList();
	ArrayList(int s);
	ArrayList(T* d, int s);
	virtual ~ArrayList();               // <- you probably don't want to make this virtual unless you plan this to be a
                                        //  parent in a class tree.  Which, with a class like this, I don't see how that
                                        //  would be practical.

    //   <- You absolutely NEED a copy ctor for this class to work properly.  It has to deep copy.  Without it
    //      you will double-delete arrays whenever you make a copy (which will cause a crash)

    //   <- You absolutely NEED an assignment operator overload for the same reason.  The assignment operator
    //      will probably have to delete the original array, then recreate a new one and deep copy.

    //   <- consider a move-ctor (C++11)
    //   <- consider a move-assignment operator (C++11)

protected:              // <- this should be private, not protected
	int size;   // <- you have functions for capacity and size... but are only tracking size???
             // how can you know the capacity?
};

[Sh0es]

This should ABSOLUTELY be private. Making this public is a disaster.

This will have to be accessed by other, non-inhereting classes and my accessor was throwing compiler errors.

probably should take const references as params, rather than copies

I'll consider that, but the methods make use of non-const methods in the class and I'm worried that making it const will cause problems in the rest of my code.

you probably don't want to make this virtual unless you plan this to be a
parent in a class tree. Which, with a class like this, I don't see how that would be practical.

this should be private, not protected

This does actually have a class which inherits from it.

you absolutely NEED a copy ctor and an overloaded assignment operator

Explain to me why, unless the overloaded = takes arrays, including both of these isn't redundant.

how can you know the capacity

1. That method isn't really used in my implementation.
2. I usually flush my arrays so that the data defaults to '\0'.

UPDATE: It turns out that data isn't used by any non-inheriting classes.

[Disch]

This will have to be accessed by other, non-inhereting classes and my accessor was throwing compiler errors.

Having that public destroys encapsulation in the worst possible way. It is the single most critical member of your class and should absolutely be private because it is so sensitive.

If you allow other code to tinker with it, it will be very easy to break the class with external code... which makes bugs much harder to find and fix. IE: if anything can access the data, then the bug could be anywhere... but if only this class can access the data, the the bug must be someone in the class code.

If other code needs direct access via a pointer and not through an ArrayList object, then a 'getter' to get a pointer to the data is very easy to write:

T* getData() { return data; }

I'll consider [passing by const ref], but the methods make use of the non-const getSpecificData method

So make getSpecificData const. It doesn't modify the object, does it? It shouldn't.

I'm worried that making it const will cause problems in the rest of my code.

It shouldn't. I don't see how it possibly could.

This does actually have a class which inherits from it.

That's weird, but ok.

Explain to me why, unless the overloaded = takes arrays, including both of these isn't redundant.

The overloaded = would take an ArrayList<T>.

Your problem is this: every time you call any of your >=, ==, etc operator overloads, you are creating a copy of the ArrayList object.

By default... if you do not specify a copy constructor... C++ will do a shallow copy of all members. This means you will have multiple objects pointing to the same memory -- and each object will try to delete[] the memory when the dtor runs -- resulting in the same memory being deleted multiple times (crash).

Since your ArrayList class has strict ownership of the array, and deletes it in its dtor... it MUST do a deep copy to ensure that each ArrayList object has its own memory, therefore when their dtor runs and deletes it, they are not deleting each others data.

Your problem now:

{
    ArrayList<int> a(10);   // <- allocates a block of memory, let's call that memory 'foo'
    {
        ArrayList<int> b(a); // <- copy.  Shallow copy means no new memory is allocated.
           // instead, now both 'a' and 'b' both point to 'foo' memory
    } // <- b's dtor runs, delete[]'s foo

    // <- here, foo has been deleted, but 'a' is unaware of that fact.  If 'a' tries to access
    //    it, VERY BAD THINGS can happen.
} // <- 'a's dtor will run and try to delete[] foo again... but it has already been deleted
  //  so it will almost certainly crash. 

The assignment operator is the same thing... only more severe because it also leaks memory:

{
    ArrayList<int> a(10);   // <- allocates 'foo'
    {
        ArrayList<int> b(10); // <- allocates 'bar'

        b = a;  // <- 'bar' memory is no longer being pointed to and therefore can never
            // be deleted.  IE:  you have a memory leak.  Instead, 'b' now points to 'foo'
    } // <- b's dtor runs, delete[]'s foo

    // <- same deal, 'foo' has been deleted, so 'a' can't access it
} // <- 'a's dtor delete[]s it again.  Crash. 

1. That method isn't really used in my implementation.

Then why have it?

2. I usually flush my arrays so that the data defaults to '\0'.

So? What if someone wants to store a value of 0 in the array? If you are using 0 as a special marker, that will screw things up.

[Sh0es]

So? What if someone wants to store a value of 0 in the array? If you are using 0 as a special marker, that will screw things up.

I'm not using 0, I'm using \0, or the null terminator.

[Disch]

They're the same thing. In a character, \ followed by a zero means the following digits form an octal number for the integral representation. IE, '\0' means use the intergral value of 0, '\1' means to use 1, etc.

Try it out yourself:

if(0 == '\0')
{
    cout << "this will print";
}

[Sh0es]

So make getSpecificData const.

I did that and I'm still getting the error.

[Disch]

What's the error?

[Sh0es]

non-const function being called on const object.

[Disch]

Are you sure you're doing it right?

// wrong:
const T getSpecificData(int p);

// right:
T getSpecificData(int p) const;

[Sh0es]

That fixed it.

[Sh0es]

About the setData() method; it's necessary for my program. How would you make it stable? I tried making it take a T& array but apparently those are not allowed. Would you suggest deep-copying it too?

[Disch]

I'm under the assumption that you want ArrayList to own this memory. If that is the case, you have 2 options:

1) Do a deep copy
or
2) Have setData simply assume ownership (ie, it assumes that whatever pointer is passed to it was not only created with new[], but will also never be deleted)

The bottom line is that at the end of the day, ArrayList has to own the memory. Period. This means it is the only area of the code that will delete[] it. As as soon as the ArrayList is destructed (or reassigned or whathaveyou), the memory will go away.

I do not recommend #2 because it is very error prone. So yes, in this case, you'd probably want to deep copy there, too.

Regardless of which option you choose, be sure to remember to delete[] the old memory before recreating new memory or the old memory will leak.


Although you don't really have to have this function at all. It is largely redundant. You can just use the ctor:

// instead of doing this:
a.setData( whatever, 5 );

// just do this:
a = ArrayList<int>( whatever, 5 );

Assuming your assignment operator is overloaded properly, that will have the same effect.

Actually in second thought that wouldn't work too well because this is a parent class... I keep forgetting that because it's so weird. =P

So yeah. Deep copy.





On a side note... is there any reason you aren't just using vector? I assumed this was a learning exercise... but really vector does all of this already and much more.

[Sh0es]

On a side note... is there any reason you aren't just using vector? I assumed this was a learning exercise... but really vector does all of this already and much more.

It's actually part of a class project. We're basically learning about data structures like this so we're not allowed to use anything in the standard libraries that would allow us to get around them.