Home C++ C++ Bidirectional Iterators tutorial with code examples
C++Tutorials

C++ Bidirectional Iterators tutorial with code examples

In C++, Bidirectional Iterators are a type of iterator that can move in both directions: forward and backward.

They offer more flexibility than forward iterators and are commonly used in containers like std::list, std::set, and std::map.

Bidirectional iterators allow for operations that require both forward and backward traversal, such as reversing a container.

Characteristics of Bidirectional Iterators

  1. Bidirectional traversal: Can move both forward (++) and backward (–).
  2. Multi-pass: Can iterate over the same sequence multiple times.
  3. Readable and writable: Can read from and write to elements.
  4. Equality comparison: Can be compared for equality or inequality.

1. Basic Example of Bidirectional Iterator with std::list

The std::list container uses bidirectional iterators, allowing both forward and backward traversal.

#include <iostream>
#include <list>
using namespace std;

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

    cout << "Forward traversal: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        cout << *it << " ";
    }

    cout << "\nBackward traversal: ";
    for (auto it = numbers.rbegin(); it != numbers.rend(); ++it) {
        cout << *it << " ";
    }

    return 0;
}

Explanation:

  • numbers.begin() and numbers.end() provide a forward iterator.
  • numbers.rbegin() and numbers.rend() provide a reverse iterator, enabling backward traversal.

Output:

Forward traversal: 1 2 3 4 5
Backward traversal: 5 4 3 2 1

2. Moving Backward with Bidirectional Iterator

Bidirectional iterators allow moving both forward and backward within the container.

#include <iostream>
#include <list>
using namespace std;

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

    auto it = numbers.end(); // Start at the end
    --it; // Move to the last element

    cout << "Elements in reverse order: ";
    while (it != numbers.begin()) {
        cout << *it << " ";
        --it;
    }
    cout << *it; // Print the first element

    return 0;
}

Explanation:

  • –it moves the iterator backward through the list, allowing for reverse traversal starting from the last element.

Output:

Elements in reverse order: 50 40 30 20 10

3. Modifying Elements with Bidirectional Iterators

Bidirectional iterators allow modifying elements in the container.

#include <iostream>
#include <list>
using namespace std;

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

    // Double each element using bidirectional iterator
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        *it *= 2;
    }

    cout << "Modified elements: ";
    for (int number : numbers) {
        cout << number << " ";
    }

    return 0;
}

Explanation:

  • *it *= 2; modifies each element in numbers by doubling its value.

Output:

Modified elements: 2 4 6 8 10

4. Using std::reverse with Bidirectional Iterators

The std::reverse algorithm can use bidirectional iterators to reverse the order of elements in a container.

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

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

    // Reverse the list
    reverse(numbers.begin(), numbers.end());

    cout << "Reversed list: ";
    for (int number : numbers) {
        cout << number << " ";
    }

    return 0;
}

Explanation:

  • reverse(numbers.begin(), numbers.end()); reverses the order of elements in numbers.

Output:

Reversed list: 5 4 3 2 1

5. Finding Elements with std::find and Bidirectional Iterators

Bidirectional iterators allow you to search for an element using std::find.

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

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

    auto it = find(numbers.begin(), numbers.end(), 30);

    if (it != numbers.end()) {
        cout << "Element 30 found!" << endl;
    } else {
        cout << "Element not found!" << endl;
    }

    return 0;
}

Explanation:

  • find(numbers.begin(), numbers.end(), 30); searches for 30 in numbers using bidirectional iterators.

Output:

Element 30 found!

6. Using Bidirectional Iterators with std::set

std::set uses bidirectional iterators, allowing you to iterate over the elements in sorted order.

#include <iostream>
#include <set>
using namespace std;

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

    cout << "Set elements in ascending order: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        cout << *it << " ";
    }

    cout << "\nSet elements in descending order: ";
    for (auto it = numbers.rbegin(); it != numbers.rend(); ++it) {
        cout << *it << " ";
    }

    return 0;
}

Explanation:

  • numbers.begin() and numbers.end() iterate in ascending order.
  • numbers.rbegin() and numbers.rend() iterate in descending order.

Output:

