Mylist review

frek (576)
I'm evolving a non-STL version of a list called Mylist as in the following 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
 
#include <iostream>

template<class Elem>
class Mylist {

public:
	class Iterator;

	Mylist<Elem>() {     // Default Constructor 
		sz = 0;
		first = nullptr;
		last = nullptr;
	}

	Mylist<Elem>(std::initializer_list<Elem> rhs) {     // Constructor with initializers
		sz = 0;
		first = nullptr;
		last = nullptr;

		for (const auto& r : rhs)
			push_back(r);
	}

	Mylist(const Mylist& rhs) {     // Copy constructor (deep copy)
		sz = 0;
		first = nullptr;
		last = nullptr;
		for (const auto& r : rhs)
			push_back(r);
	}

	Mylist& operator=(const Mylist& rhs) {    // Copy assignment operator

		if (*this != rhs)
		{
			if (size() < rhs.size()) {
				std::copy_n(rhs.begin(), size() - 1, this->begin());

					for (size_t i = size(); i < rhs.size(); ++i)
						push_back(rhs[i]);
			}

			else if (size() > rhs.size()) {
				auto rhs = rhs;  // costly?
				delete first;
				delete last;

				std::swap(rhs.sz, sz);
				std::swap(rhs.first, first);
				std::swap(rhs.last, last);
			}

			else std::copy(rhs.begin(), rhs.end(), this->begin());

			return *this;
		}
	}

	~Mylist<Elem>() {       // Destructor
		for (auto e = first; e != nullptr; ) {
			auto d = e;
			e = e->succ;
			delete d;
		}
	}

	size_t size() const { return sz; }

	Iterator begin() const { return Iterator(first); }  // iterator to the first element
	Iterator end() const {
		if (last) return Iterator(last->succ);
		else return last;
	}// iterator to one beyond the last element

	bool operator==(const Mylist<Elem> rhs) {
		return (first == rhs.first && last == rhs.last && sz == rhs.sz);
	}
	bool operator!=(const Mylist<Elem> rhs) {
		return !(this == &rhs);
	}

	Elem operator[](size_t t) {
		auto it = begin();
		for (size_t i = 0; i < size(); ++i, ++it)
			if (i == t) return *t;
	};

	const Elem operator[](size_t t) const {
		auto it = begin();
		for (size_t i = 0; i < size(); ++i, ++it)
			if (i == t) return *t;
	};

	void push_back(const Elem& v);  // insert v at end

private:
	size_t sz;
	class Link;

protected:
	Link* first;
	Link* last;
};

//*****************************************

template<class Elem>
class Mylist<Elem>::Link {

public:
	Link(Elem v, Link* p = nullptr, Link* s = nullptr) :
		val(v), prev(p), succ(s) { }

	Link* prev = nullptr;
	Link* succ = nullptr;
	Elem val;
};

//****************************************

template<class Elem>
class Mylist<Elem>::Iterator { 

private:
	Link* curr = nullptr;
	friend class Mylist<Elem>;

public:
	Iterator(Link* p) : curr(p) {  }

	Iterator& operator++() { curr = curr->succ; return *this; } // forward
	Iterator& operator--() { curr = curr->prev; return *this; } // backward

	Elem& operator*() { return curr->val; } // get value (dereference)

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

//****************************************************************************


template<class Elem>
void Mylist<Elem>::push_back(const Elem& v) // insert v at end
{
	last = (first == nullptr) ? (first = new Link(v)) : (last->succ = new Link(v, last));
	++sz;
}

//**************************************************

int main()
{
	Mylist<double> l1;   // Defalut ctor called
	l1.push_back(10);
	l1.push_back(12);
	l1.push_back(15);
	l1.push_back(20);

	std::cout << "l1: ";
	for (auto l : l1)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l2 = l1;   // copy ctor called
	std::cout << "l2: ";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l3 = { 2.2, 3.3, 4.4, 5.5 };   // ctor with initializers called
	std::cout << "l3: ";
	for (auto l : l3)
		std::cout << l << ' ';
	std::cout << '\n';

	l2 = l3; // copy assignment called

	std::cout << "l2 after assignment with l3: ";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n';

	system("pause");
	return 0;
}


1) First, I get this error for both lines 85 and 91 which I don't know why:
illegal indirection 85

2)Owing to the above errors I can't run the code to see if that works properly. But at this stage I don't find it well-written and especially the copy assignment operator looks very ugly!
Any suggestions?

Last edited on
AbstractionAnon (6954)
Line 82, 88: t is an unsigned integer.
Line 85, 91: You're trying to the indirection operator on an unsigned integer.

