Encoding an Iterator for the IntList Class

Before we can write an iterator for the IntList class, we need to have a clear idea of how the iterator will be represented in memory and how, in general, it will behave. In other words, we need to understand the interface and encoding of the iterator.

Reminder: What is an Iterator? (The Iterator Interface)

An iterator is an object that allows a programmer to traverse a container, particularly lists. It provides a way to access the elements of the container without exposing the underlying representation. In C++, iterators are typically implemented as classes that allow programmers to use the familiar syntax they would use to move a pointer across an array even though the underlying data structure maybe nothing at all like an array.

In the same way that array iteration begins at the start of the array and continues until we have gone off the end of the array (at which point we stop), data structures that provide iterators typically provide two functions:

begin()

Returns an iterator position on the first element of the container.

end()

Returns an iterator position just past the last element of the container.

• Important: Despite the name, end() does not return an iterator positioned on the last element of the container. Instead, it returns an iterator positioned just past the last element of the container.

The fundamental operations of an iterator are

*iter

Access the value at the current position of the iterator.

• When an iterator is past the end of the container (i.e., equal to the value returned by end()), using *iter to access the value is against the rules.
• If an iterator refers to a value that is then removed from the container (say, by a pop_front operation), then it is considered invalid and using *iter to access the value is against the rules.

++iter

Move the iterator to the next position in the container.

• Important: The implementation of ++ probably does not use ++ anywhere in its implementation, unless the underlying data structure is actually an array (which it isn't in our case).
• If an iterator is on the last element of the container, it is totally fine to call ++iter, which will move it to the position just past the end of the container (i.e., equal to the value returned by end()). In fact, the easiest way to work out what end() should return is to think about what would naturally happen if you were at the last element of the container and you did ++iter—whatever that would give you is what end() should return!
• If an iterator is already past the end of the container (i.e., equal to the value returned by end()), using ++iter is against the rules.

iter == other

Determine whether two iterators are at the same position in the container.

• Important: If two iterators are at different points in the container, but that container has the same value at both those points, == should still return false, because the iterators are at different positions.
• If iterators come from different lists, using == to compare them is against the rules.

iter != other

The opposite of ==.

All these operations must run in constant time.

Note that, under this specification, although various forms of misuse are against the rules, we do not specify what happens if the user misuses the iterator. While in other code we've written, it would be fairly easy to check for misuse and throw an exception, in this case, doing so would add a lot of complexity to the implementation of the iterator, and you should not worry about how to handle misuse: take a “whatever happens, happens” approach.

Additional Specifics of Our IntList::const_iterator Class

Our iterator will be a const_iterator, meaning that it allows access to the values in the list, but does not allow modifying them. Many C++ classes provide both iterator (allowing list items to be updated) and const_iterator types, but to keep things simple, we will only provide const_iterator.

Although external users will call it as IntList::const_iterator, inside the implementation of the IntList class, we will just call it Iter (i.e., IntList::Iter), using a type alias to make it available as const_iterator to external users.

IntList::Iter Encoding

Our iterator is encoded as a pointer to a Node.

The diagram below shows iterator that is set at the second node of our list, allowing access to both the value stored in that element, and the next node along in the list.

Your Task, Part 1: Updating intlist.hpp

Although in principle the iterator interface is exactly as described above, in practice, C++ requires us to add some additional verbiage to allow useful algorithms from the C++ standard library to work with our iterator. For that reason, we'll provide you with the full declaration of the IntList::Iter class for intlist.hpp, and your task in the next major part of the assignment will be to implement the member functions of that class in intlist.cpp.

Change the start of intlist.hpp that currently looks like this:

class IntList {
 public:

so that it looks like this:

class IntList {
 private:
    // Forward declaration of private class.
    class Iter;

 public:
    // Public type alias for the our internal Iter class.
    using const_iterator = Iter;

Then, add this code to the bottom of the private section of the IntList class in intlist.hpp:

    /*
     * Iter
     * C++-style const_iterator for IntList.
     */
    class Iter {
     public:
        // Iterator traits
        //   These definitions are required by the standard library to make
        //   iterators work correctly in generic algorithms.
        using value_type = int;
        using reference = const value_type&;
        using pointer = const value_type*;
        using difference_type = ptrdiff_t;
        using iterator_category = std::forward_iterator_tag;

        // Provide all the usual operations for a forward iterator

        Iter() = default;
        Iter(const Iter&) = default;
        Iter& operator=(const Iter&) = default;
        ~Iter() = default;

        Iter& operator++();
        const int& operator*() const;
        bool operator==(const Iter& rhs) const;
        bool operator!=(const Iter& rhs) const;

     private:
        // Friends can create non-default iterators and access current_.
        friend class IntList;
        explicit Iter(Node* current);

        Node* current_ = nullptr;  // The current list node
    };

Finally, add

    const_iterator begin() const;

    const_iterator end() const;

to the public: section of the IntList class in intlist.hpp with the other public member-function declarations. Provide comments to match the style of the other member-function declarations.

You can check to make sure that you haven't introduced any syntax errors in the header by running make intlist.o.

Your Task, Part 2: Writing Test Cases for the IntList::const_iterator

As before, our pattern is to write test cases first. So now we need to write those test cases. They're actually fairly straightforward. One possible test might be something like

• Use a loop to push the numbers 0 through 9 onto an IntList.
• Use an iteration loop to check that the values in the list are indeed 0 through 9.

The iteration loop will necessarily use begin(), end(), ++, *, and !=, thus testing all the operations of the iterator.

You can check the code for syntax errors by running make intlist-test.o. Obviously, you can't test against IntList yet, since you haven't implemented it, but at least you can check for serious issues with the tests.

#include "intvector.hpp"
#define IntList IntVector   // Hack, substitute IntVector for IntList

(When logged in, completion status appears here.)