C++

Forum

 
increasing value of each element in std::list<int> by some number

DragonOsman (715)
I need to increase the value of each element in a std::list<int> by 5. The code I have turns a list with int elements {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} to this:

5
1
6
3
4
7
6
7
8
8


This is my code for this operation right now:
1
2
3
4
5
6
7
 
int n = 0;
for (auto iter = lst2.begin(); iter != lst2.end(); ++iter)
{
	std::advance(iter, n);
	*iter = n + 5;
	n++;
}
MikeyBoy (5631)
On each iteration of the loop, you're incrementing your iterator twice - once on line 4, and once again on line 6. Thus, you're only modifying every second value.

(It should have been obvious to you that you're only modifying every second value, just from looking at your results.)

EDIT: My apologies - I'd misread your original post.
Last edited on
DragonOsman (715)
So I don't need the n++?

Edit: Taking out n++ gives this output:
5
5
5
5
5
5
5
5
5
5
Last edited on
MikeyBoy (5631)
Why do you think you need it?

Why do you think you need the std::advance?

How many increments do you think you need on each iteration?

This is where you get to think about the logic of your code.
Repeater (3046)

So what exactly is n for in your code? What does it represent? It looks like you're trying to use it as a completely independent way of knowing what the value of *iter is? Why bother? If you want to know the value of *iter, here's the best way: *iter
Last edited on
MikeyBoy (5631)
Please ignore my previous posts. I'd misread your OP.
DragonOsman (715)
@Repeater: n is supposed to be the value I add 5 to and place at the position given by iter. I'm not trying to have two iterators here, I'm trying to add 5 to each element in the list.

Linked lists don't have a subscript operator, so how do I get at each element in the list and add 5 to it? If it were an array or a vector, I could've just done vector[i] = i + 5; or array[i] = i + 5;, but I can't do that here.

Could someone help me out on my custom STL-style linked list (the thread I made asking for that)? How do I define constructors and destructors for the list? And how do I initialize the first and last nodes (do I allocate them in the constructor?)? I think I can do the insertion and deletion myself now that I think of it.
Last edited on
Repeater (3046)
@Repeater: n is supposed to be the value I add 5 to


No no no. You said
I need to increase the value of each element in a std::list<int> by 5.
You said you needed to add five to the value of each element in a list. n has nothing to do with that.

1
2
3
4
 
for (auto iter = lst2.begin(); iter != lst2.end(); ++iter)
{
  *iter += 5;
}
Last edited on
DragonOsman (715)
Yeah, that did it. I did do that, but it took me a while to see that that's what I wanted.

Now could someone please tell me why my compiler keeps saying that p.curr->succ and p.curr->prev here in this code are
<unknown> <unnamed>::succ
and
<unknown> <unnamed>::prev
(in insert())? It's also saying that p.curr itself is
<unknown> list<Elem>::iterator::curr
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
 
#ifndef LIST_H_
#define LIST_H_

template<typename Elem>
class Link
{
public:
	Link *prev;
	Link *succ;
	Elem val;
};

template<typename Elem>
class list
	// representation and implementation details
{
public:
	using size_type = unsigned long;
	using value_type = Elem;
	class iterator;
	class const_iterator;

	iterator begin() { return *first; }
	iterator end() { return *last; }
	const_iterator begin() const { return *first; }
	const_iterator end() const { return *last;  }

	size_type size();

	iterator insert(iterator p, const Elem &v);		// insert v into list after p
	iterator erase(iterator p);						// remove p from list

	void push_back(const Elem &v);					// insert v at end
	void push_front(const Elem &v);					// insert v at front
	void pop_front();		// remove the first element
	void pop_back();		// remove the last element

	Elem &front();			// the first element
	Elem &back();			// the last element

private:
	Link<Elem> *first;
	Link<Elem> *last;
};

#endif

// requires Element<Elem>() (§19.3.3)
template<typename Elem>
class list<Elem>::iterator
{
	Link<Elem> *curr;	// current link
public:
	iterator(Link<Elem> *p)
		: curr{ p } { }

	iterator &operator++() { curr = curr->succ; return *this; }		// forward
	iterator &operator--() { curr = curr->prev; return *this; }		// backword
	Elem &operator*() { return curr->val; }

	bool operator==(const iterator &b) { return curr == b.curr; }
	bool operator!=(const iterator &b) { return curr != b.curr; }
};

template<typename Elem>
typename list<Elem>::iterator list<Elem>::insert(list<Elem>::iterator p, const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;
	if (new_node)
	{
		if (p.curr->prev == nullptr)
		{
			// insert at beginning of list
			push_front(new_node->val);

			// return iterator to front of list
			return begin();
		}
		else if (p.curr->succ == nullptr)
		{
			// insert at end of list
			push_back(new_node->val);

			// return iterator to end of list
			return end();
		}
		else if (p.curr->succ && p.curr->prev)
		{
			new_node->prev = p.curr;
			if (p.curr->succ)
			{
				p.curr->succ->prev = new_node;
			}
			new_node->succ = p.curr->succ;
			p.curr->succ = new_node;
			return iterator(p.curr);
		}
	}
	return this;
}

template<typename Elem>
typename list<Elem>::size_type list<Elem>::size()
{

}


Also, how do I implement size()? And do I just initialize *first and *last in the constructor via new? And if so, how do I delete the nodes in the destructor? I did make a separate thread for this, but it has no replies.
Last edited on
Repeater (3046)
Have internal variable size. Begins at zero. When someone adds a node to the list, increment it. When someone removes a node from the list, decrement it. When someone asks what size the list is, return it.
DragonOsman (715)
So this wouldn't be good?
1
2
3
4
5
6
7
8
9
10
11
12
 
template<typename Elem>
typename list<Elem>::size_type list<Elem>::size()
{
	typename iterator iter = begin();
	typename size_type size = 0;
	while (iter != end())
	{
		iter++;
		size++;
	}
	return size;
}


Here's the whole 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
 
#ifndef LIST_H_
#define LIST_H_

template<typename Elem>
class Link
{
public:
	Link *prev;
	Link *succ;
	Elem val;
};

template<typename Elem>
class list
	// representation and implementation details
{
public:
	using size_type = unsigned long;
	using value_type = Elem;
	class iterator;
	class const_iterator;

	~list();

	iterator begin();
	iterator end();
	const_iterator begin() const { return *first; }
	const_iterator end() const { return *last;  }

	size_type size();

	iterator insert(iterator p, const Elem &v);		// insert v into list after p
	iterator erase(iterator p);						// remove p from list

	void push_back(const Elem &v);					// insert v at end
	void push_front(const Elem &v);					// insert v at front
	void pop_front();		// remove the first element
	void pop_back();		// remove the last element

	Elem &front() { return *first; }		// the first element
	Elem &back() { return *last; }			// the last element

private:
	Link<Elem> *first;
	Link<Elem> *last;
};

#endif

// requires Element<Elem>() (§19.3.3)
template<typename Elem>
class list<Elem>::iterator
{
	Link<Elem> *curr;	// current link
public:
	iterator(Link<Elem> *p)
		: curr{ p } { }

	iterator &operator++() { curr = curr->succ; return *this; }		// forward
	iterator &operator--() { curr = curr->prev; return *this; }		// backword
	Elem &operator*() { return curr->val; }

	bool operator==(const iterator &b) { return curr == b.curr; }
	bool operator!=(const iterator &b) { return curr != b.curr; }
};

template<typename Elem>
typename list<Elem>::iterator list<Elem>::insert(typename list<Elem>::iterator p, const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;
	if (new_node)
	{
		if (p.curr->prev == nullptr)
		{
			// insert at beginning of list
			push_front(new_node->val);

			// return iterator to front of list
			return begin();
		}
		else if (p.curr->succ == nullptr)
		{
			// insert at end of list
			push_back(new_node->val);

			// return iterator to end of list
			return end();
		}
		else if (p.curr->succ && p.curr->prev)
		{
			new_node->prev = p.curr;
			if (p.curr->succ)
			{
				p.curr->succ->prev = new_node;
			}
			new_node->succ = p.curr->succ;
			p.curr->succ = new_node;
			return iterator(p.curr);
		}
	}
	return this;
}

template<typename Elem>
typename list<Elem>::iterator list<Elem>::erase(typename list<Elem>::iterator p)
{
	Link<Elem> *trav = p.curr;
	if (trav)
	{
		if (trav->succ)
		{
			trav->succ->prev = trav->prev;
		}
		if (trav->prev)
		{
			trav->prev->succ = trav->succ;
		}
		return trav->succ;
	}
}

template<typename Elem>
typename list<Elem>::size_type list<Elem>::size()
{
	typename iterator iter = begin();
	typename size_type size = 0;
	while (iter != end())
	{
		iter++;
		size++;
	}
	return size;
}

template<typename Elem>
void list<Elem>::push_back(const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;

	typename iterator iter = end();
	iter.curr->succ = new_node;
	new_node->prev = iter.curr;
	last = new_node;
}

template<typename Elem>
void list<Elem>::push_front(const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;

	typename iterator iter = begin();
	iter.curr->prev = new_node;
	new_node->succ = iter.curr;
	first = new_node;
}

template<typename Elem>
typename list<Elem>::iterator list<Elem>::end()
{
	typename list<Elem>::iterator trav = list<Elem>::iterator::curr;
	while (trav.curr->succ)
	{
		trav++;
	}
	return trav;
}

template<typename Elem>
typename list<Elem>::iterator list<Elem>::begin()
{
	typename list<Elem>::iterator trav = list<Elem>::iterator::curr;
	while (trav.curr->prev)
	{
		trav--;
	}
	return trav;
}

template<typename Elem>
void list<Elem>::pop_back()
{

}

template<typename Elem>
void list<Elem>::pop_front()
{

}


I tried implementing it from my own understanding, but I need to ask if I defined the insertion and deletion operations correctly. I'm not sure how to define the destructor and the pop_back and pop_front functions, either.

This is the function I'm using it in:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void f()
{
	list<int> lst;
	for (int x; std::cin >> x;)
	{
		lst.push_front(x);
	}

	list<int>::iterator p = high(lst.begin(), lst.end());

	// did we reach the end?
	if (p == lst.end())
	{
		std::cout << "The list is empty\n";
	}
	std::cout << "The highest value was " << *p << '\n';
}


And this is high(): 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
emplate<typename Iter>
Iter high(Iter first, Iter last)
// return an iterator to the element in [first,last) that has the highest value
{
	Iter high = first;
	for (Iter p = first; p != last; ++p)
	{
		if (*high < *p)
		{
			high = p;
		}
	}
	return high;
}


From the looks of how it's being used in the function f(), it seems like I shouldn't add a constructor? If so, do I need a destructor? I think I need one that deletes the allocated memory, but I don't get how to define it.
Last edited on
DragonOsman (715)
I'm lost on how to how to insert a node relative to an iterator position when iterator::curr is a private member which I can't access from the list class. What should I do?

This is what I have right 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
188
 
#ifndef LIST_H_
#define LIST_H_

template<typename Elem>
class Link
{
public:
	Link *prev;
	Link *succ;
	Elem val;
};

template<typename Elem>
class list
	// representation and implementation details
{
public:
	using size_type = unsigned long;
	using value_type = Elem;
	class iterator;
	class const_iterator;

	//~list();

	iterator begin();
	iterator end();
	const_iterator begin() const { return *first; }
	const_iterator end() const { return *last;  }

	size_type size();

	iterator insert(iterator p, const Elem &v);		// insert v into list after p
	iterator erase(iterator p);						// remove p from list

	void push_back(const Elem &v);					// insert v at end
	void push_front(const Elem &v);					// insert v at front
	void pop_front();		// remove the first element
	void pop_back();		// remove the last element

	Elem &front() { return *first; }		// the first element
	Elem &back() { return *last; }			// the last element

private:
	Link<Elem> *first;
	Link<Elem> *last;
};

#endif

// requires Element<Elem>() (§19.3.3)
template<typename Elem>
class list<Elem>::iterator
{
	Link<Elem> *curr;	// current link
public:
	iterator(Link<Elem> *p)
		: curr{ p } { }

	iterator &operator++() { curr = curr->succ; return *this; }		// forward
	iterator &operator--() { curr = curr->prev; return *this; }		// backword
	Elem &operator*() { return curr->val; }

	bool operator==(const iterator &b) { return curr == b.curr; }
	bool operator!=(const iterator &b) { return curr != b.curr; }
};

template<typename Elem>
typename list<Elem>::iterator list<Elem>::insert(typename list<Elem>::iterator p, const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;
	if (new_node)
	{
		if (p.curr->prev == nullptr)
		{
			// insert at beginning of list
			p.curr->prev = new_node;
			new_node->succ = p.curr;
			first = new_node;

			// return iterator to front of list
			return begin();
		}
		else if (p.curr->succ == nullptr)
		{
			// insert at end of list
			p.curr->succ = new_node;
			new_node->prev = p.curr;
			last = new_node;

			// return iterator to end of list
			return end();
		}
		else if (p.curr->succ && p.curr->prev)
		{
			new_node->prev = p.curr;
			if (p.curr->succ)
			{
				p.curr->succ->prev = new_node;
			}
			new_node->succ = p.curr->succ;
			p.curr->succ = new_node;
			return iterator(p.curr);
		}
	}
	return p;
}

template<typename Elem>
typename list<Elem>::iterator list<Elem>::erase(typename list<Elem>::iterator p)
{
	Link<Elem> *trav = p.curr;
	if (trav)
	{
		if (trav->succ)
		{
			trav->succ->prev = trav->prev;
		}
		if (trav->prev)
		{
			trav->prev->succ = trav->succ;
		}
		return trav->succ;
	}
}

template<typename Elem>
typename list<Elem>::size_type list<Elem>::size()
{
	typename iterator iter = begin();
	typename size_type size = 0;
	while (iter != end())
	{
		iter++;
		size++;
	}
	return size;
}

template<typename Elem>
void list<Elem>::push_back(const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;

	Link<Elem> *trav = end();
	insert(trav, new_node->val);
}

template<typename Elem>
void list<Elem>::push_front(const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;

	typename iterator trav = begin();
	insert(trav, new_node->val);
}

template<typename Elem>
typename list<Elem>::iterator list<Elem>::end()
{
	return typename list<Elem>::iterator(last);
}

template<typename Elem>
typename list<Elem>::iterator list<Elem>::begin()
{
	return typename list<Elem>::iterator(first);
}

template<typename Elem>
void list<Elem>::pop_back()
{

}

template<typename Elem>
void list<Elem>::pop_front()
{

}


Lines 76, 79, 80, 86, 89, 90, 96, 98, 99, 101, 103, 104 and 105 all give the error message:
error C2248: 'list<int>::iterator::curr': cannot access private member declared in class 'list<int>::iterator'


So yeah, how do I get at the element pointed to by the passed in iterator in insert and erase? Is the actual algorithm and what I'm doing alright? And of course, please help me with the and constructor (if one is needed here) and destructor as well.
Last edited on
DragonOsman (715)
Updated code (I haven't been able to fix the errors yet; I just made some changes to fix a bit of extra typing I'd done):

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
 
#ifndef LIST_H_
#define LIST_H_

template<typename Elem>
class Link
{
public:
	Link *prev;
	Link *succ;
	Elem val;
};

template<typename Elem>
class list
	// representation and implementation details
{
public:
	using size_type = unsigned long;
	using value_type = Elem;
	class iterator;
	class const_iterator;

	//~list();

	iterator begin() { return iterator(first); }
	iterator end() { return iterator(last); }
	const_iterator begin() const { return iterator(first); }
	const_iterator end() const { return iterator(last);  }

	size_type size();

	iterator insert(iterator p, const Elem &v);		// insert v into list after p
	iterator erase(iterator p);						// remove p from list

	void push_back(const Elem &v);					// insert v at end
	void push_front(const Elem &v);					// insert v at front
	void pop_front();		// remove the first element
	void pop_back();		// remove the last element

	Elem &front() { return *first; }		// the first element
	Elem &back() { return *last; }			// the last element

private:
	Link<Elem> *first;
	Link<Elem> *last;
};

#endif

// requires Element<Elem>() (§19.3.3)
template<typename Elem>
class list<Elem>::iterator
{
	Link<Elem> *curr;	// current link
public:
	iterator(Link<Elem> *p)
		: curr{ p } { }

	iterator &operator++() { curr = curr->succ; return *this; }		// forward
	iterator &operator--() { curr = curr->prev; return *this; }		// backword
	Elem &operator*() { return curr->val; }

	bool operator==(const iterator &b) { return curr == b.curr; }
	bool operator!=(const iterator &b) { return curr != b.curr; }
};

template<typename Elem>
typename list<Elem>::iterator list<Elem>::insert(typename list<Elem>::iterator p, const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;
	if (new_node)
	{
		if (p.curr->prev == nullptr)
		{
			// insert at beginning of list
			p.curr->prev = new_node;
			new_node->succ = p.curr;
			first = new_node;

			// return iterator to front of list
			return begin();
		}
		else if (p.curr->succ == nullptr)
		{
			// insert at end of list
			p.curr->succ = new_node;
			new_node->prev = p.curr;
			last = new_node;

			// return iterator to end of list
			return end();
		}
		else if (p.curr->succ && p.curr->prev)
		{
			new_node->prev = p.curr;
			if (p.curr->succ)
			{
				p.curr->succ->prev = new_node;
			}
			new_node->succ = p.curr->succ;
			p.curr->succ = new_node;
			return iterator(p.curr);
		}
	}
	return p;
}

template<typename Elem>
typename list<Elem>::iterator list<Elem>::erase(typename list<Elem>::iterator p)
{
	Link<Elem> *trav = p.curr;
	if (trav)
	{
		if (trav->succ)
		{
			trav->succ->prev = trav->prev;
		}
		if (trav->prev)
		{
			trav->prev->succ = trav->succ;
		}
		return trav->succ;
	}
	return p;
}

template<typename Elem>
typename list<Elem>::size_type list<Elem>::size()
{
	typename iterator iter = begin();
	typename size_type size = 0;
	while (iter != end())
	{
		iter++;
		size++;
	}
	return size;
}

template<typename Elem>
void list<Elem>::push_back(const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;

	Link<Elem> *trav = end();
	insert(trav, new_node->val);
}

template<typename Elem>
void list<Elem>::push_front(const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;

	typename iterator trav = begin();
	insert(trav, new_node->val);
}

template<typename Elem>
void list<Elem>::pop_back()
{

}

template<typename Elem>
void list<Elem>::pop_front()
{

}

template<typename Iter>
void advance(Iter &p, int n)
{
	if (n > 0)
	{
		while (n > 0)
		{
			++p;
			--n;
		}
	}
	else if (n < 0)
	{
		while (n < 0)
		{
			--p;
			++n;
		}
	}
}


I'll also post this code in the original that that I asked about this in. I'd prefer it if we could continue this there. Link: http://www.cplusplus.com/forum/general/224862/
Repeater (3046)
So this wouldn't be good?


It works but it seems wasteful. You're re-calculating the size every time someone asks, even if nothing has changed.

Also, as the list grows longer, the time taken to calculate the size is going to increase with it.
DragonOsman (715)
I need to know a good way to define insert() and erase() as well, preferably a way that won't give me errors about accessing private members. And how is my current definition of insert() for when iterator::curr isn't private?

How should I check for whether a node was inserted or removed? Check whether the number of next or previous pointers in the Links decreased or increased?

If I use operator new to allocate memory for a node in insert(), shouldn't I call delete in erase()? So how should I definite erase() in that case (or is it better how it is now, but I should delete after erase() (and maybe return the "erased" node from erase()))? Also, I think I should add initialization, default and copy constructors for this as well. I think I'll make an "empty list" for the default, with first == last and begin() == end(). I don't know how to define a generic default for Elem, though. One that would work for a default constructor of any type (empty string for std::string, 0 for numeric types, etc.).

Possible (normal) constructor definition:
1
2
3
4
5
6
7
8
 
list(const Elem &v)
{
    Link<Elem> *new_node = new Link<Elem>;
    new_node->prev = nullptr;
    new_node->succ = last;
    new_node->val = val;
    first = new_node;
}


Possible default constructor definition:
1
2
3
4
5
6
 
list()
{
    first->succ = last;
    last->prev = first;
    first->val{};
}


I'd prefer an initializer list kind (i.e. 
1
2
3
4
5
 
list(const Elem &val)
    : first{initializer}, last{initializer} 
{
    // definition
}
), but I went with this way here because the initializer list one seemed complicated right now.
Last edited on
DragonOsman (715)
My current definitions for insert and erase:
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
 