I assume you meant to return *it;
seeplus (6592)
t is of type size_t - which doesn't support indirection! Don't you mean return *it? Also, if the for loop terminates there is nothing returned - which is an error.

But don't you just want (not tried):

1
2
3
 
Elem operator[](size_t t) {
		return *(begin() + t);
}


As [] doesn't do bounds checking.
Last edited on
frek (576)
Thanks, that's right, and it was a typo. I shouldn't name the elements that similarly to course the typo and lead to the error. E.g., if it was this way, that's be better:

1
2
 
Elem operator[](size_t s) {
		auto it = begin();


I edited the project as below, and it works fine until on line 179 the copy assignment is called, and it goes to line 51 since the two lists (l1 and l3) have the same sizes:

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
 
#include <iostream>

template<class Elem>
class Mylist {

public:
	class Iterator;

	Mylist<Elem>() {     // Default Constructor 
		sz = 0;
		first = nullptr;
		last = nullptr;
	}

	Mylist<Elem>(std::initializer_list<Elem> rhs) {     // Constructor with initializers
		sz = 0;
		first = nullptr;
		last = nullptr;

		for (const auto& r : rhs)
			push_back(r);
	}

	Mylist(const Mylist& rhs) {     // Copy constructor (deep copy)
		sz = 0;
		first = nullptr;
		last = nullptr;
		for (const auto& r : rhs)
			push_back(r);
	}

	Mylist& operator=(const Mylist& rhs) {    // Copy assignment operator
		if (*this != rhs)
		{
			if (size() < rhs.size()) {
				std::copy_n(rhs.begin(), size() - 1, this->begin());

				for (size_t i = size(); i < rhs.size(); ++i)
					push_back(rhs[i]);
			}

			else if (size() > rhs.size()) {
				delete this;
				sz = rhs.size();
				Mylist<Elem> p;

				for (const auto& r : rhs)
					p.push_back(r);
			}

			else std::copy(rhs.begin(), rhs.end(), begin()); 
		}
			return *this;	
	}

	~Mylist<Elem>() {       // Destructor
		for (auto e = first; e != nullptr; ) {
			auto d = e;
			e = e->succ;
			delete d;
		}
	}

	size_t size() const { return sz; }

	Iterator begin() const { return Iterator(first); }  // iterator to the first element

	Iterator end() const {
		if (last) return Iterator(last->succ);
		else return last;
	}// iterator to one beyond the last element

	bool operator==(const Mylist<Elem> rhs) {
		return (first == rhs.first && last == rhs.last && sz == rhs.sz);
	}
	bool operator!=(const Mylist<Elem> rhs) {
		return !(this == &rhs);
	}

	Elem operator[](size_t t) {
		while (t > 0) {
			++begin();
			--t;
		}
		return *begin();
	}
	const Elem operator[](size_t t) const
	{
		while (t > 0) {
			++begin();
			--t;
		}
		return *begin();
	}

	void push_back(const Elem& v);  // insert v at end

private:
	size_t sz;
	class Link;

protected:
	Link* first;
	Link* last;
};

//*****************************************

template<class Elem>
class Mylist<Elem>::Link {

public:
	Link(Elem v, Link* p = nullptr, Link* s = nullptr) :
		val(v), prev(p), succ(s) { }

	Link* prev;
	Link* succ;
	Elem val;
};

//****************************************

template<class Elem>
class Mylist<Elem>::Iterator {

private:
	Link* curr = nullptr;
	friend class Mylist<Elem>;

public:
	Iterator(Link* p) : curr(p) {  }

	Iterator& operator++() { curr = curr->succ; return *this; } // forward
	Iterator& operator--() { curr = curr->prev; return *this; } // backward

	Elem& operator*() { return curr->val; } // get value (dereference)

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

//****************************************************************************


template<class Elem>
void Mylist<Elem>::push_back(const Elem& v) // insert v at end
{
	last = (first == nullptr) ? (first = new Link(v)) : (last->succ = new Link(v, last));
	++sz;
}

//**************************************************

int main()
{
	Mylist<double> l1;   // Defalut ctor called
	l1.push_back(10);
	l1.push_back(12);
	l1.push_back(15);
	l1.push_back(20);

	std::cout << "l1: ";
	for (auto l : l1)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l2 = l1;   // copy ctor called
	std::cout << "l2: ";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l3 = { 2.2, 3.3, 4.4, 5.5 };   // ctor with initializers called
	std::cout << "l3: ";
	for (auto l : l3)
		std::cout << l << ' ';
	std::cout << '\n';

	l2 = l3; // copy assignment called

	std::cout << "l2 after assignment with l3: ";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n'; 

	system("pause");
	return 0;
}


On that line we have: else std::copy(rhs.begin(), rhs.end(), begin()); and I get dozens of errors all pointing to lines outside of the project! For instance two of them are:

Severity Code Description Project File Line Suppression State
Error C2938 'std::_Iter_cat_t' : Failed to specialize alias template
Visual Studio\2019\Community\VC\Tools\MSVC\14.28.29333\include\xutility 1232

Severity Code Description Project File Line Suppression State
Error C2794 'iterator_category': is not a member of any direct or indirect base class of 'std::iterator_traits<_Iter>' Studio\2019\Community\VC\Tools\MSVC\14.28.29333\include\xutility 1205

Whatever I look at this std::copy's version that gets three iterators and based on the code I suppose it ought to work.
JLBorges (13770)
> Whatever I look at this std::copy's version that gets three iterators
> and based on the code I suppose it ought to work.

For an iterator to work with standard algorithms and the library, its properties must be accessible
through std::iterator_traits<> https://en.cppreference.com/w/cpp/iterator/iterator_traits

A simple way is to add the appropriate member typedefs to the iterator class

1
2
3
4
5
6
7
8
9
10
11
12
13
 
template<class Elem>
class Mylist<Elem>::Iterator {
    
// ...

public: 
    using iterator_category = std::forward_iterator_tag; 
    using value_type = Elem;
    using pointer = Elem*;
    using reference = Elem&;
    using difference_type = std::ptrdiff_t;

// ...


Ideally, the iterator should also provide an overload of of operator-> (return pointer)
ne555 (10692)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
	Mylist& operator=(const Mylist& rhs) {    // Copy assignment operator
		if (*this != rhs)
		{
			if (size() < rhs.size()) {
				std::copy_n(rhs.begin(), size() - 1, this->begin()); //¿why -1? suppose list is empty

				for (size_t i = size(); i < rhs.size(); ++i)
					push_back(rhs[i]); //operator[] is quite costly, you are making this O(n^2)
			}

			else if (size() > rhs.size()) {
				delete this; //don't kill yourself
				sz = rhs.size(); //can't access sz, you are dead, ¿remember?
				Mylist<Elem> p;

				for (const auto& r : rhs)
					p.push_back(r);
				// so the things are now in `p' instead of `rhs', ¿what now?
			}

			else std::copy(rhs.begin(), rhs.end(), begin()); 
		}
			return *this;	//learn to indent
	}


too many special cases, you'll always copy min(this->size(), rhs.size()) and then manage the loose ends.
frek (576)
Yes, these are right, but I can remedy them one by one. First, the case where both lists have the same size:

1
2
3
4
5
6
7
 
else //std::copy(rhs.begin(), rhs.end(), begin());
			{
				while (begin() != end()) {
					*begin() = *rhs.begin();
					++begin(); ++rhs.begin();
				}
			}

The incrementations don't work and this falls into an infinite loop!
The incrementation works because we can print the list elements, using the ranged-for in main(), just like the way they are added by push_back, so there really is a list with this program, but I don't know why and couldn't make benefits from the debugger to know and work out why that infinite loop reveals.
Last edited on
frek (576)
Fixed many of the issues:

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
 
#include <iostream>

template<class Elem>
class Mylist {

public:
	class Iterator;

	Mylist<Elem>() {     // Default Constructor 
		sz = 0;
		first = nullptr;
		last = nullptr;
	}

	Mylist<Elem>(std::initializer_list<Elem> rhs) {     // Constructor with initializers
		sz = 0;
		first = nullptr;
		last = nullptr;

		for (const auto& r : rhs)
			push_back(r);
	}

	Mylist(const Mylist& rhs) {     // Copy constructor (deep copy)
		sz = 0;
		first = nullptr;
		last = nullptr;
		for (const auto& r : rhs)
			push_back(r);
	}

	Mylist& operator=(const Mylist& rhs) {    // Copy assignment operator
		if (*this != rhs)
		{
			if (size() < rhs.size()) {

				auto r = rhs.begin();
				for (auto& t : *this) {
					t = *r;
					++r;
				}
				for (auto t = r; t != rhs.end(); ++t)
					push_back(*r);
			}

			else if (size() > rhs.size()) {

				auto& t = begin();
				for (auto r : rhs) {
					*t = r;
					++t;
				}
				t = nullptr;
			}

			else {
				auto t = begin();
				for (auto& r : rhs) {
					*t = r;
					++t;
				}
			}
			return *this;
		}
	}

	~Mylist<Elem>() {       // Destructor
		for (auto e = first; e != nullptr; ) {
			auto d = e;
			e = e->succ;
			delete d;
		}
	}

	size_t size() const { return sz; }

	Iterator begin() const { return Iterator(first); }  // iterator to the first element

	Iterator end() const {
		if (last) return Iterator(last->succ);
		else return last;
	}// iterator to one beyond the last element

	bool operator==(const Mylist<Elem> rhs) {
		return (first == rhs.first && last == rhs.last && sz == rhs.sz);
	}
	bool operator!=(const Mylist<Elem> rhs) {
		return !(this == &rhs);
	}

	Elem operator[](size_t t) {
		while (t > 0) {
			++begin();
			--t;
		}
		return *begin();
	}
	const Elem operator[](size_t t) const
	{
		while (t > 0) {
			++begin();
			--t;
		}
		return *begin();
	}

	void push_back(const Elem& v);  // insert v at end

private:
	size_t sz;
	class Link;

protected:
	Link* first;
	Link* last;
};

//*****************************************

template<class Elem>
class Mylist<Elem>::Link {

public:
	Link(Elem v, Link* p = nullptr, Link* s = nullptr) :
		val(v), prev(p), succ(s) { }

	Link* prev;
	Link* succ;
	Elem val;
};

//****************************************

template<class Elem>
class Mylist<Elem>::Iterator {

private:
	Link* curr = nullptr;
	friend class Mylist<Elem>;

public:
	Iterator(Link* p) : curr(p) {  }

	Iterator& operator++() { curr = curr->succ; return *this; } // forward
	Iterator& operator--() { curr = curr->prev; return *this; } // backward
	Iterator& operator&()  { return *this; }

	Elem& operator*() { return curr->val; } // get value (dereference)

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

//****************************************************************************


template<class Elem>
void Mylist<Elem>::push_back(const Elem& v) // insert v at end
{
	last = (first == nullptr) ? (first = new Link(v)) : (last->succ = new Link(v, last));
	++sz;
}

//**************************************************

int main()
{
	Mylist<double> l1;   // Defalut ctor called
	l1.push_back(10);
	l1.push_back(12);
	l1.push_back(15);
	l1.push_back(20);

	std::cout << "l1: ";
	for (auto l : l1)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l2 = l1;   // copy ctor called
	l2.push_back(25);
	std::cout << "l2: ";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l3 = { 2.2, 3.3, 4.4, 5.5 };   // ctor with initializers called
	std::cout << "l3: ";
	for (auto l : l3)
		std::cout << l << ' ';
	std::cout << '\n';

	l2 = l3; // copy assignment called

	std::cout << "l2 after assignment with l3\n";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n'; 

	system("pause");
	return 0;
}


Tested all three modes in the assignment operator with various lists in main(). Fine up to here, agree, yeah? Just a couple of questions

1) I want to have a reference iterator for line 48 to be able to delete the extra elements in the right-hand side list and for that defined and implemented (!) that on line 148, but I get this error:

Error C2440 'initializing': cannot convert from 'Mylist<double>::Iterator' to 'Mylist<double>::Iterator &' 48

2) The prior version below didn't work albeit both the dereference and increment operators were called and worked, because even after increment, begin() points to the fist element when it's used! Do you have a better reason, please?

1
2
3
4
5
6
7
 
else //std::copy(rhs.begin(), rhs.end(), begin());
			{
				while (begin() != end()) {
					*begin() = *rhs.begin();
					++begin(); ++rhs.begin();
				}
			}
Last edited on
ne555 (10692)
> because even after increment, begin() points to the fist element when it's used!
of course, that's what is supposed to do.
begin() gives you an iterator to the first element of the list, it doesn't care what you do with such iterator
the start of the list didn't change, so begin() keep giving you the same result.

while (begin() != end())
think of it like this: if begin() is equal to end(), then the list is empty
Last edited on
dhayden (5798)
To my thinking, operator=() should just clear the list and copy the rhs to it. All those special cases are confusing an error prone, For example if size() > rhs.size(), you never adjust the size and I'm not sure how line 53 compiles.

operator==() just compares pointers, which will never be equal. You need to compare the lists element by element. Be sure to compare the size first since if the sizes don't match, you know they aren't equal.

The [] operators should return references, not copies. Also, shouldn't Elem operator[](size_t t) be implemented in terms of const Elem operator[](size_t t) cons?
frek (576)
To my thinking, operator=() should just clear the list and copy the rhs to it.
You meant something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Mylist& operator=(const Mylist& rhs) {    // Copy assignment operator
		if (*this != rhs)
		{
			for (auto e = first; e != nullptr; ) {
				auto d = e;
				e = e->succ;
				delete d;
			}

			for (auto r : rhs)
				push_back(r);
			return *this;
		}
	}

But for this I get the error: Access violation reading location 0xDDDDDDE5. for line 195!

operator==() just compares pointers, which will never be equal. You need to compare the lists element by element. Be sure to compare the size first since if the sizes don't match, you know they aren't equal.
Sue I will fix that too, but after the assignment operator. But why "which never be equal"? It's possible I think.

The [] operators should return references, not copies. Also, shouldn't Elem operator[](size_t t) be implemented in terms of const Elem operator[](size_t t) cons?
One of the operators is implemented this way:

1
2
3
4
5
6
7
 
const Elem& operator[](size_t t) const {
		while (t > 0) {
			++begin();
			--t;
		}
		return *begin();
	}
Last edited on
seeplus (6592)
Consider {not fully tested!):

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
 
#include <iostream>

template<class Elem>
class Mylist {

public:
	class Iterator;

	Mylist<Elem>() {}	// Default constructor

	Mylist<Elem>(const std::initializer_list<Elem>& rhs) {     // Constructor with initializers
		for (const auto& r : rhs)
			push_back(r);
	}

	Mylist(const Mylist& rhs) {     // Copy constructor (deep copy)
		for (const auto& r : rhs)
			push_back(r);
	}

	Mylist& operator=(const Mylist& rhs) {    // Copy assignment operator
		if (*this == rhs)
			return *this;

		auto it {begin()};
		auto rit {rhs.begin()};

		if (size() < rhs.size()) {
			size_t l = 0;

			for (; l < size(); ++l, ++it, ++rit)
				*it = *rit;

			for (; l < rhs.size(); ++l, ++rit)
				push_back(*rit);

			return *this;
		}

		auto itl {it};

		for (size_t l = 0; l < rhs.size(); ++l, ++it, ++rit) {
			*it = *rit;
			itl = it;
		}

                // should be last = (--it).curr;   but -- is not yet implemented as prev isn't yet used
		last = itl.curr;
		sz = rhs.size();

		for (auto p = last->succ; p != nullptr;) {
			const auto d {p};

			p = p->succ;
			delete d;
		}

		last->succ = nullptr;
	}

	~Mylist<Elem>() {       // Destructor
		for (auto e = first; e != nullptr; ) {
			const auto d {e};

			e = e->succ;
			delete d;
		}
	}

	size_t size() const { return sz; }

	Iterator begin() const { return Iterator(first); }  // iterator to the first element

	Iterator end() const {	// iterator to one beyond the last element
		return last ? Iterator(last->succ) : last;
	}

	bool operator==(const Mylist<Elem>& rhs) const {
		return (first == rhs.first && last == rhs.last && sz == rhs.sz);
	}
	bool operator!=(const Mylist<Elem>& rhs) const {
		return !(this == &rhs);
	}

	Elem& operator[](size_t t) {
		auto it {begin()};

		for (; t > 0; ++it, --t);

		return *it;
	}

	const Elem& operator[](size_t t) const
	{
		auto it {begin()};

		for (; t > 0; ++it, --t);

		return *it;
	}

	void push_back(const Elem& v);  // insert v at end

private:
	size_t sz {};
	struct Link;

protected:
	Link *first {};
	Link *last {};
};

//*****************************************

template<class Elem>
struct Mylist<Elem>::Link {
	Link(Elem v, Link *p = nullptr, Link *s = nullptr) :
		val(v), prev(p), succ(s) { }

	Link *prev {};
	Link *succ {};
	Elem val {};
};

//****************************************

template<class Elem>
class Mylist<Elem>::Iterator {

private:
	Link *curr {};
	friend class Mylist<Elem>;

public:
	Iterator(Link *p) : curr(p) {}

	Iterator& operator++() { curr = curr->succ; return *this; } // forward
	Iterator& operator--() { curr = curr->prev; return *this; } // backward
	Iterator& operator&() { return *this; }

	Elem& operator*() const { return curr->val; } // get value (dereference)
	Link* operator->() const { return curr; }

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

//****************************************************************************


template<class Elem>
void Mylist<Elem>::push_back(const Elem& v) // insert v at end
{
	last = (first == nullptr) ? (first = new Link(v)) : (last->succ = new Link(v, last));
	++sz;
}

//**************************************************

int main()
{
	Mylist<double> l1;   // Defalut ctor called
	l1.push_back(10);
	l1.push_back(12);
	l1.push_back(15);
	l1.push_back(20);

	std::cout << "l1: ";
	for (auto l : l1)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l2 = l1;   // copy ctor called
	l2.push_back(25);
	std::cout << "l2: ";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l3 = {2.2, 3.3, 4.4, 5.5};   // ctor with initializers called
	std::cout << "l3: ";
	for (auto l : l3)
		std::cout << l << ' ';
	std::cout << '\n';

	l2 = l3; // copy assignment called

	std::cout << "l2 after assignment with l3\n";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n';

	//system("pause");
	return 0;
}



l1: 10 12 15 20
l2: 10 12 15 20 25
l3: 2.2 3.3 4.4 5.5
l2 after assignment with l3
2.2 3.3 4.4 5.5

Last edited on
seeplus (6592)
As an additional thought, there is a list design idiom whereby, like a vector, you have a capacity and a used size. Hence if you copy from a smaller list to one that already contains more elements, none of the unused nodes are removed - end() points to the last used node and size is set to reflect the number of used nodes but capacity is set to the total number of nodes. When new node(s) are added, first the existing un-used nodes are used before new nodes are acquired if needed.

This means that unless for the destructor, having a succ link as nullptr doesn't indicate the end of the used data - but the end of the allocated links. But as end() is obne past the end of the used nodes, using iterators normally will work OK.
frek (576)
Thanks.

1) Why have you removed the following initializations in the constructors, please? Is it not a rule of thumb to initialize uninitialized data before we step forward to use them?
1
2
3
 
sz = 0;
first = nullptr;
last = nullptr;


2) The most important point for solving the issue is last = itl.curr; which will be possible through the friend class. I used last = (--it).curr; and it works!

3) I also changed the subscript operators and defined move functions the following way. OK to you too?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
Elem& operator[](size_t n) {
		if (n <= 0 || n >= size())
			throw std::out_of_range("out of range error! ");

		auto it{ begin() };
		while (n > 0) {
			++it;
			--n;
		}
		return *it;
	}
	const Elem& operator[](size_t n) const {
		if (n <= 0 || n >= size())
			throw std::out_of_range("out of range error");

		auto it{ begin() };
		while (n > 0) {
			++it;
			--n;
		}
		return *it;
	}


