Diving into C++ Iterators
Tags: cpp, container, iterator
Published: 2022-07-05 23:34:25

---
title: Diving into C++ Iterators
published: true
description: 
tags: Cpp, container, iterator
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rpy6lazkggbce88hz9mp.jpg
# Use a ratio of 100:42 for best results.
---
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**.
 
```C++
#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:

1. Input Iterators
2. Output Iterators
3. Forward Iterators
4. Bidirectional Iterators
5. 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. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uq19tdir050phqjmu6k3.png)

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.

```C++
#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.

```C++
#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.

```C++
#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()`.

```C++
#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.

```C++
#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!