PPP2 Chapter 17 Exercise 11

Pages: 1... 910111213... 16
Yeah, but how do I define the class' destructor now?

What makes you think that this class needs to "delete" the allocated memory?

Does this class actually own the memory that has been allocated?

What happens if someone created the instances like:

1
2
3
4
Link Thor { { "Thor", "Norse",  "", "" } };
Link Ares { { "Ares", "Greek", "War chariot", "Sword and spear" } };
Link *norse_gods = &Thor;
norse_gods->add_ordered(&Ares);


Then what do I do about the memory leak? Visual Leak Detector is showing 74 leaks, 5,112 bytes in total. Isn't this is a big problem? There's dynamic memory allocation using new, so there should also be deallocation using delete, right? But if not in the destructor, then where?

Edit: Do I delete them in main() since the memory was allocated in main()?
Last edited on
I've attempted doing it in main(). Here's the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Link *trav = gods;
while (trav->next() != nullptr)
{
	trav = trav->next();
}

while (trav->previous() != nullptr)
{
	trav = trav->erase();
	trav = trav->previous();
}
trav = trav->erase();
delete trav;
delete gods;


When I ran it while debugging it just now, I got an
Unhandled exception thrown: read access violation. this was nullptr.
error on this function within the Link class: Link *previous() const { return m_prev; }, and it's definitely because of the above code where I'm trying to deallocate the memory for the Link class. So would someone please tell me what I did wrong here?