1
2
3
 
Mylist(Mylist&& rhs) { return std::move(rhs); }  // move constructor

Mylist& operator=(Mylist&& rhs) { return std::move(rhs); }  // move assignment operator


main() works fine with the tests:

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
 
int main() try
{
	Mylist<double> l1;   // Defalut ctor called
	l1.push_back(10);
	l1.push_back(12);
	l1.push_back(15);
	l1.push_back(20);
	l1[2] = 29;

	std::cout << "l1: ";
	for (auto l : l1)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l2 = l1;   // copy ctor called
	l2.push_back(25);
	std::cout << "l2: ";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l3 = { 2.2, 3.3, 4.4, 5.5 };   // ctor with initializers called
	std::cout << "l3: ";
	for (auto l : l3)
		std::cout << l << ' ';
	std::cout << '\n';

	l2 = l3; // copy assignment called

	std::cout << "l2 after assignment with l3\n";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n'; 

	auto l4{ Mylist<double> { 1,2,3,4,5,6,7} }; // move ctor 
	std::cout << "l4: ";
	for (auto l : l4)
		std::cout << l << ' ';
	std::cout << '\n';

	system("pause");
	return 0;
}
catch (std::out_of_range& e) {
	std::cerr << e.what() << '\n';
	abort();
}


4) I've also implemented member functions Iterator erase(Iterator p); and Iterator insert(Iterator p, const Elem& v); this way:

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
 
