Iterators

1. Introduction

Iterators play a pivotal role in C++, bridging the gap between containers and algorithms. Given their varying capabilities, iterators can be grouped into distinct categories.

1.1 Categories of Iterators

From the broadest capabilities to the most specific, iterators can be classified into five major categories:

  • Random Access: The most versatile of all, supporting operations like direct element access, increments by more than one step, and decrements.

  • Bidirectional: Offers functionalities of forward iterators and additionally supports reverse navigation through elements.

  • Forward: A blend of both input and output iterators, allowing linear traversal through elements in one direction.

  • Input: Solely designed for reading purposes, it facilitates single-step forward movement and element dereferencing.

  • Output: Contrary to input iterators, this type is primarily for writing data, also allowing a single-step forward movement.

Often, the choice is determined by the algorithm or container you're working with. However, when flexibility is at your disposal, it's advisable to opt for the least powerful iterator that fulfills your needs. Such a practice ensures that your code remains versatile and adaptable to various contexts.

1.2 A Note on Constancy:

Irrespective of the category, there's another pivotal aspect of iterators: constancy. The idea is simple but critical. Whenever you're iterating through elements without the intention of altering them, using a constant iterator is a prudent choice. Not only does it bolster safety by preventing unintentional modifications but can also potentially boost performance.

Constant iterators are not categorized based on their constancy but by the aforementioned categories. So, you might encounter terms like const_forward_iterator or const_random_access_iterator.

1.3 Practical Implications:

Each iterator type has its own realm of applicability. Take the input_iterator as an example. It's the exclusive choice when dealing with console input because this input stream can't support operations like backward navigation or random jumps.

When designing algorithms, staying generic and inclusive is the key. By unnecessarily relying on capabilities of a powerful iterator, you might unintentionally limit the contexts in which your algorithm operates. For instance, if an algorithm can function with just forward_iterator, but you inadvertently use features specific to random_access_iterator, you exclude containers like lists from your algorithm's purview.

2. Iterator Types

The C++ standard library defines iterator categories, which are used to express the capabilities of iterators. These categories are represented by tags like std::input_iterator_tag, std::output_iterator_tag, etc. However, the actual iterator types provided by containers don't typically have these names! Instead, they have names that are meaningful in the context of their respective containers. Recognizing the category or capabilities of a container's iterators often requires some knowledge of the container's properties and behaviors.

We can draw the heirarchy of iterator types as follows:

(most powerful)
Random Access
    |
Bidirectional
    |
Forward
    |
Input - Output
(most specific)

2.1 Input Iterators

Definition: Input iterators provide read-only access to elements in a sequence and can only move forward. They're designed for single-pass algorithms, meaning they only access data once.

Example:

Suppose you want to read values from a file into a container. istream_iterator (from the C++ Standard Library) would be perfect for this:

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

int main() {
    std::istream_iterator<int> start(std::cin), end;
    std::vector<int> numbers(start, end);
}

The code reads integers from standard input into a vector.

2.3 Output Iterators

Definition: Output iterators provide write-only access to elements. They also only move forward but have a twist; instead of dereferencing to read a value, you dereference them to write a value.

Example:

Consider you want to append values to a list. back_insert_iterator can be used:

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

int main() {
    std::list<int> myList;
    auto inserter = std::back_inserter(myList);

    *inserter = 5;  // Appends 5 to myList
    *inserter = 10; // Appends 10 to myList
}

With output iterators, remember there's no concept of "end", and they increment automatically every time a value is set.

Now, onto more advanced iterator types:

2.4 Forward Iterators

Definition: A forward iterator combines features of both input and output iterators. They can read, write, and move forward through a sequence. Crucially, they support multi-pass algorithms.

Example:

A simple use of forward iterators would be iterating through a linked list:

#include <list>
#include <iostream>

int main() {
    std::list<int> numbers = {1, 2, 3, 4};
    for(auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
}

This prints "1 2 3 4".

2.5 Bidirectional Iterators

Definition: As the name suggests, these iterators can move both forwards and backwards in a sequence. They inherit all the capabilities of forward iterators.

Example:

#include <list>
#include <iostream>

int main() {
    std::list<int> numbers = {1, 2, 3, 4};
    auto it = numbers.end();
    while(it != numbers.begin()) {
        --it;
        std::cout << *it << " ";
    }
}

This code prints "4 3 2 1".

2.6 Random-Access Iterators

Definition: These iterators provide the most flexibility. They allow for constant-time access to any element in a sequence. As with pointers in an array, you can perform arithmetic on them.

Example:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};
    auto it = vec.begin() + 2;
    std::cout << *it << std::endl; // Prints 30
}