Set elements in ascending order: 10 20 30 40 50
Set elements in descending order: 50 40 30 20 10

7. Using std::map with Bidirectional Iterators

std::map also uses bidirectional iterators, allowing you to traverse key-value pairs.

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, string> students = {{1, "Alice"}, {2, "Bob"}, {3, "Charlie"}};

    cout << "Students (ID: Name): ";
    for (auto it = students.begin(); it != students.end(); ++it) {
        cout << it->first << ": " << it->second << ", ";
    }

    cout << "\nReverse order (ID: Name): ";
    for (auto it = students.rbegin(); it != students.rend(); ++it) {
        cout << it->first << ": " << it->second << ", ";
    }

    return 0;
}

Explanation:

  • students.begin() and students.end() iterate over the key-value pairs in ascending order.
  • students.rbegin() and students.rend() iterate in descending order.

Output:

Students (ID: Name): 1: Alice, 2: Bob, 3: Charlie, 
Reverse order (ID: Name): 3: Charlie, 2: Bob, 1: Alice,

8. Removing Elements with std::remove_if and Bidirectional Iterators

You can use std::remove_if with bidirectional iterators to remove elements based on a condition.

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

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

    // Remove even numbers
    numbers.remove_if([](int n) { return n % 2 == 0; });

    cout << "List after removing even numbers: ";
    for (int number : numbers) {
        cout << number << " ";
    }

    return 0;
}

Explanation:

  • remove_if removes all even numbers from numbers using a lambda function as the condition.

Output:

List after removing even numbers: 1 3 5

9. Counting Elements with std::count and Bidirectional Iterators

You can use std::count to count occurrences of an element in a container with bidirectional iterators.

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

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

    int count_2 = count(numbers.begin(), numbers.end(), 2);

    cout << "Number of times 2 appears: " << count_2 << endl;

    return 0;
}

Explanation:

  • count(numbers.begin(), numbers.end(), 2); counts the occurrences of 2 using bidirectional iterators.

Output:

Number of times 2 appears: 3

10. Resetting a Bidirectional Iterator for Multiple Passes

Bidirectional

iterators can be reassigned to begin() to make multiple passes over the container.

#include <iostream>
#include <list>
using namespace std;

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

    cout << "First pass: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        cout << *it << " ";
    }

    cout << "\nSecond pass: ";
    auto it = numbers.begin();
    while (it != numbers.end()) {
        cout << *it << " ";
        ++it;
    }

    return 0;
}

Explanation:

  • The iterator it is reset to begin() for a second traversal.

Output:

First pass: 1 2 3 4 5
Second pass: 1 2 3 4 5

Summary Table of Bidirectional Iterator Usage

Example Description
Basic List Traversal Uses bidirectional iterator for forward and backward traversal
Moving Backward with — Moves bidirectional iterator backward
Modifying Elements Modifies container elements using bidirectional iterators
Reversing Container Reverses container order with std::reverse
Finding Elements Finds specific element with std::find
Traversing std::set Iterates over elements in sorted order (ascending and descending)
Traversing std::map Iterates over key-value pairs in both orders
Removing Elements Removes elements based on condition with remove_if
Counting Occurrences Counts occurrences of a specific element
Multiple Passes Resets iterator for multiple traversals

Key Takeaways

  • Bidirectional Iterators enable traversal in both forward and backward directions.
  • They are multi-pass iterators, allowing for multiple traversals over the same container.
  • Containers like std::list, std::set, and std::map use bidirectional iterators, making them suitable for both sequential and reverse access.
  • Bidirectional iterators work with a wide range of algorithms, including std::reverse, std::find, std::remove_if, and std::count, making them versatile and powerful tools in the C++ STL.

You may also like

Tutorial: Function Call by Reference in C Programming

Tutorial: Function Call by Value in C Programming

Tutorial on Working with Pipes in Go

Tutorial on Working with Pointers in Go

Tutorial on Working with Modules in Go

Tutorial on Generating Random Values in Go

Tutorial on Handling Errors in Go

Tutorial on defer Statement in Go

Tutorial on Working with Directories in Go

Tutorial on the filepath Package in Go