C++

Forum

 
PPP2 Chapter 17 Exercise 11

Pages: 123... 16
DragonOsman (715)
I'm making (kind of) another thread for this. Sorry about this.

Anyway, the specs for it are as follows:

Complete the “list of gods” example from §17.10.1 and run it.


My code is:
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
 
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Section 17.9.4
// Doubly Linked Lists

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

class Link
{
public:
	std::string value;

	Link(const std::string &v, Link *p = nullptr, Link *s = nullptr);

	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 &s);    // find s in list
	const Link *find(const std::string &s) const;	    // find s in const list

	Link *advance(int n) const;    // advance n positions in list
	
	Link *next() const { return succ; }
	Link *previous() const { return prev; }

private:
	Link *prev;
	Link *succ;
};

void print_all(Link *p);

int main()
{
	Link *norse_gods = new Link{ "Thor" };
	norse_gods = norse_gods->insert(new Link{ "Odin" });
	norse_gods = norse_gods->insert(new Link{ "Zeus" });
	norse_gods = norse_gods->insert(new Link{ "Freia" });

	Link *greek_gods = new Link{ "Hera" };
	greek_gods = greek_gods->insert(new Link{ "Athena" });
	greek_gods = greek_gods->insert(new Link{ "Mars" });
	greek_gods = greek_gods->insert(new Link{ "Poseidon" });

	Link *p = greek_gods->find("Mars");
	if (p)
	{
		p->value = "Ares";
	}

	Link *p2 = norse_gods->find("Zeus");
	if (p2)
	{
		if (norse_gods)
		{
			norse_gods = p2->next();
			p2->erase();
			greek_gods = greek_gods->insert(p2);
		}
	}

	print_all(norse_gods);
	print_all(greek_gods);

	keep_window_open();
}

Link::Link(const std::string &v, Link *p, Link *s)
	: value{ v }, prev{ p }, succ{ s }
{

}

Link *Link::insert(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->succ = this;
	if (prev)
	{
		prev->succ = n;
	}
	n->prev = prev;
	prev = n;
	return n;
}

Link *Link::add(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->prev = this;
	if (succ)
	{
		succ->prev = n;
	}
	n->succ = succ;
	succ = n;
	return n;
}

Link *Link::erase()
{
	if (succ)
	{
		succ->prev = prev;
	}
	if (prev)
	{
		prev->succ = succ;
	}
	return succ;
}

Link *Link::find(const std::string &s)
{
	std::size_t i = 0;
	while (succ != nullptr)
	{
		if (value == s)
		{
			return this;
		}
		succ++;
		++i;
	}
	return nullptr;
}

const Link *Link::find(const std::string &s) const
{
	std::size_t i = 0;
	while (succ != nullptr)
	{
		if (value == s)
		{
			return this;
		}
		++i;
	}
	return nullptr;
}

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

void print_all(Link *p)
{
	std::cout << "{ ";
	while (p)
	{
		std::cout << p->value;
		if (p == p->next())
		{
			std::cout << ", ";
		}
		std::cout << " }";
	}
}


In the book, for the erase(), find(), advance() and add() methods, only the non-member function versions are given and we have to write the method-versions ourselves. That's what I'm having trouble with. I think the insert() and add() ones are fine, but I need help on the others - especially advance() because I don't know what the class-member equivalent of p = p->succ; would be.

The main problem I have is that the program output is a completely blank screen with a blinking prompt and nothing more.
Last edited on
jlb (4973)
I suggest that you get the following to work properly before proceeding.
1
2
3
4
 
int main()
{
	Link *norse_gods = new Link{ "Thor" };
	print_all(norse_gods);


DragonOsman (715)
How about now?
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
 
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Section 17.9.4
// Doubly Linked Lists

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

class Link
{
public:
	std::string value;

	Link(const std::string &v, Link *p = nullptr, Link *s = nullptr);

	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 &s);                // find s in list
	const Link *find(const std::string &s) const;    // find s in const list

	Link *advance(int n) const;                      // advance n positions in list
	
	Link *next() const { return succ; }
	Link *previous() const { return prev; }

private:
	Link *prev;
	Link *succ;
};