The key point with random-access iterators is their pointer-like behavior, supporting operations like addition or subtraction of an integer offset.

2.7 Reverse Iterators

Definition: These iterators reverse the direction of iteration. They wrap around bidirectional or random-access iterators, converting increment operations into decrements and vice versa.

Example:

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    for(auto it = vec.rbegin(); it != vec.rend(); ++it) {
        std::cout << *it << " ";
    }
}

This code prints "5 4 3 2 1".

2.8 Summary

Iterator Type Movement Direction Read Write Const Version Available Associated Containers
Input Iterator Forward only ✓ ✓ istream, istringstream
Output Iterator Forward only ✓ ostream, ostringstream
Forward Iterator Forward only ✓ ✓ ✓ forward_list, list
Bidirectional Forward & Backward ✓ ✓ ✓ list, set, multiset, map, multimap, deque
Random Access Any direction ✓ ✓ ✓ vector, array, deque, string
  • It might be confusing to see that list appear in both the forward and the bidirectional iterator categories. This is because list iterators are bidirectional iterators, but they are also forward iterators. All bidirectional iterators are forward iterators, but not all forward iterators are bidirectional iterators.

3. Common Iterator Operations

Iterators abstract the process of navigating through and accessing elements within containers. Different types of iterators provide different levels of functionality. This section will highlight some of the most common operations that you can perform with iterators.

3.1 Increment (++iter)

Incrementing an iterator moves it to the next element in a container.

Example:

std::vector<int> vec = {1, 2, 3, 4};
std::vector<int>::iterator it = vec.begin();
++it;  // now it points to the second element (2)

Note: Almost all iterator types support this operation except when they reach the end() of the container.

3.2 Decrement (--iter)

Decrementing an iterator moves it to the previous element in the container. This is only supported by bidirectional and random-access iterators.

Example:

std::list<std::string> names = {"Alice", "Bob", "Charlie"};
std::list<std::string>::iterator it = std::next(names.begin(), 2); // pointing to "Charlie"
--it;  // now it points to "Bob"

3.3 Dereferencing (*iter)

Dereferencing an iterator gives access to the element it's currently pointing to. It's like accessing an element via a pointer.

Example:

std::vector<int> numbers = {10, 20, 30};
std::vector<int>::iterator it = numbers.begin();
int val = *it;  // val is now 10

Note: For output iterators, dereferencing typically returns the iterator itself, allowing for assignments but not value retrieval.

3.4 Arrow (iter->member)

The arrow operator allows direct access to the member of an element (like using a pointer). This is useful for iterators pointing to objects or structures.

Example:

struct Person {
    std::string name;
    int age;
};

std::vector<Person> people = { {"John", 30}, {"Doe", 25} };
std::vector<Person>::iterator it = people.begin();
std::string name = it->name;  // name is "John"

3.5 Comparison (iter1 == iter2, iter1 != iter2)

Iterators can be compared to each other to see if they're pointing to the same position within a container. This is especially useful in loop conditions.

Example:

std::vector<int> nums = {5, 6, 7, 8, 9};
for(std::vector<int>::iterator start = nums.begin(), end = nums.end(); start != end; ++start) {
    std::cout << *start << std::endl;  // prints all numbers in the vector
}

Note: While equality and inequality comparisons are generally supported by all iterator types, other comparison operations like <, <=, > and >= are specifically available for random-access iterators.

4. Iterator Adapters

Iterator adapters modify the behavior of existing iterators, allowing them to be used in alternative or more specialized ways. Two common iterator adapters are reverse iterators and move iterators.

4.1 Reverse Iterators

Introduction to std::reverse_iterator

The std::reverse_iterator is a type of iterator adapter that moves in the opposite direction of the underlying iterator. For example, when incrementing a reverse_iterator, you'll actually be moving backwards in the container.

When and how to use them

Reverse iterators are useful when you want to traverse a container in reverse without modifying the container itself.

Example:

std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int>::reverse_iterator rit = vec.rbegin();  // Start from the end

for (; rit != vec.rend(); ++rit) {
    std::cout << *rit << " ";  // Prints: 5 4 3 2 1
}
std::cout << std::endl;

Remember, rbegin() gives you a reverse iterator to the last element and rend() points to one before the first element.

4.2 Move Iterators

Introduction to std::move_iterator

