Linked list deallocation exception error

[RUNNER PRO AGARIO]

I was deallocating a linked list, but go a read access violation. In my destructor's loop, when I was stepping through the code, I noticed the violating was in the second loop iteration. Here is my code.


Stack.hpp:

#pragma once
#ifndef STACK_HPP
#define STACK_HPP

class Stack
{
	struct Node
	{
		int val;
		Node * next;
	};
	Node * m_head;
public:
	Stack() : m_head{ nullptr } {};
	~Stack();
	void pop();
	void push(int value);
	inline int get()
	{
		return m_head->val;
	}

};

Stack::~Stack()
{
	if (m_head != nullptr)
	{
		Node * current = m_head;
		while (current->next != nullptr)
		{
			Node * temp = current;
			delete current;
			current = temp->next;
		}
	}
}

void Stack::push(int value)
{
	Node * pushNode = new Node{ value, m_head };
	m_head = pushNode;
}

void Stack::pop()
{
	m_head = m_head->next;
}
#endif 

Main:

#include <iostream>
#include "Stack.hpp"

int main()
{
	try
	{
		Stack stack;
		stack.push(2);
		stack.push(5);
		stack.push(66);
		std::cout << stack.get() << "\t";
		stack.pop();
		std::cout << stack.get();
		std::cin.get();
	}
	catch (const std::exception& e)
	{
		std::cerr << e.what();
		std::cin.get();
		return 1;
	}
	catch (...)
	{
		std::cerr << "Exception thrown!";
		std::cin.get();
		return 2;
	}
}

The weird thing here is, is that my exception is not being caught. Hmmm...

[Naughty Albatross]

Hi,

Node * temp = current;
			delete current;
			current = temp->next;

Should be :

Node * temp = current->next;
			delete current;
			current = temp;

[Peter87]

The problem is that current and temp points to the same node. After you have deallocated the node pointed to by current you can't use temp for the same reason you can't use current.

Changing the code to what "closed account" suggested improves things. The temp pointer is then the pointer to the next node after current so you may want to rename it next to better describe what it is.

Anyhow, you still have a problem that the loop stops too early. As soon as there is no node after the current node the loop stops which means the last node never gets deallocated. To fix this you would have to change the loop condition slightly.

[coder777]

If you provide a constructor (where you initialize the members) and a destructor (where you delete next) you wouldn't need a loop in the Stack destructor. Only delete m_head.

[dhayden]

Stack::pop() needs to delete the old head pointer.

You can further simplify the destructor by recognizing that you don't need the initial if statement:

Stack::~Stack()
{
	while (m_head) {
		Node *next = m_head->next;
		delete m_head;
		m_head = next;
	}
}

[RUNNER PRO AGARIO]

Ok thanks guys!

[RUNNER PRO AGARIO]

Here is my complete code:
Suggestions for improvement I will consider, Thanks!

Stack.hpp

#pragma once
#ifndef STACK_HPP
#define STACK_HPP

class Stack_Exception : public std::exception
{
public:
	Stack_Exception(char * error) : m_err{ error } {};
	Stack_Exception() : m_err{ "Stack::Exception thrown!" } {};
	virtual const char* what() const throw()
	{
		return m_err;
	}
private:
	char * m_err;
};

template<class T> class Stack
{
	template<class T> struct Node
	{
		T val;
		Node<T> * next;
	};
	Node<T> * m_head;
	size_t m_size;
public:
	Stack() : m_head{ nullptr }, m_size{ 0 } {};
	inline bool empty();
	inline T top();
	void push(T value);
	void pop();
	~Stack();
};


template<class T> inline bool Stack<T>::empty()
{
	return m_size == 0;
}

template<class T> inline T Stack<T>::top()
{
	if (m_head != nullptr)
	{
		return m_head->val;
	}
	else
	{
		throw Stack_Exception{ "Stack::top: Attempted to retrieve invalid node!" };
	}
}

template<class T> void Stack<T>::push(T value)
{
	Node<T> * pushNode = new Node<T>{ value, m_head };
	m_head = pushNode;
	++m_size;
}

template<class T> void Stack<T>::pop()
{
	if (m_head != nullptr)
	{
		m_head = m_head->next;
		--m_size;
	}
	else throw Stack_Exception{ "Stack::pop: Attempted to deference invalid node!" };
}

template<class T> Stack<T>::~Stack()
{
	while (m_head != nullptr)
	{
		Node<T> * nxtNode = m_head->next;
		delete m_head;
		m_head = nxtNode;
	}
}


#endif  

main.cpp

#include <iostream>
#include "Stack.hpp"

int main()
{
	try
	{
		Stack<int> stack;
		stack.push(33);
		stack.push(22);
		stack.push(32);
		stack.push(21);
		stack.push(11);
		stack.push(0);
		stack.push(13);
		stack.push(29);
		while (!stack.empty())
		{
			std::cout << stack.top() << "\t";
			stack.pop();
		}
		std::cin.get();
	}
	catch (const std::exception& e)
	{
		std::cerr << e.what();
		std::cin.get();
		return 1;
	}
	catch (...)
	{
		std::cerr << "Exception thrown!";
		std::cin.get();
		return 2;
	}
}

I include main, so you may suggest improvements to the try ... catch block of any kind.

[dhayden]

Stack<T>::pop() leaks memory.

It would probably be better for top() to return a reference rather than a value. Also, push() should take a const reference rather than a value as the argument.

The code will break if someone copies one list to another. Consider adding the copy constructor and assignment operator.

[RUNNER PRO AGARIO]

Yes, I was going to add the constructors and assignments, and how does pop leak memory?

[dhayden]

how does pop leak memory?

int main()
{
	Stack<int> stack;
	stack.push(33);
	stack.push(22);
	stack.push(32);
	stack.push(21);
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	// the stack is now empty, but none of the memory was freed.
}

[coder777]

template<class T> void Stack<T>::pop()
{
	if (m_head != nullptr)
	{
		m_head = m_head->next; // You overwrite the m_head pointer, but you need to free the memory beforehand
		--m_size;
	}
	else throw Stack_Exception{ "Stack::pop: Attempted to deference invalid node!" };
}

[RUNNER PRO AGARIO]

ooook i get it. Thanks for helping me realize.