STL Iterators

The Standard Template Library (STL) in C++ provides powerful tools for efficient programming. One of its key components is Iterators. Iterators act as a bridge between containers (like vectors, lists, and maps) and algorithms in the STL. They allow traversal, manipulation, and access of container elements without worrying about the underlying data structure.

This chapter covers STL Iterators in detail, from basic concepts to advanced usage, with in-depth explanations, real-world examples, and outputs. By the end of this chapter, you will have a comprehensive understanding of iterators and how to use them effectively.

What is an Iterator?

An iterator is an object that points to an element in a container. It behaves like a pointer and allows you to traverse through the container’s elements sequentially. Iterators abstract away the complexity of accessing elements from different types of containers.

Key Features of Iterators

  1. Access elements in containers (like vector, list, map, etc.).
  2. Provide a uniform way to traverse containers.
  3. Enable use of STL algorithms (e.g., find, sort, copy, etc.).
  4. They make the code generic (independent of the container type).

Why Use Iterators?

  • Container Independence: You don’t need to know the internal structure of a container (array, linked list, etc.).
  • Cleaner Code: Simplifies traversal and element access.
  • Integration with STL Algorithms: STL algorithms work seamlessly with iterators.
  • Flexibility: Allows manipulation of containers efficiently.

Types of Iterators in STL

Iterators in C++ can be divided into several types based on their behavior and functionality.

Iterator TypeDescriptionExamples
Input IteratorRead-only access; one-way traversal.Reading data from input streams.
Output IteratorWrite-only access; one-way traversal.Writing data to output streams.
Forward IteratorRead/write access; can move forward.forward_list or basic containers.
Bidirectional IteratorRead/write access; can move forward and backward.list, map, set.
Random Access IteratorRead/write access; can move freely (forward/backward) and jump to positions.vector, array, deque.

Iterator Categories and Examples

Let’s take a closer look at each iterator type with real examples.

Input Iterator

An Input Iterator allows you to read values sequentially from a container.

Example:

				
					#include <iostream>
#include <vector>
#include <iterator> // Required for iterator

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

    // Create an input iterator
    std::vector<int>::iterator it;

    std::cout << "Using Input Iterator to print values: ";
    for (it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " "; // Dereference iterator to get value
    }
    return 0;
}

				
			
				
					// Output
Using Input Iterator to print values: 1 2 3 4 5

Output Iterator

An Output Iterator is used for writing values sequentially.

Example:

				
					#include <iostream>
#include <vector>
#include <iterator> // For ostream_iterator
#include <algorithm> // For copy()

int main() {
    std::vector<int> numbers = {10, 20, 30, 40, 50};

    std::cout << "Using Output Iterator: ";
    std::copy(numbers.begin(), numbers.end(), std::ostream_iterator<int>(std::cout, " "));
    return 0;
}

				
			
				
					// Output
Using Output Iterator: 10 20 30 40 50

Forward Iterator

A Forward Iterator allows forward traversal with both reading and writing.

Example:

				
					#include <iostream>
