Implementation - Iterators
Iterators are objects that are used to traverse and access data within a container class without exposing the internal structure of the container.
Consider the following typical usage for an iterator for a container (like list) in the C++ Standard library:
The for loop in the above code sample prints out every value within ll. There is no need for the user to actually know what ll is. We could have changed list to vector (or some other container class) and the for loop for printing every value would not look different. We don't need to know that list is basically a linked list or that vector is essentially an array... the iterators define a way for us to access every piece of data within the container class.
In this section we will look at how to implement an iterator for our linked lists.
const_iterator vs iterator
Firstly, we need to be aware that we have two different iterators that we will need to implement. a const_iterator and an iterator. We need to understand what the difference is. A const_iterator does not allow the modification of the data within the container while an iterator does. When you pass containers to functions, you typically either pass its address or you pass by reference. To make it safe, you may make the pointer or reference const. You would not be able to use a iterator to go through this sort of container but you can use a const_iterator. Furthermore you must support the assignment of iterators into const_iterators but not the other way around.
Iterator Functionality
The iterators we will write will support the following functionality:
operator ++(makes iterator point to next piece of data. two versions, post and pre-fix)
operator -- (makes iterator point at previous piece of data. two versions, post and pre-fix)
operator * (dereference operator)
operator == (compares two iterators, returns true if they refer to the same piece of data)
operator != (compares two iterators, returns true if they do not refer to the same piece of data
We also need to add functions to the linked list class so that it will return iterators to the first piece of data within the list as well as one past the last item the list (begin() and end())
To allow assignment of iterators to const_iterators (but not the other way around) we will create a heirarchy where const_iterator is the base class and iterator is the derived class. Furthermore, we will also declare these iterators into the linked list class itself (publically).
Default Constructors
Both the iterator and const_iterator class has a default public constructor that sets the iterator to safe state.
Friends
Even though the iterator classes are part of DList, DList will not have access to their private members. To allow access, we must declare that DList is a friend of each of the iterators.
begin()/cbegin() and end()/cend()
begin()/cbegin() returns an iterator/const_iterator that refers to the first piece of data in the container. In this case this is the node pointed to by front_. end()/cend() returns an iterator/const_iterator to the item that follows the last piece of data in the container. In this case, it would be a nullptr.
end() does not return iterator to last item. It returns an iterator to whatever is AFTER the last item
Dereference (*)
The dereference operator is how we access the data within each node. There are two versions. One returns a reference to the data the other a const reference to the data. Only the iterator (not const_iterator) can return the non-const reference to the data.
Increment and Decrement (++ and --)
Both the ++ and -- operators have a prefix and postfix version. The ++ operator makes the operand point to the "next" item (one closer to the end) in the list. The -- operator makes the operand point to the "previous" item (one closer to the beginning of the list. Both the prefix and postfix versions of the operators do the same thing to the operand. The difference is in what is returned. In the prefix version of the operator, the operator returns an iterator that refers to the same object as the operand. In the postfix versions of the operator, the operator returns an iterator to the object the operand pointed at before it was altered.
prefix and postfix refers to the position of the operator with respect to the operand
pre_fix - operator comes before (pre) the operand (++x or --x) post_fix-operator comes after (post) the operand (x++ or x--)
What data must we have?
It is probably pretty obvious that we will need to store a Node* in the iterator object. It can be used to refer to a node and access the data within the node. However, that will not be quite enough. Consider the following:
According to specs, if you did the following ++x followed by --x, x should end up back where it started. Suppose initially x was referring to the last node in the list. ++x would make x refer to end(). if you then did --x you should be able to get back to the last node. To support this in your implementation you must store enough information to get back to the last node after you hit end(). Now, if all you store is a Node*, then end() would simply set that pointer to nullptr. There is no way for you to get back to any node within the list as there isn't any reference to the list or any nodes within it.
Thus, in order to allow the above to occur we will not only need a Node* but we will also need to store a pointer the DList object itself. This way, we can use the DList pointer to find its last node.
Private Constructors
It would be advantageous to create private constructors to iterator. These would only be accessible from members of DList and simplify construction.
Putting all this together
Last updated