Perfecting my linked list

Pages: 12345
cire (1845)
And, like you said, can't just be ignored


Perhaps that deserves some clarification. When I said
The benefit of exceptions in this case is that you can't ignore them by just disregarding them
what I meant was that if you disregard the exception, the program terminates. You cannot continue on with a corrupt program state or data which you can do with the other error reporting methods (or lack thereof) proposed here.

And, as Coder777 indicates, terminating the program is usually the correct thing to do when such a logic error occurs, so ignoring the exception isn't unreasonable.
Volatile Pulse (1329)
So...it's better to just forget about the exceptions and let myself or someone else who writes code containing my list figure it out on their own? I'm not trying to be ignorant with this response, I'm just trying to find out what the proper course would be to take. If I don't have to use exceptions, then, simply, I just won't. But if it is suggested that I use exceptions, then I will. I've tried avoiding exceptions for majority of the years I've been programming mainly because I never needed them and learned that they shouldn't be relied upon.

To clarify these last few posts in a more simpler question:
1) Do I need exceptions?
2) Do you recommend using them in this situation?
3) What benefits do I have over just ignoring returning something that doesn't exist?

Thanks guys and/or ladies.
Volatile Pulse (1329)
Alright, I went back to make my code a little neater and more manageable by separating the declarations and definitions and ran into some issues:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
namespace vp {
   template<class T>
   class list {
      // ...
      public:
         class iterator {
            private:
               node *current;
            public:
               iterator();
               iterator(node *n);
               iterator operator =(iterator n);
               // ... 


1
2
3
4
5
 
template <class T>
vp::list<T>::iterator vp::list<T>::iterator::operator =(vp::list<T>::iterator n) {
   this->current = n->current;
   return *this;
}


But I get these errors:
C:\Programming\List Practice\main.cpp|73|error: need 'typename' before 'vp::list<T>::iterator' because 'vp::list<T>' is a dependent scope|


I'm assuming it has to do with this part:
vp::list<T>::iterator

To me, that looks like the correct 'typename' but I'm unsure as to what it's complaining about. Can I not break apart the definitions like this?
cire (1845)
1) Do I need exceptions?

No, you don't need them.

2) Do you recommend using them in this situation?

Yes.

3) What benefits do I have over just ignoring returning something that doesn't exist?


That's been covered.

I'm assuming it has to do with this part:
vp::list<T>::iterator

Correct. In fact, the error message tells you how to correct it - put 'typename' before 'vp::list<T>::iterator'

Note that 'typename' is a keyword like 'new' and 'template'.
Volatile Pulse (1329)
That seemed really easy. -.-

But let me finish tidying this up then I'll work on the exceptions. I have a few hours yet tonight to work on this so hopefully I'll get it to where I'm happy but my mom's dog is making it hard by laying on my laptop keyboard.
Volatile Pulse (1329)
Alright, I got a good portion of my list working now and I started reading up on exceptions, still fail to see the benefit over just using if statements, but whatever. Here's what I got so far:
1
2
3
4
5
6
7
8
9
10
11
 
template<class T>
T& vp::list<T>::front() {
   try {
      if (empty())
         throw size();
      return firstNode->value;
   }
   catch (unsigned int e) {
      std::cout << "Can't return a value. Size is " << e << ".";
   }
}


The program still crashes after displaying the message, I'm assuming because I fail to return anything from the function, but I have two issues, which are the same as before. What do I "return" and I don't need to display a message to the screen, but I have no clue what should be thrown/caught. Any advice?

Edit: Here is another approach I took as well so that it still returns something, but it returns a local variable which will cause problems:
1
2
3
4
5
6
7
8
9
10
11
 
template<class T>
T& vp::list<T>::front() {
   try {
      if (empty())
         throw T();
      return firstNode->value;
   }
   catch (T e) {
      return e;
   }
}
Last edited on
cire (1845)
Your job isn't to handle the exception. Your job is to generate it.

1
2
3
4
5
6
7
8
 
#include <stdexcept>

template<class T>
T& vp::list<T>::front() {
      if (empty())
         throw std::logic_error( "list:  Invoked front() on empty list") ;
      return firstNode->value;
}
Volatile Pulse (1329)
That...is...so...AWESOME!