template<class Elem>  // insert v into the list after p
Mylist<Elem>::Iterator Mylist<Elem>::insert(Iterator p, const Elem& v) {
	if (!p)
		throw std::out_of_range("Out of range, no insertion occurred!");

	if (p.curr == last) {
		push_back(v);
		return p;
	}

	else
		for (auto& l : this)
			if (l == p) {
				auto m{ new Link<Elem>(l.curr, l.curr->succ, v) };

				l.curr->succ->prev{ m };
				l.curr->succ{ m };
				++sz;
				return p;
			}
}

//*******************************************************

template<class Elem>  // remove p from the list
Mylist<Elem>::Iterator Mylist<Elem>::erase(Mylist<Elem>::Iterator p)
{
	if (!p)
		throw std::out_of_range("Out of range, no insertion occurred!");

	if (p.curr == fisrt) {
		pop_front();
		return Iterator(first);
	}

	if (p.curr == last) {
		pop_back();
		return Iterator(last);
	}

	for (auto& l : this)
		if (l == p) {
			auto r{ p };
			l.curr->prev->succ{ l.curr->succ };
			l.curr->succ->prev{ l.curr->prev };
			--sz;
			delete l;
			return --r;
		}
}


But the project won't run and I get ta couple of errors. For instance:
syntax error: missing ';' before '{' 2
syntax error: identifier 'Iterator' 2

