Iterators provide a mechanism to access elements within containers like std::vector and characters within std::string. While std::vector and std::string offer common functionalities, only std::vector supports direct index access. Most standard library containers leverage iterators for element traversal.

Iterators function similarly to pointers, offering indirect access to objects and the ability to move between elements. Valid iterators point to an element or the position immediately after the last element. Any other state renders an iterator invalid.

Accessing Iterators

Instead of using the address-of operator, iterators are obtained via member functions named begin() and end() offered by supporting types.

• begin() returns an iterator pointing to the first element.
• end() returns an iterator that points to the position after the last element, often referred to as the end iterator. This iterator serves as a marker and does not dereference to an actual element. If a container is empty, begin() and end() return the same iterator.

// For a vector 'v', 'b' points to the first element, and 'e' points past the last.
auto b = v.begin(), e = v.end(); // 'b' and 'e' are of the same iterator type

The exact type of an iterator is usually not a concern for general usage.

Iterator Operations

Standard container iterators support the following operations:

• *iter: Dereferences the iterator to access the element it points to.
• iter->member: Dereferences the iterator and accesses a member of the pointed-to object (equivalent to (*iter).member).
• ++iter: Advances the iterator to the next element.
• --iter: Moves the iterator back to the previous element.
• iter1 == iter2 and iter1 != iter2: Compares two iterators for equality. They are equal if they point to the same element or if both are end iterators of the same container.

Dereferencing an iterator requires it to be valid and point to an actual element. Attempting to dereference an invalid or end iterator results in undefined behavior.

// Check if the string 's' is not empty before accessing its first character.
if (s.begin() != s.end()) {
    auto it = s.begin(); // 'it' points to the first character
}

Advancing Iterators

The increment operator (++) is used to move an iterator to the subsequent element. The end iterator, not pointing to an element, cannot be incremented or dereferenced.

// Iterate through each character of string 's'
for (auto it = s.begin(); it != s.end(); ++it) {
    // Process *it
}

Iterator Types

Standard library types typically provide iterator and const_iterator types for their iterators. A const_iterator allows read-only access to elements, similar to a pointer to a constant, while a regular iterator permits both reading and writing. If a container object is const, only const_iterator can be used. For non-constant objects, both iterator and const_iterator are available.

begin() and end() Return Values

The return type of begin() and end() depends on whether the object is const:

• For const objects, they return const_iterator.
• For non-const objects, they return iterator.

To consistently obtain a const_iterator, regardless of the object's constnesss, C++11 introduced cbegin() and cend(). These functions always return const_iterator.

std::vector<int> numbers;
auto const_it = numbers.cbegin(); // const_it is of type std::vector<int>::const_iterator

Combined Dereference and Member Access

To access a member of an object pointed to by an iterator, you can dereference the iterator first, then use the dot operator (.):

(*it).member_name

The parentheses are crucial to ensure dereferencing occurs before member access. C++ also provides the arrow operator (->) for this combined operation: it->member_name is equivalent to (*it).member_name.

Iterator Invalidation

Certain operations on std::vector, such as push_back(), can invalidate existing iterators. If an iterator is invalidated, it must not be used. Loops that modify the vector by adding elements should be written carefully to avoid using invalidated iterators.

Iterator Arithmetic

Iterators for std::vector and std::string support arithmetic operations:

• iter + n: Returns a new iterator advanced by n positions.
• iter - n: Returns a new iterator moved back by n positions.
• iter1 += n: Advances iter1 by n positions in-place.
• iter1 -= n: Moves iter1 back by n positions in-place.
• iter1 - iter2: Calculates the distance between two iterators. The result is the number of increments needed to get from iter2 to iter1. Both iterators must belong to the same container.
• Comparison operators (>, >=, <, <=): Allow comparing iterator positions within the same container.

Iterator Arithmetic Details

Adding or subtracting an integer from an iterator yields a new iterator offset by that integer. The result will point to an element or one past the last element. Comparisons using relational operators are valid only for iterators within the same container. Subtracting two iterators from the same container yields their distance, represented by a signed integral type (difference_type).

Using Iterator Arithmetic

Iterator arithmetic is fundamental to algorithms like binary search.

// Assumes 'text' is sorted.
// 'beg' and 'end' define the search range.
auto beg = text.begin(), end = text.end();

while (beg != end) {
    auto mid = beg + (end - beg) / 2; // Calculate midpoint
    if (*mid == sought) {
        // Found the element
        break;
    } else if (sought < *mid) {
        // Adjust the end of the search range to the midpoint
        end = mid;
    } else {
        // Adjust the beginning of the search range past the midpoint
        beg = mid + 1;
    }
}
// If beg == end after the loop, the element was not found.