C++

Forum

 
Issues deleting an entire Stack data structure

gedamial (313)
Hi.

I've my own Stack class

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
83
84
85
86
87
88
89
90
91
92
93
94
 
template<typename T>
struct Block
{
	T val;
	Block* top;
};

template<typename T>
class GStack
{
public:
	Block<T>* base;
	int blocks = 0;

public:
	GStack(const T& firstVal) : base{ new Block<T>{ firstVal, nullptr } }
	{
	   blocks++;
	}

	~GStack()
	{
	   ClearAll();
	   base = nullptr;
	}

	// Deletes all the blocks from the stack
	void ClearAll()
	{
	   for (int i{ 0 }; i < blocks; i++)
	   {
		std::cout << "ClearAll()" << endl;
		pop();
	   }
	}

	void push(const T& val)
	{
	   Block<T>* newBlock = new Block<T>;
	   newBlock->val = val;
	   newBlock->top = nullptr;

	   if (!base)
	      base = newBlock;

	   else
	   {
		Block<T>* tmp = base;

		while (tmp->top)
		{
		   tmp = tmp->top;
		}

		tmp->top = newBlock;
	   }
		blocks++;
	}

	void pop()
	{
	   if (blocks > 0)
	   {
		Block<T>* previous = base;
		Block<T>* tmp = previous->top;

		if (tmp)
		{
			// Make tmp to point to the last block
			while (tmp->top)
			{
				tmp = tmp->top;
				previous = previous->top;
			}

			delete tmp;
			tmp = nullptr;

				previous->top = nullptr;
			}

			// If it's the last block...
		else
		{
			delete previous;
			previous = nullptr;

			// set the base block point to nothing
			base = nullptr;
		}

		blocks--;
	}
}


In the main, if I write

1
2
3
4
5
 
GStack<int>* my{ new GStack<int>{0} };
my->push(10);
my->push(20);
my->push(30);
my->ClearAll();


The output is:


ClearAll()
ClearAll()


Hmh... bug!
It should be printed out 4 times, since the blocks are 4!

I tested that and, if you try to remove the pop() function call form the ClearAll() function in the for loop... then the ClearAll() gets called four times.

But why?
What's happening behind the scenes?

NOTE

For some reason the bug is related to the for loop in the ClearAll() function, specifically with the blocks variable which counts the number of blocks (nodes) in the stack.

In the main, if I write

1
2
3
4
5
6
7
8
9
 
cout << "Blocks: " << my->blocks << endl;
	my->pop();
	cout << "Blocks: " << my->blocks << endl;
	my->pop();
	cout << "Blocks: " << my->blocks << endl;
	my->pop();
	cout << "Blocks: " << my->blocks << endl;
	my->pop();
	cout << "Blocks: " << my->blocks << endl;


The output is correct


Blocks: 4
Blocks: 3
Blocks: 2
Blocks: 1
Blocks: 0


What - is - happening?

Last edited on
ne555 (10692)
1
2
3
4
5
6
7
8
 
	void ClearAll()
	{
	   for (int i{ 0 }; i < blocks; i++)
	   {
		std::cout << "ClearAll()" << endl;
		pop();
	   }
	}
i=0, blocks=4 -> pop
i=1, blocks=3 -> pop
i=2, blocks=2 -> end loop
CLman94 (46)
Notice that Blocks is being decremented in the pop function. And in ClearAll(), the loop statement will check if i < blocks and after 2 iterations, blocks = 2 and i =2. The loop end there.

Here's a demonstration: http://cpp.sh/9kje

To fix this, just create a new variable that equates to the variable block's value before the start of the loop.

1
2
3
4
 
...
int blocks_to_loop = block;
for (int i{ 0 }; i < blocks_to_loop; i++)
...
gedamial (313)
What a stupid. I feel so relieved now.

Thanks guys =)
Last edited on
Topic archived. No new replies allowed.