Last edited on
seeplus (6592)
1) default initialised in the class when defined - so no need to initialise again in the constructor.

3) IMO I wouldn't have [] with a list due to performance issues. std:list doesn't implement either

frek (576)
I still don't know the reason for the question/problem #4 above. :(
frek (576)
Here's probably the last version of Mylist with an embedded function high. Do you find any improper statement/part based on the modern cpp in it? If so, please tell me to fix (and learn) it. 

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
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
 
#include <iostream>

template<class Elem>
class Mylist {

public:
	class Iterator;

	Mylist<Elem>() { }     // Default Constructor 
		

	Mylist<Elem>(const std::initializer_list<Elem>& rhs) {     // Constructor with initializers
		for (const auto& r : rhs)
			push_back(r);
	}

	Mylist(const Mylist& rhs) {     // Copy constructor (deep copy)
		for (const auto& r : rhs)
			push_back(r);
	}

	Mylist& operator=(const Mylist& rhs) {    // Copy assignment operator
		if (*this != rhs) {

			if (size() < rhs.size()) {

				auto r = rhs.begin();
				for (auto& it : *this) {
					it = *r;
					++r;
				}
				for (auto t = r; t != rhs.end(); ++t)
					push_back(*r);
			}

			else if (size() > rhs.size()) {

				auto it = begin();
				for (auto r : rhs) {   // replace the data
					*it = r;
					++it;
				}
				last = (--it).curr;
				sz = rhs.size();

				for (auto e = last->succ; e != nullptr;) {  // delete the extra elements
					auto d{ e };
					e = e->succ;
					delete d;
				}
				last->succ = nullptr;
			}

			else {
				auto it = begin();
				for (auto& r : rhs) {
					*it = r;
					++it;
				}
			}
		}
		return *this;
	}

