1

I am trying to write a simple stack with dynamic memory allocation. Must be with new/delete. Sorry, if it's trivial but I would appreciate if someone could take a look. Any advice is appreciated.

It works, but I want to make peace with valgrind --leak-check=full

stack.cpp

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include "stack.h"
#include <algorithm>

#define INITIAL_STACKSIZE 1

stack::stack()
{
    top = 0;
    size = INITIAL_STACKSIZE;
    data = new int[size];
}
stack::~stack()
{
    // delete [] ptr;   makes it worse  "free(): double free detected in tcache 2 
    //                                   Aborted (core dumped)"

    delete [] data;
}
void stack::push(int a)
{
    if(top >= size)
    {
        int new_size = size * 2;
        ptr = new int[new_size];
        std:: copy(data, data + top, ptr);
        data = ptr;
        size = new_size;        
    }
    data[top++]=a;
}
int stack::pop()
{
    assert(top>0);
    return data[--top];
}

stack.h

class stack
{
public:
    void push(int a);
    int pop();
    void clear();
    stack();
    ~stack();
private:
    int top;
    int size;
    int *data;
    int *ptr;
};

teststack.cpp

#include <stdio.h>
#include "stack.h"

int main()
{
    stack s1;
    stack s2;
    s1.push(1);
    s1.push(2);
    
    s2.push(5); 
    s2.push(6);
    
    printf("%d %d\n",s1.pop(),s2.pop());
    printf("%d\n",s1.pop());
    printf("%d\n",s2.pop());
    return 0;
}
Nate Morning
  • 11
  • 2
  • 3
    What happens to the old data in the push member function? – Passerby Oct 28 '21 at 01:30
  • 4
    Passerby is correct. But [Rule of Three](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) is also a must-read. You've defined a destructor, so you have some responsibilities to define other functions as well. – Silvio Mayolo Oct 28 '21 at 01:31
  • 4
    I haven't tried this out yet, but my first guess is that you need to `delete[] data` before you do `data = ptr` in your `stack::push`. – Shane Bishop Oct 28 '21 at 01:31
  • `s1 = s2;` Try that, and you will never make peace with valgrind until you follow the rule of 3. *Must be with new/delete* -- And the joke is that the teacher is laughing that you will never get this right unless you are told about rule of 3. So you will be pulling your hair out trying to get valgrind to behave (if you changed `main` slightly). – PaulMcKenzie Oct 28 '21 at 01:41
  • Ask yourself why `ptr` is a member of the object instead of being a variable local to `push()`. Keeping scopes small helps remove noise when debugging. For example, if `ptr` was local to the `if` statement in `push()`, you would not waste time experimenting with `delete [] ptr;` in the destructor. – JaMiT Oct 28 '21 at 02:38
  • Using valgrind while learning is a very good idea – EvilTeach Oct 28 '21 at 14:09

1 Answers1

2

You need to delete[] data in your stack::push() before you assign ptr to data.

When you assign ptr to data as you do now before freeing the memory stored in data, you lose the pointer to the memory you allocated with new earlier (i.e., you leak memory).

Once you've copied everything out of data with std::copy(), it is safe to free the memory pointed to by data, since the memory has been copied.

So here is what your stack::push() should look like:

void stack::push(int a)
{
    if(top >= size)
    {
        int new_size = size * 2;
        ptr = new int[new_size]; // Or if ptr was a local variable,
                                 // this line would be
                                 // int ptr[] = new int[new_size];
        std:: copy(data, data + top, ptr);
        delete[] data;
        data = ptr;
        size = new_size;
    }
    data[top++]=a;
}

I also suggest you remove ptr from being a member variable of the stack class, and instead make it a local variable in the stack::push() method, since it isn't used anywhere else.

Shane Bishop
  • 3,905
  • 4
  • 17
  • 47