void print_all(Link *p);

int main()
{
	Link *norse_gods = new Link{ "Thor" };
	norse_gods = norse_gods->insert(new Link{ "Odin" });
	norse_gods = norse_gods->insert(new Link{ "Zeus" });
	norse_gods = norse_gods->insert(new Link{ "Freia" });

	Link *greek_gods = new Link{ "Hera" };
	greek_gods = greek_gods->insert(new Link{ "Athena" });
	greek_gods = greek_gods->insert(new Link{ "Mars" });
	greek_gods = greek_gods->insert(new Link{ "Poseidon" });

	Link *p = greek_gods->find("Mars");
	if (p)
	{
		p->value = "Ares";
	}

	Link *p2 = norse_gods->find("Zeus");
	if (p2)
	{
		if (p2 == norse_gods)
		{
			norse_gods = p2->next();
		}
		p2->erase();
		greek_gods = greek_gods->insert(p2);
	}

	print_all(norse_gods);
	print_all(greek_gods);

	keep_window_open();
}

Link::Link(const std::string &v, Link *p, Link *s)
	: value{ v }, prev{ p }, succ{ s }
{

}

Link *Link::insert(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->succ = this;
	if (prev)
	{
		prev->succ = n;
	}
	n->prev = prev;
	prev = n;
	return n;
}

Link *Link::add(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->prev = this;
	if (succ)
	{
		succ->prev = n;
	}
	n->succ = succ;
	succ = n;
	return n;
}

Link *Link::erase()
{
	if (succ)
	{
		succ->prev = prev;
	}
	if (prev)
	{
		prev->succ = succ;
	}
	return succ;
}

Link *Link::find(const std::string &s)
{
	std::size_t i = 0;
	while (succ != nullptr)
	{
		if (value == s)
		{
			return this;
		}
		succ++;
		++i;
	}
	return nullptr;
}

const Link *Link::find(const std::string &s) const
{
	std::size_t i = 0;
	while (succ != nullptr)
	{
		if (value == s)
		{
			return this;
		}
		++i;
	}
	return nullptr;
}

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

void print_all(Link *p)
{
	std::cout << "{ ";
	while (p)
	{
		std::cout << p->value;
		if (p == p->next())
		{
			std::cout << ", ";
		}
		std::cout << " }";
	}
}
jlb (4973)
What about it? Can you even print out that first line correctly? I doubt it since it doesn't look like you changed your print_all() function at all.

Thomas1965 (4571)
On line 124 you have an endless loop - succ never becomes a nullptr.
Easy to when you set a breakpoint at line line 124 and step through it.
DragonOsman (715)
@jlb: I copied the print_all() function from the book. I may have mistake, though. I'll check.

@Thomas1965: Yeah, thanks. I do realize that, but what should be the loop condition there?

Edit: In the book, it's like this:
1
2
3
4
5
6
7
8
9
 
void print_all(Link* p)
{
    cout << "{ ";
    while (p) {
        cout << p–>value;
        if (p=p–>next()) cout << ", ";
    }
    cout << " }";
}


When I tried to compile it, I got a warning saying that p=p–>next() should be changed to p==p–>next(). That's why it's like that.
Last edited on
jlb (4973)
When I tried to compile it, I got a warning saying that p=p–>next() should be changed to p==p–>next(). That's why it's like that.

But you made a mistake changing the '=' to '==', you should have used parentheses instead. Also your last cout is in the wrong place in your code but correct in the above snippet.

1
2
3
4
5
6
7
8
9
10
11
 
void print_all(Link* p)
{
    std::cout << "{ ";
    while (p) 
    {
        std::cout << p–>value;
        if((p = p–>next())) 
            cout << ", ";
    }
    std::cout << " }\n";
}


Edit: By changing the operator you created an endless loop because you never modify where that pointer is pointing.


I do realize that, but what should be the loop condition there?