	Mylist(Mylist&& rhs) { return std::move(rhs); }  // move constructor

	Mylist& operator=(Mylist&& rhs) { return std::move(rhs); }  // move assignment operator

	~Mylist<Elem>() {       // Destructor
		for (auto e = first; e != nullptr; ) {
			auto d = e;
			e = e->succ;
			delete d;
		}
	}

	size_t size() const { return sz; }

	Iterator begin() const { return Iterator(first); }  // iterator to the first element

	Iterator end() const {         // iterator to one beyond the last element
		if (last) return Iterator(last->succ);
		else return last;
	}

	Iterator insert(Iterator, const Elem&);

	Iterator erase(Iterator);  // remove p from the list

	bool operator==(const Mylist<Elem> rhs) {
		return (first == rhs.first && last == rhs.last && sz == rhs.sz);
	}
	bool operator!=(const Mylist<Elem> rhs) {
		return !(this == &rhs);
	}

	Elem& operator[](size_t n) {
		if (n <= 0 || n >= size())
			throw std::out_of_range("out of range error! ");

		auto it{ begin() };
		while (n > 0) {
			++it;
			--n;
		}
		return *it;
	}
	const Elem& operator[](size_t n) const {
		if (n <= 0 || n >= size())
			throw std::out_of_range("out of range error");

		auto it{ begin() };
		while (n > 0) {
			++it;
			--n;
		}
		return *it;
	}