#include <forward_list>

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

    std::cout << "Using Forward Iterator: ";
    for (auto it = fl.begin(); it != fl.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

				
			
				
					// Output
Using Forward Iterator: 1 2 3 4 5

Bidirectional Iterator

A Bidirectional Iterator allows both forward and backward traversal.

Example:

				
					#include <iostream>
#include <list>

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

    std::cout << "Using Bidirectional Iterator: ";
    for (auto it = numbers.rbegin(); it != numbers.rend(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

				
			
				
					// Output
Using Bidirectional Iterator: 5 4 3 2 1

Random Access Iterator

A Random Access Iterator supports free movement, forward, backward, and indexed access.

Example:

				
					#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};

    std::cout << "Using Random Access Iterator: ";
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " "; // Random access using indexing
    }

    return 0;
}

				
			
				
					// Output
Using Random Access Iterator: 10 20 30 40 50

Iterator Functions

C++ provides several built-in iterator functions:

FunctionDescription
begin()Returns an iterator pointing to the start.
end()Returns an iterator pointing after the last element.
rbegin()Returns a reverse iterator to the last element.
rend()Returns a reverse iterator before the first element.

Advanced Topics in Iterators

In this section, we will explore advanced concepts related to iterators in C++. These topics help developers use iterators more effectively for complex scenarios, ensuring flexibility, efficiency, and maintainability in their programs.

Const Iterators

What is a Const Iterator?

A const iterator is an iterator that provides read-only access to elements of a container. It ensures that you cannot modify the values of the container elements while iterating over them.

Using const iterators is essential when you want to enforce immutability and make it clear that the container’s elements must not be changed.

Why Use Const Iterators?

  • Prevent accidental modification of container elements.
  • Improve code safety.
  • Provide clarity and intent in the code.

How to Use Const Iterators

To declare a const iterator:

  • Use cbegin() and cend() to get const iterators.
  • Use const_iterator explicitly.

Example: Const Iterators

				
					#include <iostream>
#include <vector>

int main() {
    const std::vector<int> numbers = {10, 20, 30, 40, 50};

    // Using const_iterator to iterate over the vector
    std::cout << "Using const iterators: ";
    for (std::vector<int>::const_iterator it = numbers.cbegin(); it != numbers.cend(); ++it) {
        std::cout << *it << " "; // Read-only access
    }

    // Uncommenting the below line will cause an error
    // *it = 100; // Error: cannot modify elements through const_iterator

    return 0;
}

				
			
				
					// Output
Using const iterators: 10 20 30 40 50

Explanation:

  1. cbegin() and cend() return const iterators.
  2. Attempting to modify the elements (e.g., *it = 100) will result in a compile-time error.

Reverse Iterators

What is a Reverse Iterator?

A reverse iterator allows you to traverse a container backward, starting from the last element and moving towards the first.

Reverse iterators are particularly useful when:

  • You need to display elements in reverse order.
  • You are working with algorithms that require backward traversal.

How to Use Reverse Iterators

C++ provides rbegin() and rend() to create reverse iterators:

  • rbegin(): Points to the last element of the container.
  • rend(): Points before the first element of the container.

Example: Reverse Iterators

				
					#include <iostream>
#include <vector>

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

    // Using reverse iterators to print elements in reverse
    std::cout << "Using reverse iterators: ";
    for (std::vector<int>::reverse_iterator it = numbers.rbegin(); it != numbers.rend(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

				
			
				
					// Output
Using reverse iterators: 5 4 3 2 1

Explanation:

  1. rbegin() points to the last element of the container (5).
  2. rend() marks the position before the first element.

Move Iterators

What is a Move Iterator?

A move iterator enables “move semantics” when iterating over a container. Instead of copying elements during operations, move iterators transfer ownership of the resources.

This can significantly improve performance for containers holding large objects or objects that are expensive to copy.

Why Use Move Iterators?

  • To avoid deep copying when transferring data.
  • Improve performance in scenarios involving large objects or objects with dynamic memory.

How to Use Move Iterators

Move iterators can be created using std::make_move_iterator.

Example: Move Iterators

				
					#include <iostream>
#include <vector>
#include <algorithm> // For copy

int main() {
    std::vector<std::string> source = {"one", "two", "three"};
    std::vector<std::string> destination;

    // Move elements from source to destination using move iterators
    std::move(source.begin(), source.end(), std::back_inserter(destination));

    // Print the destination vector
    std::cout << "Destination vector: ";
    for (const auto& str : destination) {
        std::cout << str << " ";
    }

    // Print the source vector after move
    std::cout << "\nSource vector after move: ";
    for (const auto& str : source) {
        std::cout << str << " "; // Elements in source are now empty
    }

    return 0;
}

				
			
				
					// Output
Destination vector: one two three 
Source vector after move:

Explanation:

  1. std::move transfers ownership of the strings from the source vector to the destination vector.
  2. The source vector’s strings become empty because their resources have been moved.

Stream Iterators

What are Stream Iterators?

Stream iterators connect STL containers with input/output streams. They allow reading from or writing to streams like cin, cout, or files.

Types of Stream Iterators

  1. Input Stream Iterator: Reads data from input streams.
  2. Output Stream Iterator: Writes data to output streams.

Example: Input Stream Iterator

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

int main() {
    std::vector<int> numbers;

    std::cout << "Enter 5 integers: ";
    std::copy_n(std::istream_iterator<int>(std::cin), 5, std::back_inserter(numbers));

    std::cout << "You entered: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }

    return 0;
}

				
			
				
					// Input
10 20 30 40 50


				
			
				
					// Output
You entered: 10 20 30 40 50

Explanation:

  1. std::move transfers ownership of the strings from the source vector to the destination vector.
  2. The source vector’s strings become empty because their resources have been moved.

Example: Output Stream Iterator

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

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

    std::cout << "Output Stream Iterator: ";
    std::copy(numbers.begin(), numbers.end(), std::ostream_iterator<int>(std::cout, " "));

    return 0;
}

				
			
				
					// Output
Output Stream Iterator: 1 2 3 4 5

Custom Iterators

Custom iterators allow you to define your own iterator for custom data structures. While the C++ Standard Template Library (STL) provides built-in iterators for its containers (like vector, list, etc.), custom iterators become essential when you need to iterate through non-standard data structures or implement a special type of traversal logic.

Why Use Custom Iterators?

Custom iterators are needed when:

  1. You are working with non-STL containers, like custom linked lists, trees, or graphs.
  2. You need to control the traversal logic of your data structure.
  3. You want your custom container to be compatible with STL algorithms (which require iterators).

For example, if you create a custom linked list, you need an iterator to traverse through it, just like you use iterators with std::vector or std::list.

Building Blocks of Custom Iterators

To create a custom iterator, you must implement the following components:

  1. Dereference operator (*): Returns the current element.
  2. Increment operator (++): Moves the iterator to the next element.
  3. Equality and inequality operators (==, !=): Checks if two iterators are equal or not.
  4. Iterator traits (optional but recommended): Provides meta-information about the iterator (like its category).

Additionally, iterators are often implemented as classes that encapsulate these functionalities.

Steps to Create a Custom Iterator

Let’s go step-by-step to understand the creation of a custom iterator.

Step 1: Define a Custom Data Structure

Here, we will create a simple dynamic array class that requires a custom iterator.

				
					#include <iostream>
#include <cstddef> // For std::size_t

class MyArray {
private:
    int* data;     // Pointer to dynamically allocated array
    std::size_t size;

public:
    MyArray(std::size_t s) : size(s) {
        data = new int[size]; // Allocate memory
        for (std::size_t i = 0; i < size; ++i) {
            data[i] = i + 1;  // Initialize array elements
        }
    }

    ~MyArray() {
        delete[] data; // Free allocated memory
    }

    int& operator[](std::size_t index) {
        return data[index]; // Allow access to elements
    }

    std::size_t getSize() const { return size; }

    // Forward declaration of custom iterator
    class Iterator;

    // Function to return an iterator pointing to the start of the array
    Iterator begin();

    // Function to return an iterator pointing to the end of the array
    Iterator end();
};

Step 2: Define the Custom Iterator Class

Now, let’s define the Iterator class within MyArray. It will contain all the required functionalities like dereferencing, incrementing, and comparison.

				
					class MyArray::Iterator {
private:
    int* ptr; // Pointer to the current element

public:
    // Constructor: Takes a pointer to initialize
    Iterator(int* p) : ptr(p) {}

    // Dereference operator: Returns the current element
    int& operator*() { 
        return *ptr; 
    }

    // Increment operator: Move to the next element
    Iterator& operator++() {
        ++ptr;
        return *this;
    }

    // Equality operator: Check if two iterators are equal
    bool operator==(const Iterator& other) const {
        return ptr == other.ptr;
    }

    // Inequality operator: Check if two iterators are not equal
    bool operator!=(const Iterator& other) const {
        return !(*this == other);
    }
};

Step 3: Implement begin() and end() Functions

Now we define begin() and end() in the MyArray class. These functions return the custom iterator pointing to the start and end of the array.

				
					MyArray::Iterator MyArray::begin() {
    return Iterator(data); // Start of the array
}

MyArray::Iterator MyArray::end() {
    return Iterator(data + size); // Past the last element
}

Step 4: Use the Custom Iterator

Now that we have defined the custom iterator and its functionalities, we can use it in a range-based for loop or with STL algorithms.

				
					int main() {
    MyArray arr(5); // Create a MyArray object of size 5

    std::cout << "Using Custom Iterator to traverse MyArray:\n";
    for (MyArray::Iterator it = arr.begin(); it != arr.end(); ++it) {
        std::cout << *it << " "; // Use the custom iterator
    }
    std::cout << "\n";

    return 0;
}

Output

				
					Using Custom Iterator to traverse MyArray:
1 2 3 4 5

Explanation

  1. Custom Data Structure: MyArray is a simple dynamic array class that holds integers.
  2. Iterator Class:
    • operator*() provides access to the current element.
    • operator++() moves to the next element.
    • operator==() and operator!=() compare iterators.
  3. begin() and end(): These functions return iterators pointing to the start and end of the array.
  4. Traversal: The for loop uses the custom iterator to traverse the MyArray elements.

Advanced iterators like const iterators, reverse iterators, move iterators, and stream iterators extend the flexibility and power of the STL. They allow developers to perform efficient, clean, and high-performance operations on containers, streams, and custom data structures. Happy coding !❤️

Table of Contents

Home
Roadmap
ATS Resume
Playground
Resources