You really need to try to reason out what should be done in that function for yourself. Recheck the code from the book for hints.
Last edited on
DragonOsman (715)
All I can tell from the book for that is that for the find() function, in the non-member function, you check if the Link* object passed to the function is null or not. As long as it isn't, and if the value of that pointer object is the same as passed in string, return the pointer. If it's not, and it's not the same value yet, advance to the next link in the linked-list and continue looking. If after that you've found no match, return null. But I get confused on this because of the "this" pointer. How should I word the condition to have it repeat as long as I need to and to have it return the right thing at the right time? Do I return the value of whatever the "this" pointer is pointing to? Do I return the "this" pointer itself?

Also, do you mean I have to put parentheses around the assignment operator? Why?

Edit: I changed the non-const find() function to this for now:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Link *Link::find(const std::string &s)
{
	std::size_t i = 0;
	while (value != s)
	{
		if (value == s)
		{
			return this;
		}
		succ++;
		++i;
	}
	return nullptr;
}

I thought that the loop should probably go as long as the value of the current node isn't the same as the passed in string. It could be wrong, but that's all I got for now.

And where do I put the parentheses in print_all()?
Last edited on
jlb (4973)
Also, do you mean I have to put parentheses around the assignment operator? Why?

Look at the code I provided, it has the parentheses added. Do you understand that you need to change the pointer, not just compare the pointer to something?

All I can tell from the book for that is that for the find() function, in the non-member function, you check if the Link* object passed to the function is null or not.

Did you look at the "member" function? Your non-member function should internally look about the same. Part of the differences will be that you need some way of accessing the private class variables.

Do I return the value of whatever the "this" pointer is pointing to? Do I return the "this" pointer itself?

What? Look at your class member variables, which one allows you to traverse the list in the correct direction?
Last edited on
Thomas1965 (4571)
I think your find function should look more like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Link *Link::find(const std::string &s)
{
  Link* tmp = succ;

  while (tmp != nullptr)
  {
    if (tmp->value == s)
    {
      return tmp;
    }
    tmp= tmp->next();
  }
  return nullptr;
}
Last edited on
DragonOsman (715)
@jlb: The one in the book is the one that isn't a class member function, right? The one with the "this" pointer should be class member function. That's the one I'm trying to ask for help on here.

@Thomas1965: So basically it's creating a temporary pointer for traversing? I see. Makes sense.

Edit: This is the output I get now:

{ Freia, Zeus, Poseidon, Ares, Athena, Hera }{ Zeus, Poseidon, Ares, Athena, Hera }Please enter a character to exit
k
Press any key to continue . . .


Both are lists of Greek Gods. In main(), the list of Norse Gods is also being printed. Am I still doing something wrong?

Here's the 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
 
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Section 17.9.4
// Doubly Linked Lists

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

class Link
{
public:
	std::string value;

	Link(const std::string &v, Link *p = nullptr, Link *s = nullptr);

	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 &s);                // find s in list
	const Link *find(const std::string &s) const;    // find s in const list

	Link *advance(int n) const;                      // advance n positions in list
	
	Link *next() const { return succ; }
	Link *previous() const { return prev; }

private:
	Link *prev;
	Link *succ;
};

void print_all(Link *p);

int main()
{
	Link *norse_gods = new Link{ "Thor" };
	norse_gods = norse_gods->insert(new Link{ "Odin" });
	norse_gods = norse_gods->insert(new Link{ "Zeus" });
	norse_gods = norse_gods->insert(new Link{ "Freia" });

	Link *greek_gods = new Link{ "Hera" };
	greek_gods = greek_gods->insert(new Link{ "Athena" });
	greek_gods = greek_gods->insert(new Link{ "Mars" });
	greek_gods = greek_gods->insert(new Link{ "Poseidon" });

	Link *p = greek_gods->find("Mars");
	if (p)
	{
		p->value = "Ares";
	}

	Link *p2 = norse_gods->find("Zeus");
	if (p2)
	{
		if (p2 == norse_gods)
		{
			norse_gods = p2->next();
		}
		p2->erase();
		greek_gods = greek_gods->insert(p2);
	}

	print_all(norse_gods);
	print_all(greek_gods);

	keep_window_open();
}

Link::Link(const std::string &v, Link *p, Link *s)
	: value{ v }, prev{ p }, succ{ s }
{

}

