Newbie: C++ destructor problem

Question

I have to write a stack class template using arrays in C++ for my assignment. Here is my code.

#include <iostream>

template <typename Type>
class Stack {
private:
  int top;
  Type items[];
public:
  Stack()  { top = -1; };
  ~Stack() { delete[] items; };
  void push(Type);
  bool isEmpty() const;
  Type pop();
  Type peek() const;
};

int main (int argc, char *argv[]) {
  Stack<double> st;
  return 0;
}

template<typename Type>
void Stack<Type>::push(Type item) {
  top++;
  if(top == sizeof(items) / sizeof(Type)) {
    Type buff[] = new Type[top];
    std::copy(items,items+top,buff);
    delete[] items;
    items = new Type[2*top];
    std::copy(buff,buff+top,items);
    delete[] buff;
  }
  items[top] = item;
}

template<typename Type>
bool Stack<Type>::isEmpty() const {
  return top == -1 ? true : false;
}

template<typename Type>
Type Stack<Type>::pop() {
  //TODO
  return items[top--];
}

template<typename Type>
Type Stack<Type>::peek() const{
  //TODO
  return items[top-1];
}

It is compiled fine using "g++ -Wall".

When I run the program, I got this error.

*** glibc detected *** `./lab3: munmap_chunk(): invalid pointer: 0x00007fff41a3cdf8`

After trying out a bit with gdb, I found out the error arose from the line
free[] items in the destructor.

I don't understand why freeing an array results in a memory leak ? Any clues ?

Answer 1

You should only delete[] what you have explicitly allocated with new[]. Your items member is not a dynamically allocated array, so you must not free it as if it were.

On the other hand, you have

Type items[];

which doesn't actually allocate any space in your object instances for the stack.

Answer 2

I don't think that's a memory leak! It's a crash occurring because you deleted a non-heap object.

Answer 3

The first thing I've seen is that you're likely to mean Type *items, not Type items[].

And then you don't want to (can't) use sizeof on the dynamically allocated data.

Answer 4

items is a pointer to Type. This pointer must be initialised before it is used (it is a wild pointer as it is). That is why your program crashes. That it happens in the destructor is a coincidence. It could just as well have happened earlier. E.g. in push() memory is overwritten in the location that items happens to point to.

You need to allocate memory for a number of elements. See below.

You already have the logic for the dynamic growth of the array in place. But an array in C++ does not know its size (it is just a pointer of some type). You need to keep track of the current capacity/size. Thus instead of

sizeof(items)

define a new member to hold the current capacity.

E.g.:

int capacity;

and in the constructor:

capacity = 100;
items = new Type[capacity];

The last line allocates a number of elements and is the main solution to your problem.

And in push():

if (top == capacity / sizeof(Type)) {

---

The logic for reallocation will need to change. E.g.:

capacity *= 2;
items = new Type[capacity];

instead of
items = new Type[2*top];

I have just sketched out a solution here. Yon can fill in the details.

---

Note: you have only one instance of Stack in your program; body of main() is:

Stack<double> st;

If you instead were to assign one instance of Stack to another instance, e.g.

{
   Stack<double> st;
   Stack<double> st2 = st; //Copy constructor will be invoked for st2. If not defined the compiler generated copy constructor will do a copy of the pointer value.
   Stack<double> st3;
   st3 = st; //Assignment operator will be invoked for st3. If not defined the compiler generated assignment operator will do a copy of the pointer value.
}

then the copy constructor (to work for st2) and the assignment operator (to work for st3) for Stack must be defined properly (make a copy of the referenced member items). Otherwise a double or triple delete in the destructor and undefined behavior (e.g. a crash) will be the result when st, st2 and st3 goes out of scope at the close brace.

Answer 5

You haven't new'd items, so you can't delete it in the destructor. Assuming you require 'Stack' to be a dynamically sized class then the items array must be dynamically allocated in which case the declaration for items should be

Type *items;    (as hacker mentions above)

and the constructor should call 'items = new Type[ARRAY_SIZE]' to allocate the memory, or at the very least initially assign the 'items' pointer to NULL.

Edit based on comments -

To complete and secure the memory allocation responsibilities for this class you should also include a copy constructor and an assignment operator which allocates new memory and copies the values stored in items to the new object. This avoids the pointer simply being copied by the compiler generated copy constructor or assignment operator which would lead to multiple objects pointing to the same dynamically allocated memory. Upon destruction of the first of these objects this memory will be deleted. Further use of the now deleted memory by the other objects which share the pointer would be likely to result in a crash.

Rather than adding code here I refer you to the code in Martin's answer for this question.