0

When I implement pop() and destructor of a stack which holds nodes,should I delete node->data before deleting the node itself or should I just delete the node and let the caller who creates node->data to delete the node->data? If letting the caller to do that, when and how should the caller deletes the data? Should it call in this way: {data = stack.top(); delete data; stack.pop();}?

I have not seen any code which delete node->data, neither in a implementation of pop() nor a caller function. That is why I am confused.

Here I copy the stack I implemented using link list.Please take a look at the note of pop() and ~stack() for my question. Thanks for your help. 

typedef struct Node_t{
    struct Node_t* next;
    void* data;
}Node; 

class stack {
public: 
    stack(): _head(null), _size(0){}
    ~stack();
    void push(void* data);
    void pop();
    void* top();
    bool empty();
    stack(const stack& original);
    stack& operator=(const stack& original);    
private:
    Node* _head;    
    int _size;  
};
stack::~stack{
 Node* next = null;
 while(_head){
      next = _head->next;
      //should delete _head->_data???
      delete _head;                     
      _head = next;
 }
 _size = 0;
}
void stack::push(void* data){
    Node* elem = new Node;
    elem->data = data; 
    elem->next = _head;
   _head = elem;
    _size++;
}    

void stack::pop(){
Node* next = NULL;
if (_head) {
   next = _head->next;
   //should delete _head->_data???
   delete _head;
   _head = next;        
   _size--;
}
}    

void* stack::top() const{
if (_head) {
   return _head->_data;
}        
}

bool stack::empty(){
   if(_size>0) return false;
   else return true;
}
user389955
  • 9,605
  • 14
  • 56
  • 98

2 Answers2

2

Your data is a pointer pointing to something elsewhere. The strategy here is: you create a data object out side your stack and push the pointer of data into your stack. So, by symmetry, the control of delete the data should also exist out side your stack. You need to explicitly delete it if you don't need it. For example:

stack s;
char mydata[] = {'a','b','c'};
s.push((void*)mydata);
//do things
s.pop();
delete [] mydata;

If you really want to control the data inside the stack (through it may be not a good idea, suppose your data may be used in somewhere else), there is also a problem. Because the type of data is void* and you may not 'safely' delete it just as is. See this thread Is it safe to delete a void pointer?

Community
  • 1
  • 1
jgmao
  • 147
  • 2
  • 8
  • +1: I agree that this is a good approach for `pop()` based on the existing `push()` semantics. I can't immediately think of an example where the existing `push()` sementics are the best option for the whole design, though, when reference semantics are available. – Simon Jun 27 '13 at 22:21
1

There are several parts to this answer:

  1. For practical programming, there is no reason to ever build your own data structures where those data structures are already provided by the standard library.

  2. If you do have to build your own data structures as a learning exercise, in principle you could have any semantics of allocation and deletion that you wish.

  3. However, if you have to build your own stack, I'd strongly advise following the same semantics as the standard library stack, which uses copy and reference semantics to avoid the need for explicit allocation and deletion in user code.

Following the standard library semantics improves consistency, reduces cognitive load in understanding interfaces and greatly reduces the chances of memory leaks.

Simon
  • 10,679
  • 1
  • 30
  • 44
  • It is for learning. I tried to make the interface the same as std::stack except that I did not use template such as using push(const T& data) because I did not want to complicate my code. But it seems I'd better use pass template by reference (T& data) rather than pass by pointer (void* data) according to your suggestion. Thx – user389955 Jun 27 '13 at 22:41
  • I just read the std::stack and found the data is not pass by reference, it is copied to the stack. see http://www.daniweb.com/software-development/cpp/threads/301165/stack-implementation-code-using-stl. in line 60 -> line 64 -> line 52, the item will be copied to nodeValue. If the structure of nodevalue is complex, copy is expensive. – user389955 Jun 27 '13 at 23:03
  • If you push a copy of the pointer to the node data, that is very cheap and those semantics explicitly leave the responsibility of allocating and deleting the memory in the user's code, which is where you would like that to be done. – Simon Jun 27 '13 at 23:13
  • when u said "If you push a copy of the pointer to the node data, that is very cheap" do you mean using pointer for push (void* data) or push(Data* data) (suppose type of data is Data)? that is how I wrote the push() of stack. – user389955 Jun 27 '13 at 23:24
  • In this particular case, `push(const Data *data)` and `push(const Data *&data)` (the latter being equivalent to the `std::stack()` implementation) are not much different. For me, using reference semantics both for `push()` and for `top()` is a strong message to the user of the class that the class will not manage allocate or delete the memory at the end of the pointer. – Simon Jun 27 '13 at 23:38