After that, I also need help with the remaining part of the exercise. Making a list of gods from three mythologies and then creating three lists of different mythologies from it. I tried doing it while looking at the moving code in the book, but no luck. I deleted the code and will start over after I've gotten the code for destroying the list correct. I don't want to leak any memory.
Last edited on
This is my current 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
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
int main()
{
	try
	{
		Link *gods = new Link{ { "Odin", "Norse",
			"Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
		gods = gods->add_ordered(new Link{ { "Baldr", "Norse", "Ship called Hringorni", "None" } });
		gods = gods->add_ordered(new Link{ { "Thor", "Norse",
			"Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Hammer called Mjolnir" } });
		gods = gods->add_ordered(new Link{ { "Frejya", "Norse",
			"Chariot pulled by two cats", "Magic called seidr" } });
		gods = gods->add_ordered(new Link{ { "Ares", "Greek", "War chariot", "Sword and spear" } });
		gods = gods->add_ordered(new Link{ { "Zeus", "Greek",
			"A chariot pulled by the four major winds shaped as horses", "Thunderbolt" } });
		gods = gods->add_ordered(new Link{ { "Apollo", "Greek",
			"Chariot pulled by the four horses Aethon, Pyrois, Phlegon and Eous", "A bow" } });
		gods = gods->add_ordered(new Link{ { "Hera", "Greek", "A chariot drawn by peacocks", "Her intelligence" } });
		gods = gods->add_ordered(new Link{ { "Amaterasu", "Japanese", "", "Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata" } });
		gods = gods->add_ordered(new Link{ { "Susanoo", "Japanese", "", "Sword of Totsuka" } });
		gods = gods->add_ordered(new Link{ { "Izanagi", "Japanese", "", "Sword of Totsuka (later given to Susanoo)" } });
		gods = gods->add_ordered(new Link{ { "Bishamonten", "Japanese", "", "A spear" } });

		print_all(gods);

		Link *trav = gods;
		while (trav->next() != nullptr)
		{
			trav->next();
		}

		while (trav->previous() != nullptr)
		{
			trav->erase();
			trav->previous();
		}
		trav = trav->erase();
		delete trav;
		delete gods;
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << '\n';
		keep_window_open();
		return 1;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << "\n";
		keep_window_open();
		return 2;
	}
	catch (...)
	{
		std::cerr << "An unknown exception occurred\n";
		keep_window_open();
		return 3;
	}

	keep_window_open();
}


I still get that same exception thrown, but now it happens a bit later.
I think you need to review how your previous() and next() member functions actually work, since you appear to be calling the improperly.

What do you think happens if you try to delete the same memory more than once?
It ends up "deleting" memory that the program doesn't own anymore. Which leads to disastrous results. But that's what I'm doing there, then?

What's there to not understand about the previous() and next() member functions? They're const functions that return a pointer to the previous and next node, respectively.

And all the member function erase() actually does is remove the node "this" is pointing at and return it to the calling function, right? So how do I actually remove and destroy a node? And then destroy the head node when it's the only node left? Because that's what I want to do.
But that's what I'm doing there, then?

Is it? What did you do to try to verify your conclusion?

They're const functions that return a pointer to the previous and next node, respectively.

That's correct, but since you never use the return value what does calling these functions really accomplish?

And all the member function erase() actually does is remove the node "this" is pointing at and return it to the calling function, right?

Did you try to follow the logic in that function? What is it really doing?

Because that's what I want to do.

But is that really what is happening? Again did you follow the logic of your program to see what is actually happening?

I thought trav->erase(); would work because it's done similarly in the book, in main(), for removing elements from the list and moving them into another list. And it worked when I tried it like that then.

Anyway, I changed it to the more clearer syntax:
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
int main()
{
	try
	{
		Link *gods = new Link{ { "Odin", "Norse",
			"Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
		gods = gods->add_ordered(new Link{ { "Baldr", "Norse", "Ship called Hringorni", "None" } });
		gods = gods->add_ordered(new Link{ { "Thor", "Norse",
			"Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Hammer called Mjolnir" } });
		gods = gods->add_ordered(new Link{ { "Frejya", "Norse",
			"Chariot pulled by two cats", "Magic called seidr" } });
		gods = gods->add_ordered(new Link{ { "Ares", "Greek", "War chariot", "Sword and spear" } });
		gods = gods->add_ordered(new Link{ { "Zeus", "Greek",
			"A chariot pulled by the four major winds shaped as horses", "Thunderbolt" } });
		gods = gods->add_ordered(new Link{ { "Apollo", "Greek",
			"Chariot pulled by the four horses Aethon, Pyrois, Phlegon and Eous", "A bow" } });
		gods = gods->add_ordered(new Link{ { "Hera", "Greek", "A chariot drawn by peacocks", "Her intelligence" } });
		gods = gods->add_ordered(new Link{ { "Amaterasu", "Japanese", "", "Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata" } });
		gods = gods->add_ordered(new Link{ { "Susanoo", "Japanese", "", "Sword of Totsuka" } });
		gods = gods->add_ordered(new Link{ { "Izanagi", "Japanese", "", "Sword of Totsuka (later given to Susanoo)" } });
		gods = gods->add_ordered(new Link{ { "Bishamonten", "Japanese", "", "A spear" } });

		print_all(gods);

		Link *trav = gods;
		while (trav->next() != nullptr)
		{
			trav = trav->next();
		}

		while (trav->previous() != nullptr)
		{
			trav = trav->erase();
			trav = trav->previous();
		}
		trav = trav->erase();
		delete trav;
		delete gods;
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << '\n';
		keep_window_open();
		return 1;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << "\n";
		keep_window_open();
		return 2;
	}
	catch (...)
	{
		std::cerr << "An unknown exception occurred\n";
		keep_window_open();
		return 3;
	}

	keep_window_open();
}


Is it? What did you do to try to verify your conclusion?


What? Are you really going to ask me that when you were the one who brought up the question
What do you think happens if you try to delete the same memory more than once?
? What's your intention to ask that? Is it because you're saying I'm doing that, or what?

I ran it in my debugger, but I'm not sure what actually happened. It looped in print_all() and this part
1
2
3
4
5
6
7
8
9
10
while (trav->next() != nullptr)
{
	trav = trav->next();
}

while (trav->previous() != nullptr)
{
	trav = trav->erase();
	trav = trav->previous();
}
in main() a few times and then triggered the same exception on previous() as before. I really don't understand what to take away from that, though.

As for erase(). It checks if the previous pointer is not null, and if it isn't, it follows it to its next pointer and makes point to the current pointer's previous pointer. Effectively taking the node pointed to by the current node's next pointer out. It also checks if the current node's previous pointer is null. If it isn't, it follows it to get to its next pointer and makes it point to the current node's next pointer. Then it returns the node pointed to by the current node's next pointer. So it takes out the node pointed to by the next pointer of the current node and returns it to the caller.
Last edited on
Are you really going to ask me that when you were the one who brought up the question

Look at what I was actually questioning:
It ends up "deleting" memory that the program doesn't own anymore. Which leads to disastrous results. But that's what I'm doing there, then?

You're guessing that something is or is not happening, I'm just questioning your conclusions. You need to stop guessing, you're not really very good at it.
As for erase().

I suggest you re-post the code for erase() but IMO you're using confusing terminology. What exactly is this function removing? You have one of three possible elements that should be removed, which one is it actually removing?


What do you think happens if you try to delete the same memory more than once?
? What's your intention to ask that? Is it because you're saying I'm doing that, or what?

Why would I ask a question like that if you weren't doing it?

in main() a few times and then triggered the same exception on previous() as befor

And what exactly is the wording for this exception? And exactly where is the debugger telling you it detects the problem?

But I guessed right that you meant I was deleting something more than once, so that's at least something, isn't it? And you just admitted that yourself here:
Why would I ask a question like that if you weren't doing it?
See that? That's what I was talking about the whole time.

And what exactly is the wording for this exception? And exactly where is the debugger telling you it detects the problem?


The previous() function is where it was pointing at, and the exception message is as I said in an earlier post:
Unhandled exception thrown: read access violation. this was nullptr.
.

erase():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Link *Link::erase()
{
	Link *trav = this;
	if (trav == nullptr)
	{
		return this;
	}
	if (trav->m_succ)
	{
		trav->m_succ->m_prev = trav->m_prev;
	}
	if (trav->m_prev)
	{
		trav->m_prev->m_succ = trav->m_succ;
	}
	return trav->m_succ;
}


Where am I deleting memory more than once? Do you mean I shouldn't erase trav and then also delete it and the gods pointer?
Last edited on
But I guessed right that you meant I was deleting something more than once, so that's at least something, isn't it?

Why are you guessing? You need to verify your conclusions. By the way this is easy to verify.

Unhandled exception thrown: read access violation. this was nullptr.

Exactly were is the debugger telling you it detects the problem?

The previous() function is where it was pointing at, and the exception message is as I said in an earlier post:

And where exactly? Point me to the actual line number.

Did you look at the values of the variables at the time of the crash? You need to backtrace the problem. Many times the debugger will produce a stack trace that you need to follow backwards to see where the problem starts. You need to figure out why *this is a nullptr since this should never happen unless your logic is incorrect somewhere.


Where am I deleting memory more than once?

At the end of the block right before the exception handlers.
How do I verify it, then?

And I'll post the code here to show you where the exception is occurring:
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Exercises 11-13

#include <iostream>
#include <vld.h>
#include "../../cust_std_lib_facilities.h"

struct God
{
	God(const std::string &name, const std::string &myth, const std::string &vehicle, const std::string &weapon)
		: m_name{ name }, m_myth{ myth }, m_vehicle{ vehicle }, m_weapon{ weapon } { }

	std::string name() const { return m_name; }
	std::string myth() const { return m_myth; }
	std::string vehicle() const { return m_vehicle; }
	std::string weapon() const { return m_weapon; }

	void set_name(const std::string name) { m_name = name; }
	void set_myth(const std::string myth) { m_myth = myth; }
	void set_vehicle(const std::string vehicle) { m_vehicle = vehicle; }
	void set_weapon(const std::string weapon) { m_weapon = weapon; }
private:
	std::string m_name;
	std::string m_myth;
	std::string m_vehicle;
	std::string m_weapon;
};

class Link
{
public:
	Link(const God &god, Link *p = nullptr, Link *s = nullptr)
		: m_god{ god }, m_prev{ p }, m_succ{ s } { }
	~Link();
	Link *insert(Link *n);                                            // insert n before this object
	Link *add(Link *n);                                               // insert n after this object
	Link *erase();                                                    // remove this object from list
	Link *find(const std::string &name);                              // find node matching passed in name in list
	const Link *find(const std::string &name) const;                  // find node matching passed in name in const list
	Link *find_if_myth(const std::string &myth);		              // find node matching passsed in myth in list
	const Link *find_if_myth(const std::string &myth) const;          // find node matching passsed in myth in const list
	Link *advance(int n) const;                                       // advance n positions in list
	Link *add_ordered(Link *n);							              // insert n in its correct lexicographical position

	God god() const { return m_god; }
	Link *next() const { return m_succ; }
	Link *previous() const { return m_prev; }

private:
	God m_god;
	Link *m_prev;
	Link *m_succ;
};

void print_all(Link *p);

int main()
{
	try
	{
		Link *gods = new Link{ { "Odin", "Norse",
			"Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
		gods = gods->add_ordered(new Link{ { "Baldr", "Norse", "Ship called Hringorni", "None" } });
		gods = gods->add_ordered(new Link{ { "Thor", "Norse",
			"Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Hammer called Mjolnir" } });
		gods = gods->add_ordered(new Link{ { "Frejya", "Norse",
			"Chariot pulled by two cats", "Magic called seidr" } });
		gods = gods->add_ordered(new Link{ { "Ares", "Greek", "War chariot", "Sword and spear" } });
		gods = gods->add_ordered(new Link{ { "Zeus", "Greek",
			"A chariot pulled by the four major winds shaped as horses", "Thunderbolt" } });
		gods = gods->add_ordered(new Link{ { "Apollo", "Greek",
			"Chariot pulled by the four horses Aethon, Pyrois, Phlegon and Eous", "A bow" } });
		gods = gods->add_ordered(new Link{ { "Hera", "Greek", "A chariot drawn by peacocks", "Her intelligence" } });
		gods = gods->add_ordered(new Link{ { "Amaterasu", "Japanese", "", "Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata" } });
		gods = gods->add_ordered(new Link{ { "Susanoo", "Japanese", "", "Sword of Totsuka" } });
		gods = gods->add_ordered(new Link{ { "Izanagi", "Japanese", "", "Sword of Totsuka (later given to Susanoo)" } });
		gods = gods->add_ordered(new Link{ { "Bishamonten", "Japanese", "", "A spear" } });

		print_all(gods);

		Link *trav = gods;
		while (trav->next() != nullptr)
		{
			trav = trav->next();
		}

		while (trav->previous() != nullptr)
		{
			trav = trav->erase();
			trav = trav->previous();
		}
		trav = trav->erase();
		delete trav;
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << '\n';
		keep_window_open();
		return 1;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << "\n";
		keep_window_open();
		return 2;
	}
	catch (...)
	{
		std::cerr << "An unknown exception occurred\n";
		keep_window_open();
		return 3;
	}

	keep_window_open();
}

Link::~Link()
{
	Link *trav = this;
	Link *head = nullptr;
	if (trav && trav->m_succ && trav->m_prev)
	{
		while (trav->m_prev)
		{
			trav = trav->m_prev;
		}
		head = trav;
		Link *current = trav;
		while (trav->m_succ)
		{
			trav = trav->m_succ;
			trav = trav->erase();
			delete current;
			current = trav = trav->m_succ;
		}
	}
	delete trav;
	trav = nullptr;
}

Link *Link::insert(Link *n)
{
	if (n == nullptr)
	{
		error("Node to add cannot be null");
	}
	n->m_succ = this;
	if (m_prev)
	{
		m_prev->m_succ = n;
	}
	n->m_prev = m_prev;
	m_prev = n;
	return n;
}

Link *Link::add(Link *n)
{
	if (n == nullptr)
	{
		error("Node to add cannot be null");
	}
	n->m_prev = this;
	if (m_succ)
	{
		m_succ->m_prev = n;
	}
	n->m_succ = m_succ;
	m_succ = n;
	return n;
}

Link *Link::erase()
{
	Link *trav = this;
	if (trav == nullptr)
	{
		return this;
	}
	if (trav->m_succ)
	{
		trav->m_succ->m_prev = trav->m_prev;
	}
	if (trav->m_prev)
	{
		trav->m_prev->m_succ = trav->m_succ;
	}
	return trav->m_succ;
}

Link *Link::find(const std::string &name)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		if (trav->m_god.name() == name)
		{
			return trav;
		}
		trav = trav->m_succ;
	}
	return this;
}

const Link *Link::find(const std::string &name) const
{
	const Link *c_trav = this;                    // const pointer
	Link *nc_trav = const_cast<Link*>(c_trav);    // non-const pointer
	while (c_trav != nullptr && nc_trav != nullptr)
	{
		if (c_trav->m_god.name() == name)
		{
			return c_trav;
		}
		nc_trav = nc_trav->m_succ;
	}
	return this;
}

Link *Link::find_if_myth(const std::string &myth)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		if (trav->m_god.myth() == myth)
		{
			return trav;
		}
		trav = trav->m_succ;
	}
	return this;
}

const Link *Link::find_if_myth(const std::string &myth) const
{
	const Link *c_trav = this;                    // const pointer
	Link *nc_trav = const_cast<Link*>(c_trav);    // non-const pointer
	while (c_trav != nullptr && nc_trav != nullptr)
	{
		if (c_trav->m_god.myth() == myth)
		{
			return c_trav;
		}
		nc_trav = nc_trav->m_succ;
	}
	return this;
}

Link *Link::advance(int n) const
{
	Link *trav = const_cast<Link *>(this);
	if (trav == nullptr)
	{
		return const_cast<Link*>(this);
	}
	if (n > 0)
	{
		while (n--)
		{
			if (trav->m_succ == nullptr)
			{
				return const_cast<Link*>(this);
			}
			trav = trav->m_succ;
		}
	}
	else if (n < 0)
	{
		while (n++)
		{
			if (trav->m_prev == nullptr)
			{
				return const_cast<Link*>(this);
			}
			trav = trav->m_prev;
		}
	}
	return trav;
}

Link *Link::add_ordered(Link *n)
{
	if (!n)
	{
		error("Node to insert cannot be null");
	}
	
	Link *trav = this;
	if (!trav)
	{
		return this;
	}

	// to make sure to start at head of the list
	while (trav->m_prev != nullptr)
	{
		trav = trav->m_prev;
	}

	while (trav->m_god.name() < n->m_god.name() && trav->m_succ)
	{
		trav = trav->m_succ;
	}

	if (n->m_god.name() < trav->m_god.name())
	{
		trav = trav->insert(n);
	}
	else
	{
		trav = trav->add(n);
	}
	return trav;
}

void print_all(Link *p)
{
	while (p->previous())
	{
		p = p->previous();
	}

	std::cout << "{\n";
	while (p)
	{
		std::cout << "Name: " << p->god().name()
			<< "; Myth: " << p->god().myth();
		if (p->god().vehicle() != "")
		{
			std::cout << "; Vehicle: " << p->god().vehicle();
		}
		else
		{
			std::cout << "; Vehicle: N/A";
		}
		std::cout << "; Weapon: " << p->god().weapon();
		if ((p = p->next()))
		{
			std::cout << "\n";
		}
	}
	std::cout << "\n}\n";
}


It's at line 49, the previous() function itself.

If my code is incorrect somewhere, it's in the code where I'm trying to free the memory allocated by the program.
How do I verify it, then?

That's a good question. How do you think you should go about verifying that you were deleting the same memory twice in your earlier code?

It's at line 49, the previous() function itself.

But the interesting place is found by following the stack trace back to the origin of the problem. Have you done that?

If my code is incorrect somewhere, it's in the code where I'm trying to free the memory allocated by the program.

Probably. But since you're not even getting to the point where you delete the memory what do you think you're doing wrong? Your exception is giving you a good hint but what do you think is the actual cause of the problem.

It's throwing the exception at line 92, the call to previous(). Pointer this must be becoming null at that point.

I don't know how to follow the stack trace. My diagnostic tools are only showing me the stack itself, and it only has three items in it aside from "External Code" at the start (previous() at line 49, print_all() at line 320, and main() at line 81), and two when the exception is thrown: lines 49 and 92. So the exception is thrown when it gets to line 92 and calls previous() which is defined at line 49 and this has become null by the point it gets there during that iteration of the loop (at line 89 in main). Am I right so far?

Is it because I shouldn't call previous() again after erase() has been called once? Should I put the call to previous() before the call to erase()? Or is there something wrong in the loop condition itself (this I doubt because I'm trying to stop the loop when previous() is pointing at nullptr).

It's throwing the exception at line 92, the call to previous(). Pointer this must be becoming null at that point.

What would make the pointer become null at that point? You need to look for something that modifies that pointer somewhere earlier in your code. Please show me what your call stack looks like when your debugger detects the error.

This is what my call stack looks like at the time of the crash.
1
2
#0 0x403746	Link::previous(this=0x0) (/main.cpp:44)
#1 0x40203a	main() (/main.cpp:87) 

The debugger detected the problem on line 44 (the previous() function) but you need to look at the earlier location (line 87 in the code I compiled probably around line 91 or 92 for you). Remember when the debugger detects a problem the problem usually has occurred earlier in your code. So you use the place where the debugger detects the problem and then go backwards until you see where the problem actually happens.

Is it because I shouldn't call previous() again after erase() has been called once?

I probably can't completely answer this question but yes you probably shouldn't be calling previous() after erase().

What happens to the three pointers (this, prev, succ) when you call erase?

How do I look at my stack trace, though?

What happens to the three pointers (this, prev, succ) when you call erase?


The first time erase() is called, trav is at the last node. So succ is pointing at nullptr. And erase() returns trav->m_succ. Is that bad?

I still have 68 out of the original 74 memory leaks, but the "this was nullptr" problem is solved.

Code:
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Exercises 11-13

#include <iostream>
#include <vld.h>
#include "../../cust_std_lib_facilities.h"

struct God
{
	God(const std::string &name, const std::string &myth, const std::string &vehicle, const std::string &weapon)
		: m_name{ name }, m_myth{ myth }, m_vehicle{ vehicle }, m_weapon{ weapon } { }

	std::string name() const { return m_name; }
	std::string myth() const { return m_myth; }
	std::string vehicle() const { return m_vehicle; }
	std::string weapon() const { return m_weapon; }

	void set_name(const std::string name) { m_name = name; }
	void set_myth(const std::string myth) { m_myth = myth; }
	void set_vehicle(const std::string vehicle) { m_vehicle = vehicle; }
	void set_weapon(const std::string weapon) { m_weapon = weapon; }
private:
	std::string m_name;
	std::string m_myth;
	std::string m_vehicle;
	std::string m_weapon;
};

class Link
{
public:
	Link(const God &god, Link *p = nullptr, Link *s = nullptr)
		: m_god{ god }, m_prev{ p }, m_succ{ s } { }
	Link *insert(Link *n);                                            // insert n before this object
	Link *add(Link *n);                                               // insert n after this object
	Link *erase();                                                    // remove this object from list
	Link *find(const std::string &name);                              // find node matching passed in name in list
	const Link *find(const std::string &name) const;                  // find node matching passed in name in const list
	Link *find_if_myth(const std::string &myth);		              // find node matching passsed in myth in list
	const Link *find_if_myth(const std::string &myth) const;          // find node matching passsed in myth in const list
	Link *advance(int n) const;                                       // advance n positions in list
	Link *add_ordered(Link *n);							              // insert n in its correct lexicographical position

	God god() const { return m_god; }
	Link *next() const { return m_succ; }
	Link *previous() const { return m_prev; }

private:
	God m_god;
	Link *m_prev;
	Link *m_succ;
};

void print_all(Link *p);

int main()
{
	try
	{
		Link *gods = new Link{ { "Odin", "Norse",
			"Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
		gods = gods->add_ordered(new Link{ { "Baldr", "Norse", "Ship called Hringorni", "None" } });
		gods = gods->add_ordered(new Link{ { "Thor", "Norse",
			"Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Hammer called Mjolnir" } });
		gods = gods->add_ordered(new Link{ { "Frejya", "Norse",
			"Chariot pulled by two cats", "Magic called seidr" } });
		gods = gods->add_ordered(new Link{ { "Ares", "Greek", "War chariot", "Sword and spear" } });
		gods = gods->add_ordered(new Link{ { "Zeus", "Greek",
			"A chariot pulled by the four major winds shaped as horses", "Thunderbolt" } });
		gods = gods->add_ordered(new Link{ { "Apollo", "Greek",
			"Chariot pulled by the four horses Aethon, Pyrois, Phlegon and Eous", "A bow" } });
		gods = gods->add_ordered(new Link{ { "Hera", "Greek", "A chariot drawn by peacocks", "Her intelligence" } });
		gods = gods->add_ordered(new Link{ { "Amaterasu", "Japanese", "", "Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata" } });
		gods = gods->add_ordered(new Link{ { "Susanoo", "Japanese", "", "Sword of Totsuka" } });
		gods = gods->add_ordered(new Link{ { "Izanagi", "Japanese", "", "Sword of Totsuka (later given to Susanoo)" } });
		gods = gods->add_ordered(new Link{ { "Bishamonten", "Japanese", "", "A spear" } });

		print_all(gods);

		Link *trav = gods;
		while (trav->next() != nullptr)
		{
			trav = trav->next();
		}

		while ((trav = trav->previous()) && trav->previous() != nullptr)
		{
			trav = trav->erase();
		}
		trav = trav->erase();
		gods = gods->erase();
		delete gods;
		gods = nullptr;
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << '\n';
		keep_window_open();
		return 1;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << "\n";
		keep_window_open();
		return 2;
	}
	catch (...)
	{
		std::cerr << "An unknown exception occurred\n";
		keep_window_open();
		return 3;
	}

	keep_window_open();
}

Link *Link::insert(Link *n)
{
	if (n == nullptr)
	{
		error("Node to add cannot be null");
	}
	n->m_succ = this;
	if (m_prev)
	{
		m_prev->m_succ = n;
	}
	n->m_prev = m_prev;
	m_prev = n;
	return n;
}

Link *Link::add(Link *n)
{
	if (n == nullptr)
	{
		error("Node to add cannot be null");
	}
	n->m_prev = this;
	if (m_succ)
	{
		m_succ->m_prev = n;
	}
	n->m_succ = m_succ;
	m_succ = n;
	return n;
}

Link *Link::erase()
{
	Link *trav = this;
	if (trav == nullptr)
	{
		return this;
	}
	if (trav->m_succ)
	{
		trav->m_succ->m_prev = trav->m_prev;
	}
	if (trav->m_prev)
	{
		trav->m_prev->m_succ = trav->m_succ;
	}
	return trav->m_succ;
}

Link *Link::find(const std::string &name)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		if (trav->m_god.name() == name)
		{
			return trav;
		}
		trav = trav->m_succ;
	}
	return this;
}

const Link *Link::find(const std::string &name) const
{
	const Link *c_trav = this;                    // const pointer
	Link *nc_trav = const_cast<Link*>(c_trav);    // non-const pointer
	while (c_trav != nullptr && nc_trav != nullptr)
	{
		if (c_trav->m_god.name() == name)
		{
			return c_trav;
		}
		nc_trav = nc_trav->m_succ;
	}
	return this;
}

Link *Link::find_if_myth(const std::string &myth)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		if (trav->m_god.myth() == myth)
		{
			return trav;
		}
		trav = trav->m_succ;
	}
	return this;
}

