Diving into C++ Iterators

#cpp #container #iterator

Data structures have been covered extensively but iterators are often in their shadow. This article centers on iterators instead, specifically C++ iterators. We'll explore what they are, why we need them and their various types.

As the name suggests, iterators often come up when traversing through elements of a container. They are produced from C++ containers or streams through functions like begin() and end(). Some common use cases are illustrated in Listing 1.

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> v{46, 34, 97, 55};

    std::cout << "Initial order:";
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    std::sort(v.begin(), v.end());

    std::cout << "Final order:";
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

Listing 1: Vector Iterators

Observations:

An object of type vector<int>::iterator is generated from the vector.
It is dereferenced like a pointer in the body of the loop.
It is incremented to get to the next vector element.
It is compared with the iterator at the end of the vector to check for loop termination.
It is passed to standard functions like sort.

We can thus deduce that an iterator is a pointer-like object that can be incremented with ++, dereferenced with * and compared against another iterator with !=. That's a good start; iterators are in-fact wrappers around pointers. Why do we need a separate type for them? Couple reasons:

They abstract away containers hence enabling algorithms to be generic. In Listing 1, the vector was sorted with std::sort() which takes iterator arguments. The same function can sort any other container/array that generates the same kind of iterator; we'll later explore the various kinds of iterators. In addition to that, std::sort() can be used to sort a portion of the data structure by passing iterators from the interior.
Efficiency: Iterators are pointers, Functions that take Iterator arguments instead of containers avoid expensive copying of all elements. If std::sort() took vector instead, the vector would have to be copied on function call as well as on return (twice if the returned vector is assigned to another variable). Moreover, we'd need a different sort function for all the different data types.

As hinted above, there are different classes of iterators. They don't map to C++ classes but are based on the kinds of operations they support. These are:

Input Iterators
Output Iterators
Forward Iterators
Bidirectional Iterators
Random access Iterators

Some iterators are more powerful than others, you can think of them as classes derived from weaker ones as shown in the hierarchy below.

An iterator supports all operations for its kind as well as all above it. The kind of iterators a data structure generates determines the kind of operations it supports. Lets dive in, starting from the top.

1. Input iterators

Input iterators support the following operations.

Increment with iter++ and ++iter.
Comparison with other iterators using == and !=.
Pointer dereference to read data at the address but not store to it.

istream iterators for input streams are good examples of Input Iterators. Listing 2 demonstrates how they are used with standard input. Assigning to *iter would not compile since it is read-only.

#include <iostream>
#include <iterator>

int main()
{
    std::cout << "Enter a stream of numbers terminated by Ctrl+Z: ";

    std::istream_iterator<double> eos;           // end-of-stream iterator from default constructor
    std::istream_iterator<double> iter(std::cin); // stdin iterator

    double sum = 0;
    while (iter != eos)
    {
        sum += *iter;
        ++iter;
    }

    std::cout << "The sum of the numbers is: " << sum << '\n';

    return 0;
}

Listing 2: Input Iterators

2. Output iterators

Output iterators support the following operations.

Increment with iter++ and ++iter.
Comparison with other iterators using == and !=.
Pointer dereference to store data at the address but not read from it.

They are similar to Input Iterators but differ in that they are write-only instead of read-only. ostream iterators for output streams are good examples of output Iterators. Listing 3 samples how they are used. Reading from *iter would not compile since it is write-only.

#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    std::vector<int> v{46, 34, 97, 55};

    std::cout << "Printing vector contents: ";
    std::ostream_iterator<int> iter(std::cout, ", ");
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        *iter = *it;
        ++iter;
    }
    return 0;
}

Listing 3: Output Iterators

3. Forward iterators

Forward iterators support the following operations.

Increment with iter++ and ++iter.
Comparison with other iterators using == and !=.
Pointer dereference to read and store data at the address.

As the hierarchy suggests, they combine InputIterator and OutputIterator. As the name suggests, they can not be decremented. Forward list iterators are good examples of purely forward iterators. std::forward_list is implemented as a singly linked list hence allows traversing the elements only in forward direction. Listing 4 shows they work. They can read and store data but calling it-- to iterate in reverse would not compile.

#include<forward_list>
#include <iostream>
#include <iterator>

int main()
{
    std::forward_list<int> fl{46, 34, 97, 55};

    std::cout << "Before mutation: ";
    for (std::forward_list<int>::iterator it = fl.begin(); it != fl.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    for (std::forward_list<int>::iterator it = fl.begin(); it != fl.end(); ++it)
        *it = *it * 2;

    std::cout << "After mutation: ";
    for (std::forward_list<int>::iterator it = fl.begin(); it != fl.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

Listing 4: Forward Iterators

4. Bidirectional iterators

Bidirectional iterators support the following operations.

All forward iterator operations.
Decrement with iter-- and --iter.

They are similar to forward iterators but they can be decremented. std::list which is implemented as a doubly linked list generates bidirectional iterators. List iterators are good examples of purely bidirectional iterators as illustrated in Listing 4. The first two loops shows operations inherited from forward iterators. The last loop traverses the list in reverse. Since list::end() returns an invalid pointer past the last element, decrement operator is used to get the last element. It would be cleaner to simply subtract 1 but arithmetic operations are not supported. Similarly, the first element is printed after the loop because we can't get past the first element by subtracting from list::begin().

#include <list>
#include <iostream>
#include <iterator>

int main()
{
    std::list<int> l{46, 34, 97, 55};

    std::cout << "Before mutation: ";
    for (std::list<int>::iterator it = l.begin(); it != l.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    for (std::list<int>::iterator it = l.begin(); it != l.end(); ++it)
        *it = *it * 2;

    std::cout << "After mutation, in reverse order: ";
    std::list<int>::iterator it;
    for (it = --l.end(); it != l.begin(); --it)
        std::cout << ' ' << *it;
    std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

Listing 4: Bidirectional iterators

5. Random access iterators

Random access iterators support the following operations.

All bidirectional iterator operations.
Pointer arithmetic i.e addition or subtraction with a constant.
All comparisons i.e <, >, <=, >=

They are the most powerful iterators. They are generated by array based data structures such as array, std::vector and std::string. Listing 5 demonstrates these operations using vector iterators.
The first two loops shows the operations inherited from bidirectional iterators. The third loop traverses the list in reverse, but more elegantly than list iterators as a result of the following:

We can subtract 1 from list::end() to get the last element.
We can make the loop go all the way to the first element by using >= operator.

Moreover, the vector can be sorted std::sort() which only takes random access iterators.

#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

int main()
{
    std::vector<int> v{46, 34, 97, 55};

    std::cout << "Before mutation: ";
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        *it = *it * 2;

    std::cout << "After mutation in reverse order: ";
    std::vector<int>::iterator it;
    for (it = v.end() - 1; it >= v.begin(); --it)
        std::cout << ' ' << *it;

    std::cout << '\n';

    std::sort(v.begin(), v.end());

    std::cout << "After sorting:";
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

Listing 5: Random access iterators

And that friends, is iterators in a nutshell. Since the kind of iterators generated by a data structures determines the operations they support, Iterator knowledge comes handy when choosing data structures. Happy hacking!