	void push_back(const Elem& v);  // insert v at end
	void push_front(const Elem& v); // insert v at front
	void pop_back();  // remove the last element
	void pop_front();  // remove the first element
	
private:
	size_t sz{};
	class Link;

protected:
	Link* first{};
	Link* last{};
};

//*****************************************

template<class Elem>
class Mylist<Elem>::Link {

public:
	Link(Elem v, Link* p = nullptr, Link* s = nullptr) :
		val(v), prev(p), succ(s) { }

	Link* prev;
	Link* succ;
	Elem val;
};

//****************************************

template<class Elem>
class Mylist<Elem>::Iterator {

private:
	Link* curr = nullptr;
	friend class Mylist<Elem>;  // Inside the friend class (Mylist), it'll be possible for the instances
	                            // of the class Iterator to access private/protected data

public:
	Iterator(Link* p) : curr(p) {  }

	Iterator& operator++() { curr = curr->succ; return *this; } // forward
	Iterator& operator--() { curr = curr->prev; return *this; } // backward

	Elem& operator*() { return curr->val; } // get value (dereference)

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

//****************************************************************************

template<class Elem>  // add v after p in the list
typename Mylist<Elem>::Iterator Mylist<Elem>::insert(Iterator p, const Elem& v) {
	if (p == nullptr)
		throw std::out_of_range("Out of range, no insertion occurred!");
	if (p == first) {
		push_front(v);
		return p;
	}

	if (p.curr == last) {
		push_back(v);
		return p;
	}
 
	p.curr->succ->prev = new Link(v, p.curr, p.curr->succ);
	p.curr->succ = p.curr->succ->prev;

	++sz;
	return p;
}

//******************************************************************************

template<class Elem>  // remove p from the list
typename Mylist<Elem>::Iterator Mylist<Elem>::erase(Iterator p)
{
	if (p == nullptr)
		throw std::out_of_range("Out of range, no insertion occurred!");

	if (p.curr == first) {
		pop_front();
		return Iterator(first);
	}

	if (p.curr == last) {
		pop_back();
		return Iterator(last);
	}

	p.curr->prev->succ = p.curr->succ;
	p.curr->succ->prev = p.curr->prev;

	delete p.curr;
	--sz;
	return 0;
}

//**************************************************************

template<class Elem>
void Mylist<Elem>::push_back(const Elem& v) // insert v at end
{
	last = (first == nullptr) ? (first = new Link(v)) : (last->succ = new Link(v, last));
	++sz;
}

//******************************************************

template<class Elem>
void Mylist<Elem>::push_front(const Elem& v)
{
	first = (first == nullptr) ? (first = new Link(v)) : (first->prev = new Link(v, nullptr, first));
	++sz;
}

//****************************************

template<class Elem>  // remove the last element
void Mylist<Elem>::pop_back()
{
	if (size() == 0)
		throw std::out_of_range("pop_back from empty list!");
	if (first == last)
		delete first;

	else {
		last = last->prev;
		delete last->succ;
		//last->succ = nullptr;
	}
}

//******************************************
template<class Elem>    // remove the first element
void Mylist<Elem>::pop_front()
{
	if (size() == 0)
		throw std::out_of_range("pop_first from empty list!");
	if (first == last)
		delete first;

	else {
		first = first->succ;
		delete first->prev;
		first->prev = nullptr;
	}
}

//**************************************************

template<class 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 (*p > *high) high = p;
	return high;
}