Link *Link::insert(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->succ = this;
	if (prev)
	{
		prev->succ = n;
	}
	n->prev = prev;
	prev = n;
	return n;
}

Link *Link::add(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->prev = this;
	if (succ)
	{
		succ->prev = n;
	}
	n->succ = succ;
	succ = n;
	return n;
}

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

Link *Link::find(const std::string &s)
{
	Link *trav = succ;
	while (trav != nullptr)
	{
		if (trav->value == s)
		{
			return trav;
		}
		trav = trav->succ;
	}
	return nullptr;
}

const Link *Link::find(const std::string &s) const
{
	Link *trav = succ;
	while (trav != nullptr)
	{
		if (trav->value == s)
		{
			return trav;
		}
		trav = trav->succ;
	}
	return nullptr;
}

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

void print_all(Link *p)
{
	std::cout << "{ ";
	while (p) 
	{
		std::cout << p->value;
		if ((p = p->next()))
		{
			std::cout << ", ";
		}
	}
	std::cout << " }";
}


Edit2: And how did Freia get in there?
Last edited on
jlb (4973)
The one in the book is the one that isn't a class member function, right?

Okay, but the basic logic will still need to be the same. The logic you used in your original member function doesn't really resemble the logic in the non-member function, right?

Your original code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Link *Link::find(const std::string &s)
{
	std::size_t i = 0;
	while (value != s)
	{
		if (value == s)
		{
			return this;
		}
		succ++;
		++i;
	}
	return nullptr;
}


The code from the book:

1
2
3
4
5
6
7
8
9
10
 
Link* find(Link* p, const std::string& s)
{
    while(p)
    {
        if(p->value == s)
            return p;
        p = p->succ;
    }
    return nullptr;
}


In this code you need to understand what the parameter p really is inside that function. You also need to understand why Thomas used a local pointer variable instead of using one of the class member variables. By the way I don't believe that Thomas' code is completely correct. I believe that succ is a pointer to the next item in the list you need to start at the first item.

EDIT: By the way why is value in the public section of the class?
Last edited on
DragonOsman (715)
Dr. Stroustrup himself made it public in the book. I'll have to look at the explanation again for why.

Anyways. So how do I point to the root node or to the one right after the root node? The one I should point to is one of them, right?

And I think my erase() might be wrong as well. It seems like it's erasing the entire nose_god list. If that's the case, how do I fix it?

Edit:

We left value as a public member because (so far) we have no reason not to; it is “just data.”


I'm guessing he means it's not important data that needs to be made private.
Last edited on
JLBorges (13770)
> why is value in the public section of the class?

There is no identifiable invariant that can be associated with the member object value; ergo public.
(it is “just data.”)

There are clear invariants associated with the members prev and succ; so those two are private.
Last edited on
DragonOsman (715)
What does the term "invariant" mean in this context again? I remember something related to error-checking, but I'm not clear on it.

Anyway,

Anyways. So how do I point to the root node or to the one right after the root node? The one I should point to is one of them, right?

And I think my erase() might be wrong as well. It seems like it's erasing the entire nose_god list. If that's the case, how do I fix it?

...Anyone? Do I just have the temporary pointer assigned the same value as "this"?

Edit:

Okay, I had to do a const_cast in advance(), but aside from that it worked (assigning trav to "this"). I'm just stumped on the const version of find(). Assigning to "this" there won't work (and I don't want to make trav a const pointer). But at least it's printing the lists out correctly now.

Here's the 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
 
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Section 17.9.4
// Doubly Linked Lists

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

class Link
{
public:
	std::string value;

	Link(const std::string &v, Link *p = nullptr, Link *s = nullptr);

	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 &s);                // find s in list
	const Link *find(const std::string &s) const;    // find s in const list

	Link *advance(int n) const;                      // advance n positions in list
	
	Link *next() const { return succ; }
	Link *previous() const { return prev; }

private:
	Link *prev;
	Link *succ;
};

void print_all(Link *p);

