Implementing Iterators

Section 28.2 Implementing Iterators

Iterators provide both a uniform abstraction for working with different types of collections and a way for those collections to expose their internal structure in a controlled manner. When you ask a collection for an iterator, you get an object that is like a pointer, but only allows you to do certain operations.

🔗

Say we have a linked list and ask for an iterator using something like ListIterator myIterator = myList.begin();. What we get back is an iterator object that contains a pointer to the first node in the linked list:

🔗

A linked list with three nodes. There is an object myIterator that contains a pointer named currentNode that points to the first node in the list.🔗 — Figure 28.2.1. An iterator tracking the first node in a linked list.
🔗

If we were given a raw pointer to the first node, we would need to know the details of how the linked list is implemented in order to move to the next node. (Whether to say currentNode->next, currentNode->m_next, or something else.). We also would be able to manipulate the list node we were pointing at, potentially breaking the list structure.

🔗

The iterator object insulates us from those details and guards the data structure against accidental corruption. It provides a set of operations that we can use to move through the list and access the elements, without exposing the internal structure of the list itself. These are implemented as operator overloads on the iterator class:

🔗

Listing 28.2.2. ListIterator class implementation

🔗

template <typename T>
class ListIterator {
private:
    ListNode<T>* currentNode;
public:
    // Constructor to initialize the iterator that starts at a given node
    ListIterator(ListNode<T>* startNode) {
        currentNode = startNode;
    }

    // Returns a reference to the element at the current position
    T& operator*() {
        return currentNode->data;
    }

    // Advances the iterator to the next position
    ListIterator& operator++() {
        currentNode = currentNode->next;
        return *this;
    }

    // Compare two iterators for equality/inequality
    bool operator==(const ListIterator& other) const {
        return currentNode == other.currentNode;
    }

    bool operator!=(const ListIterator& other) const {
        return currentNode != other.currentNode;
    }
};

Those operators are some of the basic building blocks we can use to implement algorithms like traversing the linked list:

🔗

for(ListIterator<int> it = myList.begin(); it != myList.end(); ++it) {
    cout << *it << " ";
}

Two of the operators here are particularly important:

The dereference operator (*it) allows us to access the element at the current position. It returns a reference to the data, which means we could use something like *it = 10; to modify the element. However, we can only use it to access currentNode->data. It gives us no access to the next pointer in the node.

🔗
The preincrement operator (++it) allows us to move to the next element in the list. It could be implemented as a void function, but returning a reference to the iterator allows us to chain operations and use the iterator in more complex expressions.

🔗

🔗

Other than the type of the iterator (which we could declare using auto), this is the same syntax we would use for printing any standard container. However, it does depend on being able to ask myList for iterators using myList.begin() and myList.end(). We will tackle that in the next section.

🔗

Our ListIterator meets the criteria for being a forward iterator, because it supports moving forward through the collection using the preincrement operator (++it) and dereferencing to access the element at the current position (*it). If we were implementing an iterator for a doubly linked list, we might also implement the predecrement operator (--it) to allow moving backwards through the list, making it a bidirectional iterator. If we were implementing an iterator for a vector, we could implement addition and subtraction operators, as well as the subscript operator ([]) to jump to specific positions, making it a random access iterator.

🔗

Checkpoint 28.2.1.

Imagine we are implementing an iterator for an ArrayList<T>. We might implement it by storing the address of the array and an index to the current position as shown below:

🔗

template <typename T>
class ArrayListIterator {
private:
    T* arrayPtr; // Pointer to the array
    size_t index; // Current index in the array
public:
    ArrayListIterator(T* arr, size_t startIndex);
    ArrayListIterator& operator++();
    T& operator*();
    bool operator==(const ArrayListIterator& other) const;
    bool operator!=(const ArrayListIterator& other) const;
};

Which definition would be correct for the preincrement operator (++it)?

🔗

ArrayListIterator& ArrayListIterator::operator++() { 
  ++index;
  return *this; 
}

ArrayListIterator& ArrayListIterator::operator++() { 
  arrayPtr += index;
  return *this; 
}

We are trying to move forward one position.

ArrayListIterator& ArrayListIterator::operator++() { 
  index += arrayPtr;
  return *this;
}

We are trying to move forward one position.

ArrayListIterator& ArrayListIterator::operator++() { 
  ++arrayPtr;
  return *this;
}

We want to change where we are in the array. This changes where we think the start of the array is.

🔗

Checkpoint 28.2.2.

Hint 1.

The dereference operator should return the element at the current index in the array.

🔗

Hint 2.

Use [ ] to access the element at the current index in the array.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next