What is an iterator?

An iterator in C++ is an object that provides a way to access elements within a container (such as arrays, vectors, lists, etc.) in a sequential manner. It acts as an abstraction that allows algorithms to traverse through the elements of a container without exposing the underlying implementation details of the container.

Iterators serve as a bridge between algorithms and data structures, providing a standardized way to access, modify, and iterate over elements within a container. They encapsulate the logic for traversing the container, abstracting away concepts like memory addresses, indices, and container-specific navigation mechanisms.

An iterator in C++ STL is an object that facilitates traversal through the elements of a container. It acts as a pointer-like interface, enabling sequential access to the elements contained within the container, providing a uniform way to access its elements regardless of the container type.

Normal Iterator Syntax:

In the normal iterator syntax, we explicitly declare the iterator type (std::vector<int>::iterator)

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Declare iterator object
    std::vector<int>::iterator it;

    // Iterate through the vector using the iterator
    for (it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Using auto keyword:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Iterate through the vector using auto keyword
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

With the introduction of the auto keyword in C++11, we can simplify the iterator declaration by allowing the compiler to deduce the type of the iterator from the container itself. This makes the code more concise and easier to read.

Using auto in the iterator declaration automatically deduces the correct iterator type (std::vector<int>::iterator) based on the type of the container (std::vector<int>)

Iterator Types

Based on their functionality, Iterators are divided into 5 group.

1. Input iterators
2. Output iterators
3. Forward iterators
4. Bidirectional iterators
5. Random Access iterators

1. Input Iterator (read only, forward moving)

It provide a mechanism for single-pass traversal of container elements in a forward direction. With input iterators, developers can read values from the pointed-to element of a container but cannot modify the elements or perform random access operations.

It is commonly used in scenarios where read-only access to elements is sufficient, such as parsing input streams or processing data sequentially.

We can iterate forward using ++, and read values using * or member values using ->.

Syntax:

// Declaration of iterator variable
container_type::iterator it;

// Initialization of iterator with begin() function
it = container.begin();

// Looping through container using iterators
while (it != container.end()) {
    // Accessing element using dereferencing operator
    std::cout << *it << " ";

    // Advancing iterator to the next element
    ++it;
}

// Alternatively, the loop can be implemented using a for loop:
for (container_type::iterator it = container.begin(); it != container.end(); ++it) {
    std::cout << *it << " ";
}

Example:

Consider the example, usage of input iterators to traverse a vector:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Using input iterators to traverse the vector
    std::vector<int>::iterator it;
    for (it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Characteristics of Input Iterators:

1. Single-Pass traversal: Input iterators allow traversing the container elements only once, moving sequentially from one element to the next.
2. Read-only access: Input iterators facilitate reading values from container elements but do not permit modification of the elements.
3. Forward direction: Input iterators support traversal in a forward direction, progressing from the beginning towards the end of the container.

2. Output Iterator (write only, forward moving)

An output iterator is an iterator type that facilitate writing values to the pointed-to element within a container. Unlike input iterators, which only read operations, Output iterators allow for the modification or generation of elements in the container. 

We can iterate forward using ++, and write values using *. The = operator can be used to write values.

Characteristics of Output Iterators:

1. Single-Pass Forward Traversal: Like input iterators, Output iterators support single-pass traversal of elements in a forward direction. They provide a means to sequentially write values to the container, iterating from the beginning to the end.
2. Write-Only Access: Output iterators are designed exclusively for writing values to the container. They do not support reading or accessing existing elements within the container. Their purpose is to populate or modify the container contents during traversal.
3. Mutable Element Assignment: Output iterators allow the assignment of values to the elements they point to within the container. This enable dynamic modification of container element during iteration.
4. No Random Access: Unlike Random Access iterators, Output iterators do not provide direct access to arbitrary container elements using arithmetic operations like addition and subtraction. They are primarily intended for sequential writing rather than random access.

Example:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    vector<int>::iterator itr;

// Output Iterator
    for (itr = v.begin(); itr != v.end(); ++itr) {
        *itr *= 100;
    }

// Input Iterator
    vector<int>::iterator inputItr;
    for (inputItr = v.begin(); inputItr != v.end(); ++inputItr) {
        // *inputItr = 4;
        cout << *inputItr << endl;
    }

    return 0;
}

// Output
100
200
300
400
500

3. Forward Iterator (read/write, forward moving)

A forward iterator is a type of iterator that allows traversal through a container in a forward direction, from the beginning to the end. It supports sequential access to elements, allowing both reading and writing operations. Unlike input iterators, forward iterators permits multiple passes through the container. However, they do not support backward traversal or random access to elements, distinguishing them from the bidirectional and random access iterators.

Characteristics of Forward Iterators:

1. Forward Movement: Forward Iterators facilitate movement in a single direction – forward. They enable sequential access to elements in a container, starting from the beginning and progressing towards the end.
2. Multiple Passes: Unlike input iterators, forward iterators allow for multiple passes through the container. This means that you can iterate over the elements more than once, accessing or modifying them as needed.

Example:

#include <iostream>
#include <list>

int main() {
    std::list<int> numbers = {1, 2, 3, 4, 5};

    // Using a forward iterator to traverse the list
    std::list<int>::iterator it;
    for (it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

4. Bidirectional Iterator (read/write, forward/backward moving)

A bidirectional iterator is a type of iterator that allows traversal in both forward and backward directions through a container. It is an extension of the forward iterator, providing additional functionality for moving backwards. Bidirectional iterator support increment and decrement operations, enabling efficient navigation through the elements of a container in both directions.

5. Random Access Iterator (read/write, forward/backward, random access)

This iterator have all the properties of bidirectional iterators along with random access.

Some Commonly used operators for random access iterators are:

• ++ = iterate forward
• -- = iterate backward
• * or [] = read and write values
• -> = access member values
• + = iterate forward by desired number of steps
• - = iterate backward by desired number of steps

Input Iterator:

• Access = Uses -> to access member function/variables of the pointed-to element.
• Read = Dereferences the iterator using *i to read the value of the pointed-to element.
• Iterate = Increments the iterator using ++ to move to the next element.

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();
int value = *it; // Reads the value of the first element
++it;            // Moves to the next element

Output Iterator:

• Write = Assings a value to the pointed-to element using *i=.
• Iterate = Increments the iterator using ++ to move to the next element.

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();
*it = 10; // Writes the value 10 to the first element
++it;     // Moves to the next element

Iterator Functions

1. begin() and end():

• begin() = Returns an iterator pointing to the first element of the container.
• end() = Returns an iterator pointing to the position past the last element of the container.

std::vector<int> numbers = {1, 2, 3, 4, 5};
auto it_begin = numbers.begin(); // Iterator pointing to the first element
auto it_end = numbers.end();     // Iterator pointing to the position past the last element

2. advance():

• advance(iterator, n) = Advances the iterator by n positions.

std::list<int> numbers = {1, 2, 3, 4, 5};
auto it = numbers.begin();
std::advance(it, 2); // Advances the iterator by 2 positions

3. next() and prev():

• next(iterator, n) = Returns an iterator pointing to the element n positions ahead of the given iterator.
• prev(iterator, n) = Returns an iterator pointing to the element n positions before the given iterator.

std::list<int> numbers = {1, 2, 3, 4, 5};
auto it = numbers.begin();
auto next_it = std::next(it, 2); // Iterator pointing to the element 2 positions ahead
auto prev_it = std::prev(it, 1); // Iterator pointing to the element 1 position before

4. distance():

• distance(first, last) = Returns the number of elements between two iterators.

std::vector<int> numbers = {1, 2, 3, 4, 5};
auto distance = std::distance(numbers.begin(), numbers.end()); // distance = 5

5. insert():

• insert(iterator, value) = Inserts a value before the iterator position and returns an iterator pointing to the inserted element.

std::vector<int> numbers = {1, 2, 4, 5};
auto it = std::find(numbers.begin(), numbers.end(), 2);
numbers.insert(it, 3); // Inserts 3 before the element 2

6. erase()

• erase(iterator) = Removes the element at the iterator position and returns an iterator pointing to the next element.

std::vector<int> numbers = {1, 2, 3, 4, 5};
auto it = std::find(numbers.begin(), numbers.end(), 3);
numbers.erase(it); // Removes element 3