int main()
{
	Link *norse_gods = new Link{ "Thor" };
	norse_gods = norse_gods->insert(new Link{ "Odin" });
	norse_gods = norse_gods->insert(new Link{ "Zeus" });
	norse_gods = norse_gods->insert(new Link{ "Freia" });

	Link *greek_gods = new Link{ "Hera" };
	greek_gods = greek_gods->insert(new Link{ "Athena" });
	greek_gods = greek_gods->insert(new Link{ "Mars" });
	greek_gods = greek_gods->insert(new Link{ "Poseidon" });

	Link* p = greek_gods->find("Mars");
	if (p)
	{
		p->value = "Ares";
	}

	Link* p2 = norse_gods->find("Zeus");
	if (p2) 
	{
		if (p2 == norse_gods)
		{
			norse_gods = p2->next();
		}
		p2->erase();
		greek_gods = greek_gods->insert(p2);
	}

	print_all(norse_gods);
	std::cout << '\n';

	print_all(greek_gods);
	std::cout << '\n';

	keep_window_open();
}

Link::Link(const std::string &v, Link *p, Link *s)
	: value{ v }, prev{ p }, succ{ s }
{

}

Link *Link::insert(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->succ = this;
	if (prev)
	{
		prev->succ = n;
	}
	n->prev = prev;
	prev = n;
	return n;
}

Link *Link::add(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->prev = this;
	if (succ)
	{
		succ->prev = n;
	}
	n->succ = succ;
	succ = n;
	return n;
}

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

Link *Link::find(const std::string &s)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		if (trav->value == s)
		{
			return trav;
		}
		trav = trav->succ;
	}
	return nullptr;
}

const Link *Link::find(const std::string &s) const
{
	Link *trav = succ;
	while (trav != nullptr)
	{
		if (trav->value == s)
		{
			return trav;
		}
		trav = trav->succ;
	}
	return nullptr;
}

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

void print_all(Link *p)
{
	std::cout << "{ ";
	while (p) 
	{
		std::cout << p->value;
		if ((p = p->next()))
		{
			std::cout << ", ";
		}
	}
	std::cout << " }";
}


And the output:
{ Freia, Odin, Thor }
{ Zeus, Poseidon, Ares, Athena, Hera }
Please enter a character to exit
k
Press any key to continue . . .
Last edited on
JLBorges (13770)
> What does the term "invariant" mean in this context again?

In general, "an invariant is a condition that can be relied upon to be true during execution of a program, or during some portion of it. It is a logical assertion that is held to always be true during a certain phase of execution."
https://en.wikipedia.org/wiki/Invariant_(computer_science)

In this particular context, we are talking about a class invariant. "a class invariant (or type invariant) is an invariant used to constrain objects of a class. Methods of the class should preserve the invariant. The class invariant constrains the state stored in the object."
https://en.wikipedia.org/wiki/Class_invariant

An example of an invariant that could (should) be asserted for the above class is:
assert( succ == nullptr || succ->prev == this ) ;
DragonOsman (715)
Thanks for the info.

What about the code I posted, though? How do I fix the remaining problems (I think there are some left, even though the output is the desired one now)?

Edit: What's the reason for putting "succ == nullptr" in the assert() macro call? We don't want to be true, do we?
Last edited on
JLBorges (13770)
> What's the reason for putting "succ == nullptr" in the assert() macro call? We don't want to be true, do we?

For the last node in the list, it must be true.


> What about the code I posted, though?

