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:

std::list<int> ll;
...
std::list<int>::const_iterator it;
for(it = ll.begin();it !=ll.end();it++){
    std::cout << *it << std::endl;
}

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.

template <typename T>
class DList{
...
public:
    class const_iterator{

    public:
        const_iterator(){...}
        const_iterator operator++(){...}     //prefix
        const_iterator operator++(int){...}  //postfix
        const_iterator operator--(){...}     //prefix
        const_iterator operator--(int){...}  //postfix
        const T& operator*() const{...}
        bool operator==(const_iterator rhs) const{...}
		bool operator!=(const_iterator rhs) const{...}
    };
    class iterator:public const_iterator{
    public:
        iterator(){...}
        iterator operator++(){...}     //prefix
        iterator operator++(int){...}  //postfix
        iterator operator--(){...}     //prefix
        iterator operator--(int){...}  //postfix
        T& operator*(){...}
        const T& operator() const{...}   
    };
    const_iterator cbegin() const{...}
    const_iterator cend() const{...}
    iterator begin(){...}
    iterator end(){...}
    ...
};

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

prefix - operator comes before (pre) the operand (++x or --x) postfix-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.

Access Control

We should never allow Node to be exposed publicly. Thus any function that can set the Node* curr_ must not be public. The only function that exposes Node are the constructors const_iterator(Node* curr, const DList* theList) and iterator(Node* curr, const DList* theList), so these two must not be public. the iterator constructor must be able to access the constructor const_iterator(Node* curr, const DList* theList), so that constructor should be protected. the iterator constructor can be private or protected in this case.. most important is that its not public.

Putting all this together

template <typename T>
class DList{
...
public:
    class const_iterator{
        friend class DList;
    protected:
        const DList* myList_;
        Node* curr_;
        const_iterator(Node* curr, const DList* theList){ 
            curr_ = curr;
            myList_=theList;
        }
    public:
        const_iterator(){
            myList_=nullptr;
            curr_=nullptr;
        }
        //prefix
        const_iterator operator++(){ 
            curr_=curr_->next_;
            return *this;
        } 
        //postfix
        const_iterator operator++(int){
            const_iterator old=*this;
            curr_=curr_->next_;
            return old;
        }
        //prefix
        const_iterator operator--(){
            if(curr_){
                curr_=curr_->prev_;
            }
            else{
                if(myList_){
                    curr_=myList->back_;
                }
            }
            return *this;
        } 
         //postfix            
        const_iterator operator--(int){
            const_iterator old=*this;
            if(curr_){
                curr_=curr_->prev_;
            }
            else{
                if(myList_){
                    curr_=myList->back_;
                }
            }
            return old;        
        } 
        const T& operator*() const{return curr_->data_;}
        bool operator==(const_iterator rhs) const{
            bool rc=false;
            if(myList_==rhs.myList_ && curr_==rhs.curr_)
                rc=true;
            return rc;
        }
		bool operator!=(const_iterator rhs) const{
		    return !(*this==rhs);
		}
    };
    class iterator:public const_iterator{
        //NOTE: the LACK OF data members here. 
        //the curr_ data member is inherited from const_iterator class
        //DO NOT redeclare or the two pointers will be out of sync and
        //potentially cause conflict.
        friend class DList;
        iterator(Node* curr,DList* theList):const_iterator(curr,theList){}
    public:
        iterator():const_iterator(){}
        iterator operator++(){
            //Some compilers will complain if you try to 
            //to access curr_ the same way as const_iterator version
            //of the code.  It will say curr_ is undeclared
            //To get pass this use this-> to access the members of
            //base class:   
            this->curr_= this->curr_->next_;
            return *this;            
        } 
        iterator operator++(int){...}  //postfix
        iterator operator--(){...}     //prefix
        iterator operator--(int){...}  //postfix
        T& operator*(){...}
        const T& operator() const{...}    
    
    };
    const_iterator cbegin() const{return const_iterator(front_,this);}
    const_iterator cend() const{return const_iterator(nullptr,this);}
    iterator begin(){return iterator(front_,this);}
    iterator end(){return iterator(nullptr,this);}
    ...
};