The std::move_iterator is an iterator adapter that, when dereferenced, produces an rvalue reference to its underlying iterator's value. This means elements can be "moved" from a container, transferring ownership rather than copying the value.

Use cases, especially with algorithms like std::move

Move iterators are particularly useful when transferring ownership of resources, such as when moving elements from one container to another.

Example:

std::vector<std::unique_ptr<int>> src;
src.push_back(std::make_unique<int>(10));
src.push_back(std::make_unique<int>(20));
src.push_back(std::make_unique<int>(30));

std::vector<std::unique_ptr<int>> dest;

std::move(src.begin(), src.end(), std::back_inserter(dest));

// At this point, the elements have been "moved" from src to dest. 
// src's unique_ptrs are now null, and dest has taken ownership of the resources.

for (const auto& ptr : dest) {
    std::cout << *ptr << " ";  // Prints: 10 20 30
}
std::cout << std::endl;

In the above example, we're using std::move along with move iterators to transfer ownership of std::unique_ptr elements from src to dest. After the move, the original container (src) is left with null pointers, while the destination container (dest) owns the values.

5. Common Mistakes and Pitfalls

Navigating the world of iterators in C++ can be tricky. Here are some common pitfalls and mistakes developers often make when working with iterators, along with examples of each:

5.1 Dangling Iterators

Pitfall: An iterator that continues to be used after the container it points into has been modified in such a way that the iterator is no longer valid is referred to as a "dangling iterator."

Example:

std::vector<int> vec = {10, 20, 30};
std::vector<int>::iterator it = vec.begin();
vec.clear();
// it is now a dangling iterator
std::cout << *it;  // Undefined behavior!

In the example above, after clearing the vector, it is left dangling. Accessing the value through a dangling iterator is undefined behavior, and can lead to program crashes, unexpected results, or other issues.

5.2 Comparing Iterators from Different Containers

Pitfall: Iterators should never be compared if they originate from different containers. Doing so results in undefined behavior.

Example:

std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2 = {4, 5, 6};

auto it1 = vec1.begin();
auto it2 = vec2.begin();

if (it1 == it2) {  // Comparing iterators from different containers
    std::cout << "The iterators are equal";  // Undefined behavior!
}

In the example, comparing it1 and it2 is undefined because they belong to different containers.

5.3 Modifying the Container While Iterating Over It

Pitfall: Modifying a container (like adding or removing elements) while iterating over it can invalidate the iterator, potentially leading to undefined behavior.

Example:

std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it == 3) {
        vec.erase(it);  // Modifying the container during iteration
    }
}

In the example above, erasing an element from the vector during iteration invalidates the iterator. The subsequent call to ++it in the loop will lead to undefined behavior. A safer approach might involve marking elements for deletion and erasing them after the iteration completes, or using the erase-remove idiom.

6. Best Practices

Working with iterators in C++ can be straightforward and efficient when you adopt best practices. Here are some guidelines and examples that can help enhance your iterator usage:

6.1 When to use auto vs Explicitly Specifying the Iterator Type

Best Practice: The auto keyword can be useful to simplify code and avoid verbosity, but sometimes explicitly specifying the iterator type can enhance clarity.

Examples:

  • Using auto for simplicity:
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    // do something
}

In this example, auto neatly infers the iterator type without requiring the programmer to specify it.

  • Explicitly specifying for clarity:
std::list<double> myList = {1.1, 2.2, 3.3};
std::list<double>::iterator it = myList.begin();

Here, by explicitly mentioning the iterator type, the code clearly communicates its intentions.

6.2 Using cbegin() and cend() for Constant Iterators

Best Practice: When you don't intend to modify the elements you're iterating over, prefer using cbegin() and cend(). They return constant iterators, enforcing read-only access to the elements.

Example:

std::vector<int> vec = {10, 20, 30, 40};
for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
    std::cout << *it << " ";  // OK: Reading the value
    //*it = 5;                 // Error: Trying to modify through a constant iterator
}

6.3 Iterating with Range-Based For Loops

Best Practice: For simple iterations where you don't need direct access to the iterator itself (like modifying the container during iteration), prefer range-based for loops. They offer a concise and clear way to iterate over containers.

Example:

std::vector<std::string> names = {"Alice", "Bob", "Charlie"};
for (const auto& name : names) {
    std::cout << name << " ";
}

In this example, a range-based for loop is used to iterate over a vector of strings. It's concise and easy to read. The const auto& ensures each string is accessed by reference without modifying it.