C++

Forum

 
Linked list deallocation exception error

Aug 8, 2016 at 9:26pm
RUNNER PRO AGARIO (275)
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
#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;
	}
}
Edit & run on cpp.sh

The weird thing here is, is that my exception is not being caught. Hmmm...
Aug 8, 2016 at 10:08pm
Naughty Albatross (1283)
Hi, 
1
2
3
 
Node * temp = current;
			delete current;
			current = temp->next;


Should be : 
1
2
3
 
Node * temp = current->next;
			delete current;
			current = temp;
Aug 9, 2016 at 9:10am
Peter87 (11189)
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.
Last edited on Aug 9, 2016 at 9:11am
Aug 9, 2016 at 10:59am
coder777 (8442)
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.
Aug 9, 2016 at 4:01pm
dhayden (5798)
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:
1
2
3
4
5
6
7
8
 
Stack::~Stack()
{
	while (m_head) {
		Node *next = m_head->next;
		delete m_head;
		m_head = next;
	}
}

Aug 11, 2016 at 6:19pm
RUNNER PRO AGARIO (275)
Ok thanks guys!
Aug 11, 2016 at 6:25pm
RUNNER PRO AGARIO (275)
Here is my complete code:
Suggestions for improvement I will consider, Thanks!

Stack.hpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
#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 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#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;
	}
}
Edit & run on cpp.sh

I include main, so you may suggest improvements to the try ... catch block of any kind.
Last edited on Aug 11, 2016 at 6:26pm
Aug 11, 2016 at 6:56pm
dhayden (5798)
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.
Aug 11, 2016 at 7:48pm
RUNNER PRO AGARIO (275)
Yes, I was going to add the constructors and assignments, and how does pop leak memory?
Aug 12, 2016 at 11:31am
dhayden (5798)
how does pop leak memory? 
1
2
3
4
5
6
7
8
9
10
11
12
13
 
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.
}

Aug 12, 2016 at 11:58am
coder777 (8442)
1
2
3
4
5
6
7
8
9
 
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!" };
}
Aug 19, 2016 at 7:52pm
RUNNER PRO AGARIO (275)
ooook i get it. Thanks for helping me realize.
Last edited on Aug 19, 2016 at 7:54pm
Topic archived. No new replies allowed.