I never knew something like that existed. Is it only g++ that handles uncaught exceptions like this or is it standard amongst compilers? That's where I was getting confused. I thought that I had to personally handle the exceptions with "catch". Now, I assume there is a generic way to "catch" these exceptions so that you can prevent the program from crashing as well. Meaning, if someone doesn't want to error test, they could possibly call a logic_catch() function or something and handle it how they see fit instead of just letting the program crash?

I'm just trying to learn some things. I'll have to delve further into stdexcept as well, I presume.
Volatile Pulse (1329)
So, I've been working on adding more things to my list and decided on adding in some more ctors, mainly copy ctor and a sized ctor, and now things are broke. I'm getting SEGFAULTS at the end() function. Here is all of the code so far:
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
 
#include <iostream>
#include <stdexcept>

namespace vp {
   template<class T>
   class list {
      private:
         struct node {
            node();
            node(T Value, node *pnode);
            node(T Value, node *Prev, node *Next);
            T value;
            node *prev;
            node *next;
         };
         node *firstNode;
         node *lastNode;
         unsigned int mSize;
      public:
         class iterator {
            private:
               node *current;
            public:
               iterator();
               iterator(node *n);
               iterator operator =(iterator n);
               iterator& operator ++();
               iterator operator ++(int);
               node* operator ->();
               node* operator *();
               bool operator !=(iterator n);
         };
         list();
         list(unsigned n, const T& value = T());
         list(list<T>& x);
         ~list();
         //void assign
         T& back();
         iterator begin();
         void clear();
         bool empty();
         iterator end();
         //iterator erase
         T& front();
         void pop_back();
         void pop_front();
         void push_back(T x);
         void push_front(T x);
         unsigned int size();
   };
}


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
 
/** Node definitions **/
template<class T>
vp::list<T>::node::node() : value(T()), prev(NULL), next(NULL) {}

template<class T>
vp::list<T>::node::node(T Value, node *pnode) :
   value(Value), prev(pnode->prev), next(pnode) {
   pnode->prev = this;

   if (prev)
      prev->next = this;
}

template<class T>
vp::list<T>::node::node(T Value, node *Prev, node *Next) :
   value(Value), prev(Prev), next(Next) {
   if (prev)
      prev->next = this;

   if (next)
      next->prev = this;
}

/** Iterator definitions **/
template<class T>
vp::list<T>::iterator::iterator() :
   current(NULL) {}

template<class T>
vp::list<T>::iterator::iterator(node *n) :
   current(n) {}

template<class T>
typename vp::list<T>::iterator vp::list<T>::iterator::operator =(iterator n) {
   this->current = n->current;
   return *this;
}

