Iterators

Every STL container — vector, list, map, set, and the rest — stores its elements differently in memory. A vector is contiguous, a list is a chain of linked nodes, a map is a tree. If every algorithm had to know the internal layout of every container, the STL would fall apart. Iterators solve this: an iterator is a generalized, pointer-like object that knows how to move to the "next" element of whatever container it belongs to, without the calling code needing to know how that traversal actually works under the hood.

Because every container exposes the same small interface — dereference with *, advance with ++, compare with == — a single generic algorithm like std::sort or std::find can operate on a vector, a deque, or a set purely through its iterators, never touching the container's internals directly.

begin() and end()

Every container provides .begin(), which returns an iterator to the first element, and .end(), which returns an iterator one position past the last element (a sentinel you must never dereference). A range is therefore described as the half-open interval [begin, end). Const-correct variants .cbegin() and .cend() return const_iterators, which let you read elements but not modify them through that iterator — useful when you want to guarantee a function doesn't mutate the container it's traversing.

Manual iterator loop vs range-based for

CPP

#include <iostream>
#include <vector>

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

    // Manual iterator loop
    for (std::vector<int>::iterator it = nums.begin(); it != nums.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    // Read-only traversal with a const_iterator
    for (auto it = nums.cbegin(); it != nums.cend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    // Range-based for loop: the compiler expands this into
    // the exact same begin()/end()/operator++ pattern above.
    for (int n : nums) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

Range-based for is syntactic sugar

The range-based for (auto x : container) loop introduced in C++11 is not a new traversal mechanism — it is rewritten by the compiler into calls to .begin(), .end(), and operator++ on an iterator, exactly like the manual loop above. Understanding iterators is what lets you understand what the range-based for is actually doing for you.

Iterator categories

Not all iterators support the same operations. The STL defines a hierarchy of iterator categories, each a superset of the one before it in capability. An algorithm documents the minimum category it needs — for example, std::sort requires random access iterators, which is why you cannot sort a std::list with it directly (list provides only bidirectional iterators; it has its own .sort() member function instead).

Category	Supports	Example containers
Input	Single-pass read, ++ forward	istream_iterator, input streams
Output	Single-pass write, ++ forward	ostream_iterator, back_inserter
Forward	Multi-pass read/write, ++ forward	forward_list, unordered_map/set
Bidirectional	Forward capabilities + -- backward	list, set, map, multiset, multimap
Random Access	Bidirectional + jump by n in O(1) (it + n, it[n])	vector, deque, array, C-style arrays

Modifying a container while iterating

Iterators are only valid as long as the container's internal state matches what they were obtained from. Certain operations — inserting into a full vector (triggering reallocation), or erasing an element — invalidate some or all outstanding iterators into that container.

The wrong way to erase while iterating

CPP

#include <vector>

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

    // BUG: erase() invalidates 'it', so ++it on the next
    // iteration is undefined behavior.
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        if (*it % 2 == 0) {
            nums.erase(it); // invalidates it and everything after it
        }
    }

    // CORRECT: erase() returns a valid iterator to the next
    // element, so reassign it instead of blindly incrementing.
    std::vector<int> nums2 = {1, 2, 3, 4, 5};
    for (auto it = nums2.begin(); it != nums2.end(); ) {
        if (*it % 2 == 0) {
            it = nums2.erase(it);
        } else {
            ++it;
        }
    }

    return 0;
}

Iterator invalidation is undefined behavior, not a crash

Modifying a container (inserting, erasing, or in a vector's case, even just growing past capacity) while an iterator into it is still in use is one of the most common sources of subtle C++ bugs. It may appear to work by accident in testing and then corrupt memory in production. Always consult the container's documentation for which operations invalidate which iterators, and prefer the idiomatic fix — such as reassigning the iterator from .erase()'s return value — over incrementing a stale one.

Iterators are the uniform interface that lets one algorithm work across many container types.
.begin()/.end() define a half-open range; .cbegin()/.cend() give read-only access.
The range-based for loop is compiler sugar over the manual iterator pattern.
Five categories — input, output, forward, bidirectional, random access — form a capability hierarchy.
Never use an iterator after an operation that may have invalidated it.