//******************************************************

int main() try
{
	Mylist<double> l1;   // Defalut ctor called
	l1.push_back(10);
	l1.push_back(12);
	l1.push_back(15);
	l1.push_back(20);
	l1[2] = 29;

	std::cout << "l1: ";
	for (auto l : l1)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l2 = l1;   // copy ctor called
	l2.push_back(25);
	std::cout << "l2: ";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n';

	Mylist<double> l3 = { 2.2, 3.3, 4.4, 5.5 };   // ctor with initializers called
	std::cout << "l3: ";
	for (auto l : l3)
		std::cout << l << ' ';
	std::cout << '\n';

	l2 = l3; // copy assignment called

	std::cout << "l2 after assignment with l3\nl2: ";
	for (auto l : l2)
		std::cout << l << ' ';
	std::cout << '\n'; 

	auto l4{ Mylist<double> { 1,2,3,4,5,6,7} }; // move ctor 
	std::cout << "l4: ";
	for (auto l : l4)
		std::cout << l << ' ';
	std::cout << '\n';

	l4.pop_front();
	l4.push_front(11);

	auto p{ l4.begin() };
	++p;
	l4.erase(p);

	p = l4.begin();
	++p;
	l4.insert(p, 33);

	l4.pop_back();
	l4.push_back(77);

	std::cout << "l4 after change: ";
	for (auto l : l4)
		std::cout << l << ' ';
	std::cout << '\n';

	auto it = high(l1.begin(), l1.end());
	std::cout << "\nThe highest value of l1 is: " << *it << '\n';

	it = high(l2.begin(), l2.end());
	std::cout << "The highest value of l2 is: " << *it << '\n';

	it = high(l3.begin(), l3.end());
	std::cout << "The highest value of l3 is: " << *it << "\n";

	it = high(l4.begin(), l4.end());
	std::cout << "The highest value of l4 is: " << *it << "\n\n";

	system("pause");
	return 0;
}
catch (std::out_of_range& e) {
	std::cerr << e.what() << '\n';
	abort();
}

Topic archived. No new replies allowed.