template<class T>
typename vp::list<T>::iterator& vp::list<T>::iterator::operator ++() {
   if (current)
      current = current->next;

   return *this;
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::iterator::operator ++(int) {
    iterator result = *this;
    if (current)
        current = current->next;
        
    return result;
}

template<class T>
typename vp::list<T>::node* vp::list<T>::iterator::operator ->() {
   return current;
}

template<class T>
typename vp::list<T>::node* vp::list<T>::iterator::operator *() {
   return current;
}

template<class T>
bool vp::list<T>::iterator::operator !=(iterator n) {
   return current != n.current;
}

/** List definitions **/
template<class T>
vp::list<T>::list() :
   firstNode(NULL), lastNode(NULL), mSize(0) {}

template<class T>
vp::list<T>::list(unsigned n, const T& value) :
   firstNode(NULL), lastNode(NULL), mSize(0) {
      for (unsigned i = 0; i < n; i ++)
         push_back(value);
}

template<class T>
vp::list<T>::list(list<T>& x) :
   firstNode(NULL), lastNode(NULL), mSize(0) {
      for (auto it : x)
         push_back(it->value);
}

template<class T>
vp::list<T>::~list() {
   while (firstNode != NULL) {
      node *n = firstNode->next;
      delete firstNode;
      firstNode = n;
   }
}

template<class T>
T& vp::list<T>::back() {
   if (empty())
      throw std::logic_error("list: Invoked back() on empty list") ;
   return lastNode->value;
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::begin() {
   return iterator(firstNode);
}

template<class T>
void vp::list<T>::clear() {
   while (firstNode != NULL) {
      node *n = firstNode->next;
      delete firstNode;
      firstNode = n;
   }

   mSize = 0;
}

template<class T>
bool vp::list<T>::empty() {
   return !size();
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::end() {
   return iterator(lastNode->next);
}

template<class T>
T& vp::list<T>::front() {
   if (empty())
      throw std::logic_error("list: Invoked front() on empty list") ;
   return firstNode->value;
}

template<class T>
void vp::list<T>::pop_back() {
   if (empty())
      return;

   node *n = lastNode->prev;
   n->next = NULL;
   delete lastNode;
   lastNode = n;
   mSize --;

   if (empty())
      firstNode = lastNode;
}

template<class T>
void vp::list<T>::pop_front() {
   if (empty())
      return;

   node *n = firstNode->next;
   n->prev = NULL;
   delete firstNode;
   firstNode = n;
   mSize --;

   if (empty())
      lastNode = firstNode;
}

template<class T>
void vp::list<T>::push_back(T x) {
   lastNode = new node(x, lastNode, NULL);

   if (firstNode == NULL)
      firstNode = lastNode;

   mSize ++;
}

template<class T>
void vp::list<T>::push_front(T x) {
   firstNode = new node(x, NULL, firstNode);

   if (lastNode == NULL)
      lastNode = firstNode;

   mSize ++;
}

template<class T>
unsigned int vp::list<T>::size() {
   return mSize;
}


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
 
int main() {
   // Default Ctor
   vp::list<int> myList1;
   // Sized Ctor
   vp::list<int> myList2(3, 200);
   // Copy Ctor
   vp::list<int> myList3(myList2);
   
   // Display each list
   for (auto it : myList1)
      std::cout << "Prev:\t" << it->prev << "\n"
                << "Node:\t" << it << "\n"
                << "Next:\t" << it->next << "\n"
                << "Value:\t" << it->value << "\n\n";
      
   for (auto it : myList2)
      std::cout << "Prev:\t" << it->prev << "\n"
                << "Node:\t" << it << "\n"
                << "Next:\t" << it->next << "\n"
                << "Value:\t" << it->value << "\n\n";
      
   for (auto it : myList3)
      std::cout << "Prev:\t" << it->prev << "\n"
                << "Node:\t" << it << "\n"
                << "Next:\t" << it->next << "\n"
                << "Value:\t" << it->value << "\n\n";
   return 0;
}


I'm trying to use the for-range loop and running the debugger, I get errors at the end function. I swore I had this issue before but got it fixed. I did also try using a regular for loop and still had the same issues. Here is the specific end function though:
1
2
3
4
 
template<class T>
typename vp::list<T>::iterator vp::list<T>::end() {
   return iterator(lastNode->next);
}


I changed lastNode->next to just lastNode, but then it skips the last element. What am I missing?

Edit: I figured it out. The SEGFAULT is being caused by and empty list. I'm going to try returning NULL if it's empty.

Edit: Something else that I thought was really weird was that when using auto, a derefence operator isn't required on it to get the node's memory location, it seems to be forbidden. However, when making the type of it vp::list<int>::iterator, it's required. What does auto set it to? The private node?
Last edited on
cire (1845)
vp::list<int> myList1;
invokes:

1
2
 
  vp::list<T>::list() :
      firstNode(NULL), lastNode(NULL), mSize(0) {}


then end:

1
2
3
 
vp::list<T>::iterator vp::list<T>::end() {
   return iterator(lastNode->next);
}


So invoking end causes a null pointer to be dereferenced.
Volatile Pulse (1329)
Yeah, I figured that one out. I simply changed end to this:
1
2
3
4
5
6
 
template<class T>
typename vp::list<T>::iterator vp::list<T>::end() {
   if (empty())
      return iterator(lastNode);
   return iterator(lastNode->next);
}


But I am concerned about the way auto behaves. I understood that it determines the data type automatically from the context of how it's used, but I'm confused as to what auto is in this sense:
1
2
3
4
5
6
7
8
9
10
 
   // Uses iterator
   // Requires derefencing 'it'
   for (vp::list<int>::iterator it : myList1) {
      if (!it->prev)
         std::cout << "\t" << it->prev << "\nFirst->";
      std::cout << "\t" << *it << " Value:\t" << it->value;
      if (!it->next)
         std::cout << " <- Last\n\t" << it->next << "\n";
      std::cout << "\n";
   }

1
2
3
4
5
6
7
8
9
10
 
   // Uses auto
   // Forbids dereferencing 'it'
   for (auto it : myList2) {
      if (!it->prev)
         std::cout << "\t" << it->prev << "\nFirst->";
      std::cout << "\t" << it << " Value:\t" << it->value;
      if (!it->next)
         std::cout << " <- Last\n\t" << it->next << "\n";
      std::cout << "\n";
   }


I have tried looking around for a way to deduce what data type auto would transform into, but I couldn't find anything in this situation.
cire (1845)
It will be the type your list::iterator::operator* returns. Which, in this case is a pointer to a node.

That probably isn't quite right. An iterator shouldn't be returning a pointer to an implementation detail. It should be returning a reference to the data that is held by the node. Users iterating through a list shouldn't be concerned about next or previous pointers or what the data is called internally by the list.
coder777 (2377)
in addition to what cire said: In STL the end iterator is always excluded from processing, hence it would suffice to write end() like so:
1
2
3
4
 
template<class T>
typename vp::list<T>::iterator vp::list<T>::end() {
   return iterator();
}


So the operator -> would look like this: T &operator ->();
Last edited on
Volatile Pulse (1329)
Thanks for all of your help so far. Is there any issue with being able to access those elements, for example, next, last, value, etc? Should something be changed with my iterator, node, or list classes?

I also read on a stackoverflow forum that auto can select private classes, in this case node, which shouldn't be able to be accessed. Again, is this a problem? To me, I'm content with using auto in this situation since it's a pain to constantly type out vp::list<int>::iterator.

One last question. When looking at the STL implementation, it refers to Allocators. From http://cplusplus.com/reference/list/list/list/
explicit list ( size_type n, const T& value= T(), const Allocator& = Allocator() );
Repetitive sequence constructor: Initializes the container object with its content set to a repetition, n times, of copies of value.


Up until now, I have just ignored the Allocator since I've never used one for any STL container. Is this something I should look into implementing in my code? or should I just ignore it? For the most part, the rest of the functions of an STL list look pretty straight forward. Obviously, I'll have to do some error testing when it comes to seeing if my definitions are correct, much like the situation with my end function. Is there anything that you see or saw in my code thus far that may cause issues down the road?

Thanks again for all of your help though.

Edit: Trying to switch my it type to vp::list<int>::iterator* yields this error:
C:\Programming\List Practice\main.cpp|275|error: cannot convert 'vp::list<int>::node*' to 'vp::list<int>::iterator*' in initialization|


That makes me assume that auto actually uses a node pointer, which again should be restricted, is irrelevant to me, but shouldn't my iterator class be convertible from a node to prevent needing a node?
Last edited on
Volatile Pulse (1329)
coder777 wrote:
So the operator -> would look like this: T &operator ->();


So then what would actually be getting returned? If I return current->value, I'll receive an int in this situation which isn't comparable to an iterator. I don't know what else should be returned instead of a node. Possibly an iterator reference instead? Everything so far was just to get by, now I'm running in to issues with simple implementations and I don't enjoy that.

I'm getting stuck with what an iterator should be in this case. Obviously I don't want it to be a node, I don't want it to be T& either.
coder777 (2377)
I don't want it to be T& either.
You want it, trust me.

So then what would actually be getting returned? If I return current->value, I'll receive an int in this situation which isn't comparable to an iterator. I don't know what else should be returned instead of a node. Possibly an iterator reference instead? Everything so far was just to get by, now I'm running in to issues with simple implementations and I don't enjoy that.
I don't know what you're trying to compare. You compare iterator with iterator, nothing else. You cannot compare the content of an iterator with an iterator itself (that wouldn't make sense)


to make your iterator compliant to STL it looks like this;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
         class iterator {
            private:
               node *current;
            public:
               iterator();
               iterator(node *n);
               iterator operator =(iterator n);
               // You need this comparison operator:
               bool operator ==(const iterator &it) const
               {
                 return (current == it.current);
               }
               bool operator !=(const iterator &it) const
               {
                 return !operator ==(it);
               }
               iterator& operator ++();
               iterator operator ++(int);
               iterator& operator --(); // you can go back, so why not
               iterator operator --(int); // you can go back, so why not
               T &operator ->();
               T &operator *();
         };
Volatile Pulse (1329)
I must have had the wrong concept of what an iterator was then -.-

Anyways, I made the above changes and I ended up with something that looks weird so I cross checked it with the STL list and it has the same affect. Looping through the list with iterators, every value has the same exact memory location. Is this right?

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
 
int main() {
   // Default Ctor
   vp::list<int> myList1;
   std::list<int> STLList1;
   // Sized Ctor
   vp::list<int> myList2(3, 200);
   std::list<int> STLList2(3,200);
   // Copy Ctor
   vp::list<int> myList3(myList2);
   std::list<int> STLList3(STLList2);
   
   myList1.push_back(300);
   STLList1.push_back(300);
   
   // Display each list
   for (auto it : myList1)
      std::cout << &it << " " << it << "\n";
   std::cout << "\n";
   for (auto it : STLList1)
      std::cout << &it << " " << it << "\n";
   std::cout << "\n";
   for (auto it : myList2)
      std::cout << &it << " " << it << "\n";
   std::cout << "\n";
   for (auto it : STLList2)
      std::cout << &it << " " << it << "\n";
   std::cout << "\n";
   for (auto it : myList3)
      std::cout << &it << " " << it << "\n";
   std::cout << "\n";
   for (auto it : STLList3)
      std::cout << &it << " " << it << "\n";
   std::cout << "\n";
   return 0;
}


0x22fed0 300

0x22fec4 300

0x22feb8 200
0x22feb8 200
0x22feb8 200

0x22feac 200
0x22feac 200
0x22feac 200

0x22fea0 200
0x22fea0 200
0x22fea0 200

0x22fe94 200
0x22fe94 200
0x22fe94 200


Also, why can't you compare an iterator with list.begin() like if (it == myList1.begin())? I get the error 
C:\Programming\List Practice\main.cpp|288|error: no match for 'operator==' in 'it == myList1.vp::list<T>::begin<int>()'|


I also get a very similar error with the STL lists. Why aren't iterators comparable? or am I comparing the wrong things?
coder777 (2377)
Looping through the list with iterators, every value has the same exact memory location. Is this right?
Yes, it's right. it by the way is not an iterator but the value which content is set during each iteration.

What strange is, is this:
it == myList1.vp::list<T>::begin<int>()
where does this template parameter come from?

otherwise iterators of the same type are comparable since you implement them so.
Last edited on
Volatile Pulse (1329)
That was the error returned from g++ while trying to compare it and myList1.begin().

And I'm confused. Why don't we want an iterator but instead want the value? I think I'm confusing myself now, but shouldn't auto be an iterator instead of T? I'm going to have to take a look again at how everything should interact.

If I understand correctly, an iterator isn't really being used by myself, but more by the compiler to traverse the list in the range. I assume the reason it returns the value is so that you can change what you need to without having access to private data. But then, are iterators the only way to traverse the list? Can pointers not be used like they are in arrays? Or instead of a pointer, something similar?

In theory, shouldn't something like this work?
1
2
 
iterator it = list.begin();
it ++; // now points to the second item


Or does it work, but I just need to specify an iterator instead of T when declaring 'it'.
cire (1845)
If you write:

1
2
 
   for (auto it : myList1)
      std::cout << &it << " " << it << "\n";


For all practical purposes, it expands to:

1
2
3
4
5
 
for ( auto _iterator = myList1.begin(); _iterator != myList1.end(); ++_iterator )
{
    auto it = *_iterator ;
    std::cout << &it << " " << it << "\n" ;
}


Typically, the range-based for loop would be used with a reference type so you aren't making copies of each item in the list:

1
2
 
    for ( auto& element : myList1 )
        std::cout << element << '\n' ;


It is just shorthand for the longer version.
Last edited on
Pages: 12345

C++

Forum