const Link *Link::find_if_myth(const std::string &myth) const
{
	const Link *c_trav = this;                    // const pointer
	Link *nc_trav = const_cast<Link*>(c_trav);    // non-const pointer
	while (c_trav != nullptr && nc_trav != nullptr)
	{
		if (c_trav->m_god.myth() == myth)
		{
			return c_trav;
		}
		nc_trav = nc_trav->m_succ;
	}
	return this;
}

Link *Link::advance(int n) const
{
	Link *trav = const_cast<Link *>(this);
	if (trav == nullptr)
	{
		return const_cast<Link*>(this);
	}
	if (n > 0)
	{
		while (n--)
		{
			if (trav->m_succ == nullptr)
			{
				return const_cast<Link*>(this);
			}
			trav = trav->m_succ;
		}
	}
	else if (n < 0)
	{
		while (n++)
		{
			if (trav->m_prev == nullptr)
			{
				return const_cast<Link*>(this);
			}
			trav = trav->m_prev;
		}
	}
	return trav;
}

Link *Link::add_ordered(Link *n)
{
	if (!n)
	{
		error("Node to insert cannot be null");
	}
	
	Link *trav = this;
	if (!trav)
	{
		return this;
	}

	// to make sure to start at head of the list
	while (trav->m_prev != nullptr)
	{
		trav = trav->m_prev;
	}

	while (trav->m_god.name() < n->m_god.name() && trav->m_succ)
	{
		trav = trav->m_succ;
	}

	if (n->m_god.name() < trav->m_god.name())
	{
		trav = trav->insert(n);
	}
	else
	{
		trav = trav->add(n);
	}
	return trav;
}

