Issues with implementing an iterator

Question

I wrote the following code when trying to create a doubly linked list with an internal STL-like iterator. I will just put the header file with non-relevant parts truncated at the moment.

My questions...

• STL uses iterators in a certain way - in particular, you navigate the STL container from the .begin () iterator to, but not including the .end () iterator. To do this, the .end () iterator must be one after the end of the container. How would I implement this semantics based on what I started with (this is the main question)?

• Is there anything in the interface that stands (regarding the iterator class and what should be present in it)?

Here is the code:

template <typename T> class Node { T data; Node<T>* next; Node<T>* prev; }; template <typename T> class LinkedList { public: class Iterator { public: Iterator() {} explicit Iterator(const Node<T>& init) { current = init; } //Dereference operator - return the current node data. inline T& operator*() { return current->data; } //Prefix returns by reference. inline Iterator& operator++() { current = current->next; return *this; } inline Iterator& operator--() { current = current->prev; return *this; } //Postfix returns non-reference and has int parameter to differentiate function signature. inline Iterator operator++(int) { Iterator res = *this; current = current->next; return res; } inline Iterator operator--(int) { Iterator res = *this; current = current->prev; return res; } private: Node<T>* current; }; Iterator begin() { return Iterator(m_start); } Iterator end() { return Iterator(m_end); } private: Node<T>* m_start; Node<T>* m_end; }; 

I know that I may or may not have problems with ++ / - operators, but this doesn’t bother me much, since I will work with them when I have enough code to carry out some tests on this, Do not hesitate to throw hints although if you are inclined :)

Answer 1

• The first node prev pointer is NULL, so the last node is the next pointer. The one-to-end pointer current would be NULL.

• operator->

Answer 2

• The iterator returned by end() must be decrementable, otherwise you cannot iterate over the list in reverse order. You can do this if Iterator stores two pointers: to the current node (which will be NULL for the end) and the previous node (which allows you to find the last node with the data in it, even if current == NULL .

   class Iterator { public: Iterator() {} explicit Iterator(Node<T>* curr, Node<T>* prev): current(curr), previous(prev) {} //Dereference operator - return the current node data. inline T& operator*() { return current->data; } //Prefix returns by reference. inline Iterator& operator++() { previous = current; current = current->next; return *this; } inline Iterator& operator--() { current = previous; previous = current->previous; return *this; } //Postfix should be implemented in terms of prefix operators inline Iterator operator++(int) { Iterator res = *this; ++*this; return res; } inline Iterator operator--(int) { Iterator res = *this; --*this; return res; } private: Node<T>* current; Node<T>* previous; }; Iterator begin() { return Iterator(m_start, 0); } Iterator end() { return Iterator(0, m_end); } 

  Alternatively, you can have a watch node in your list that indicates “one end of the past” in the list. However, this node must have a data item. This can be achieved by dividing the node class into a base without templates, pointing only to the pointers to the next and previous node.

  For example, it seems that the implementation of the GCC list holds a pointer to the watch, so its next points to the first element in the list, and its prev points to the last element in the list (or both points for itself if the list is empty).

• You are missing operator-> , operator== and operator!= , Classified typedefs that can be inherited from std :: iterator , implementation of const_iterator (iterator must be implicitly converted to const_iterator).

Answer 3

• I think NULL will do just fine here.
• You might want to write something like for (iterator it = list.begin(); it != list.end(); it++) , so you also need comparison operators.