template<typename Elem>
typename list<Elem>::iterator list<Elem>::insert(typename list<Elem>::iterator p, const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;
	if (new_node)
	{
		if (p.current_link()->prev == nullptr)
		{
			// insert at beginning of list
			p.current_link()->prev = new_node;
			new_node->succ = p.current_link();
			first = new_node;

			// return iterator to front of list
			return begin();
		}
		else if (p.current_link()->succ == nullptr)
		{
			// insert at end of list
			p.current_link()->succ = new_node;
			new_node->prev = p.current_link();
			last = new_node;

			// return iterator to end of list
			return end();
		}
		else if (p.current_link()->succ && p.current_link()->prev)
		{
			new_node->prev = p.current_link();
			if (p.curr->succ)
			{
				p.current_link()->succ->prev = new_node;
			}
			new_node->succ = p.current_link()->succ;
			p.current_link()->succ = new_node;
			return iterator(p.current_link());
		}
	}
	return p;
}

template<typename Elem>
typename list<Elem>::iterator list<Elem>::erase(typename list<Elem>::iterator p)
{
	if (p.current_link())
	{
		if (p.current_link()->succ && !p.current_link()->prev)
		{
			p++;
			Link<Elem> *temp = p.current_link()->prev;
			temp = nullptr;
			temp->succ = nullptr;
			delete p.current_link()->prev;
		}
		else if (!p.current_link()->succ && p.current_link()->prev)
		{
			p--;
			Link<Elem> *temp = p.current_link()->succ;
			p.current_link()->succ = nullptr;
			p.current_link()->succ->prev = nullptr;
			delete p.current_link()->succ;
		}
		else if (p.current_link()->succ && p.current_link()->prev)
		{
			p.current_link()->prev->succ = p.current_link()->succ;
			p.current_link()->succ->prev = p.current_link()->prev;
			p.current_link()->prev = nullptr;
			p.current_link()->succ = nullptr;
			delete p.current_link();
		}
	}
	return p;
}


If there's anything wrong I need to fix, please let me know and offer possible fixes as well.

Here're the constructor and destructor:
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
 
list(const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->prev = nullptr;
	new_node->succ = last;
	new_node->val = val;
	first = new_node;
}

list()
{
	first->succ = last;
	last->prev = first;
	first->val{};
}

~list()
{
	iterator iter = end();
	while (iter != begin())
	{
		delete iter.current_link();
		--iter;
	}
}


Last edited on
DragonOsman (715)
Okay, I almost have it all figured out except for insert() and the destructor and maybe erase() and the other node-removing functions. This is the Gist link for my latest update code: https://gist.github.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb . When I run the code in my debugger, I can see that insert() places the new node into the list. But the function high() still reports the node before it as the highest one (I input 100, 200, 300, 400, and 500, and then use insert() to insert 600 after position 5, but high still returns the iterator to position 5 as being the iterator to the highest value). What am I missing or what am I doing wrong?

By the way, in case anyone wonders why I'm decrementing iter twice in the destructor: With the first --iter, I'm trying to get to the previous node to delete the one after it. And with the second --iter, I move the loop itself along.
Topic archived. No new replies allowed.