I would write something like this.
(I wouldn't want the user of the list to be responsible for establishing and maintaining the class invariant):

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
 
#include <string>
#include <cassert>
#include <algorithm>

namespace my
{
    struct str_list
    {
        std::size_t size() const { return sz ; }
        bool empty() const { return size() == 0 ; }

        // a constructor must establish the invariant
        str_list() { assert( valid() ) ; }

        str_list( std::initializer_list<std::string> ilist )
        {
            for( const std::string& str : ilist ) push_back(str) ;
            assert( valid() ) ;
        }

        str_list( const str_list& that )
        {
            assert( valid() ) ; // we have initialised our list to a  valid state
            assert( that.valid() ) ; // we have a valid list to copy from
            for( auto lnk = that.first ; lnk != nullptr ; lnk = lnk->next )
                push_back( lnk->value ) ;
            assert( valid() ) ;
        }

        str_list( str_list&& that )
        {
            assert( valid() ) ; // we have initialised our list to a  valid state
            assert( that.valid() ) ; // we have a valid list to move from
            swap(that) ;
        }

        str_list& operator= ( str_list that ) noexcept
        {
           assert( valid() ) ; // we have a valid list to start with
           assert( that.valid() ) ; // we have a valid list to copy from
           swap(that) ;
           return *this ;
        }

        // the destructor starts (but need not end) with a valid list
        ~str_list()
        {
            assert( valid() ) ;
            while( !empty() ) pop_back() ;
        }

        void swap( str_list& that ) noexcept
        {
           assert( valid() && that.valid() ) ; // we have two valid lists to swap
           using std::swap ;
           swap( first, that.first ) ;
           swap( last, that.last ) ;
           swap( sz, that.sz ) ;
        }

        void push_back( std::string str )
        {
            assert( valid() ) ; // modifier: we have a valid list to start with

            if( empty() ) first = last = new link( std::move(str) ) ;
            else
            {
                last->next = new link( str, nullptr, last ) ;
                last = last->next ;
            }
            ++sz ;

            assert( valid() ) ; // modifier: we have a valid list at the end
        }

        void pop_back()
        {
            assert( valid() ) ; // modifier: we have a valid list to start with
            assert( !empty() ) ; // invariant for this operation

            if( size() == 1 )
            {
                delete first ;
                first = last = nullptr ;
            }
            else
            {
                last = last->prev ;
                delete last->next ;
                last->next = nullptr ;
            }
            --sz ;

            assert( valid() ) ; // modifier: we have a valid list at the end
        }

        template < typename FN > void for_each( FN fn ) const
        {
            assert( valid() ) ; // selector: we have a valid list to start with
            for( auto lnk = first ; lnk != nullptr ; lnk = lnk->next )
            {
                const std::string& str = lnk->value ;
                fn(str) ;
            }
            // selector: no need to test the invariant (we haven't changed the list)
        }

        // TO DO: other list operations

        private:

            struct link
            {
                link( std::string value, link* next = nullptr, link* prev = nullptr )
                    : value( std::move(value) ), next(next), prev(prev) {}

                std::string value ;
                link* next ;
                link* prev ;
            };

            link* first = nullptr ;
            link* last = nullptr ;
            std::size_t sz = 0 ;

            // invariant for a valid link: must return true
            static bool valid( const link* lnk )
            {
                return ( lnk != nullptr ) &&
                       ( lnk->next == nullptr || lnk->next->prev == lnk ) &&
                       ( lnk->prev == nullptr || lnk->prev->next == lnk ) ;
            }

            // class invariant: must return true if there is no programming error
            bool valid() const
            {
                if( first && first->prev ) return false ;
                if( last && last->next ) return false ;

                if( empty() && ( first || last || sz ) ) return false ;

                for( auto lnk = first ; lnk != nullptr ; lnk = lnk->next )
                    if( !valid(lnk) ) return false ;

                return true ;
            }
    };

    void swap( str_list& a, str_list& b ) { a.swap(b) ; }
}

http://coliru.stacked-crooked.com/a/ba93cef17a46d289
DragonOsman (715)
I meant to ask about my implementation of the exercise solution. Especially find(), including the const version since I don't know what to assign trav to in that one ("this" won't work because it's a const pointer in a const function). I wasn't asking about assert() for this exercise.

Also, exercise 12:
Why did we define two versions of find()?
Is it because there's a need for a const overload in cases where we need to find a const node in the list? Or am I dead wrong?
Last edited on
JLBorges (13770)
> Why did we define two versions of find()?
> Is it because there's a need for a const overload in cases where we need to find a const node in the list?

It is because we may need to find a node in a const list.
(But the member object 'value' of a node in a const list should not be modifiable.)
See 'What’s the deal with “const-overloading”?' https://isocpp.org/wiki/faq/const-correctness
Pages: 123... 16