void print_all(Link *p)
{
	while (p->previous())
	{
		p = p->previous();
	}

	std::cout << "{\n";
	while (p)
	{
		std::cout << "Name: " << p->god().name()
			<< "; Myth: " << p->god().myth();
		if (p->god().vehicle() != "")
		{
			std::cout << "; Vehicle: " << p->god().vehicle();
		}
		else
		{
			std::cout << "; Vehicle: N/A";
		}
		std::cout << "; Weapon: " << p->god().weapon();
		if ((p = p->next()))
		{
			std::cout << "\n";
		}
	}
	std::cout << "\n}\n";
}


After this, I also need help on moving nodes from one list to another. For the rest of the exercise.
The first time erase() is called, trav is at the last node. So succ is pointing at nullptr. And erase() returns trav->m_succ. Is that bad?


How many times are you calling erase()?

How many pointers did I ask about?

I still have 68 out of the original 74 memory leaks, but the "this was nullptr" problem is solved.

That's good I suppose, now when you figure out how to handle the other 68 memory leaks let me know.



I'm asking you because I don't know. Where else do I need to call delete, and on what?

I'm only calling erase() three times, but one of them is in a loop so it'll be called as many times as there are nodes in the list it's being called on, plus two more times.

And you only asked about three pointers. Why do you ask?

Edit: Do I need a user-defined destructor? And if so, what should I explicitly destroy in it?
Last edited on
And you only asked about three pointers. Why do you ask?

Because you don't seem to understand the importance of those pointers.

Do I need a user-defined destructor?

Why?

What would be the purpose of this destructor?

Where would you use this destructor?


I'm only calling erase() three times, but one of them is in a loop so it'll be called as many times as there are nodes in the list it's being called on, plus two more times.

Why are you calling erase() this many times?

Where else do I need to call delete, and on what?

You should know the answer to this, if you don't then there is really no need to proceed.

By the way the best way to avoid the memory leaks is not to use dynamic memory in the first place.

Pages: 1... 910111213... 16