Traverse Any Container with C++ Iterators

By the end of this page, you will understand what iterators are and why C++ needs them, write iterator-based loops over standard containers, recognise the five iterator categories and what each one supports, and avoid the three most common iterator bugs that cause undefined behaviour.

What and Why

Imagine you have three boxes of data: a std::vector (items in a contiguous array), a std::list (items linked by pointers), and a std::set (items in a balanced tree). Each stores data completely differently internally. If you wanted to write a generic print_all function, you would normally need a separate version for each container type.

Iterators solve this problem. An iterator is an object that represents a position inside a sequence. It exposes a small, consistent interface — dereference to get the current value, increment to advance, compare to know when you have reached the end — regardless of how the underlying container is laid out in memory.

The result is that a single algorithm, say std::sort, works on any container that provides the right kind of iterators. You write the algorithm once; the container supplies the navigation.

Think of an iterator the way you would think of a cursor in a text editor. The cursor knows where it is in the document, you can move it forward or backward, and you can read or replace the character it currently points at. The cursor does not need to understand whether the document is stored as one long string or as a tree of paragraphs.

Step by Step

The raw iterator loop (C++11)

Every standard container provides begin() and end() member functions. begin() returns an iterator positioned at the first element; end() returns one past the last element — a sentinel that marks "you have gone too far."

#include <iostream>
#include <vector>

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

    // it starts at the first element; the loop runs while it != end()
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << '\n';  // dereference to get the value
    }
}

Three operations cover almost all iterator use:

Range-based for is iterator sugar (C++11)

The range-based for loop you already know is exactly the raw loop above, written by the compiler on your behalf:

#include <iostream>
#include <vector>

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

    // The compiler expands this into the begin/end loop above.
    for (int n : numbers) {
        std::cout << n << '\n';
    }
}

Understanding that range-for uses iterators matters when the loop body must modify elements or when you need the iterator itself (for example, to erase during traversal).

Reading without modifying: const_iterator

When you only read from a container, prefer cbegin() and cend(). They return const_iterator objects that refuse to let you modify the underlying element, catching accidental mutations at compile time.

#include <iostream>
#include <vector>

void print(const std::vector<int>& v) {
    for (auto it = v.cbegin(); it != v.cend(); ++it) {
        // *it = 0;  // compile error — iterator is read-only
        std::cout << *it << '\n';
    }
}

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

The five iterator categories

Not every iterator can do everything. C++ defines a hierarchy of categories based on what operations are supported. The category a container provides determines which algorithms can work with it.

std::sort requires random-access iterators (it needs it + n for its partition steps). std::find only needs input iterators. When a call to std::sort fails to compile, mismatched iterator categories are often the reason.

The contiguous category was formalised in C++17. It adds the guarantee that elements occupy adjacent memory addresses, enabling std::span and pointer-arithmetic tricks that random-access iterators alone do not permit.

Common Patterns

Pattern 1 — finding and erasing a single element

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

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

    auto it = std::find(v.begin(), v.end(), 4);
    if (it != v.end()) {
        v.erase(it);  // erase the element at the found position
    }

    for (int n : v) std::cout << n << ' ';  // 3 1 1 5 9
}

Always check it != v.end() before using a result from std::find. If the value is absent, find returns end(), and dereferencing it is undefined behaviour.

Pattern 2 — iterating a sub-range

Because iterators are just positions, you can pass any valid range [first, last) to an algorithm — the range does not have to cover the whole container:

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

int main() {
    std::vector<int> v = {5, 3, 8, 1, 9, 2, 7};

    // Sort only the first four elements; leave the rest untouched.
    std::sort(v.begin(), v.begin() + 4);

    for (int n : v) std::cout << n << ' ';  // 1 3 5 8 9 2 7
}

Pattern 3 — reverse iteration

Every bidirectional container provides rbegin() and rend() for walking backwards without reversing the container itself:

#include <iostream>
#include <vector>

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

    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        std::cout << *it << ' ';  // 5 4 3 2 1
    }
}

Pattern 4 — safe advancement with std::next and std::prev (C++11)

Writing it + 1 only compiles for random-access iterators. std::next and std::prev work with any iterator category that supports movement in that direction, without modifying the original iterator.

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

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

    auto it = lst.begin();            // points at 10
    auto second = std::next(it);      // points at 20 — it is unchanged
    auto last = std::prev(lst.end()); // points at 50

    std::cout << *second << ' ' << *last << '\n';  // 20 50

    // std::next accepts an optional count:
    auto fourth = std::next(it, 3);   // points at 40
    std::cout << *fourth << '\n';     // 40
}

Prefer std::next(c.begin()) over ++c.begin(). The latter is not guaranteed to compile when begin() returns an rvalue (e.g., some MSVC debug iterators); std::next always works.

Pattern 5 — writing into a container with std::back_inserter

Algorithms that write to an output iterator (like std::copy or std::transform) need a destination. Passing v.begin() requires the destination to already have enough elements. std::back_inserter wraps a container and calls push_back for each write, growing the container automatically.

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

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

    std::copy_if(src.begin(), src.end(),
                 std::back_inserter(evens),          // C++98; no pre-sizing needed
                 [](int x) { return x % 2 == 0; });

    for (int n : evens) std::cout << n << ' ';      // 2 4
}

What Can Go Wrong

Dereferencing end()

end() points one past the last element — there is nothing there. Dereferencing it is undefined behaviour and typically causes a crash or silent data corruption.

std::vector<int> v = {1, 2, 3};
auto it = std::find(v.begin(), v.end(), 99);  // not found

// BAD — it == v.end(), so *it is undefined behaviour
std::cout << *it;

// GOOD — always guard the result
if (it != v.end()) {
    std::cout << *it;
}

Iterator invalidation

Many container operations invalidate existing iterators — the iterator no longer points at a valid location. For std::vector, any insertion that causes a reallocation invalidates all iterators into that vector. Erasing an element invalidates iterators at and after the erased position.

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin() + 2;  // points at 3

v.push_back(6);           // may reallocate — it is now invalid!
std::cout << *it;         // undefined behaviour

// GOOD — capture the index instead, or re-obtain the iterator after modification

Erasing inside a loop without updating the iterator

// BAD — incrementing an invalidated iterator is undefined behaviour
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) v.erase(it);  // erase returns the next valid iterator, but we ignore it
}

// GOOD — erase returns the next valid iterator; assign it back
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) it = v.erase(it);
    else ++it;
}

Quick Reference

std::distance and std::advance

std::distance measures how many steps separate two iterators, and std::advance moves an iterator by a given count — but both pay O(n) for non-random-access iterators, so understanding the cost matters. For random-access iterators (vector, deque, array), both operations are O(1) because the compiler subtracts or adds an integer directly. For forward or bidirectional iterators (list, map, set), distance counts steps one at a time and advance walks one node at a time.

#include <iterator>
#include <list>
#include <vector>

std::vector<int> v = {10, 20, 30, 40, 50};
auto it_v = v.begin();
std::advance(it_v, 3);                   // O(1): it_v now points at 40
auto d_v = std::distance(v.begin(), v.end()); // O(1): d_v == 5

std::list<int> lst = {10, 20, 30, 40, 50};
auto it_l = lst.begin();
std::advance(it_l, 3);                   // O(n): walks three links
auto d_l = std::distance(lst.begin(), lst.end()); // O(n): counts five steps

Prefer std::next(it, n) over std::advance when you do not want to mutate the original iterator. For size queries, most containers expose .size() directly in O(1) — avoid calling std::distance(c.begin(), c.end()) on those.

std::reverse_iterator and rbegin()/rend()

std::reverse_iterator is an adapter that wraps any bidirectional iterator and inverts the direction of ++ and --, so existing algorithms can traverse a range backwards without the container being reversed. Every bidirectional standard container exposes rbegin() (pointing at the last element) and rend() (a sentinel one before the first element).

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

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

    // Walk backwards
    for (auto it = v.rbegin(); it != v.rend(); ++it)
        std::cout << *it << ' ';   // 5 4 3 2 1

    // Algorithms accept reverse iterators as regular iterators
    auto pos = std::find(v.rbegin(), v.rend(), 3);
    // pos.base() is the forward iterator one past the found element
    std::cout << '\n' << *pos;     // 3
}

One subtle point: reverse_iterator::base() returns the underlying forward iterator shifted by one position past the element the reverse iterator names. This matters when you need to pass the result to a container operation like erase, which takes a forward iterator.

Stream Iterators: Treating Streams as Ranges

Stream iterators adapt std::istream and std::ostream to the iterator interface, allowing standard algorithms to read from or write to streams as if they were containers. std::istream_iterator<T> reads successive values of type T using operator>>, and std::ostream_iterator<T> writes successive values using operator<<.

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

int main() {
    // Read all integers from stdin into a vector
    std::vector<int> nums(
        std::istream_iterator<int>(std::cin),
        std::istream_iterator<int>()   // default-constructed == end-of-stream
    );

    // Compute sum
    int total = std::accumulate(nums.begin(), nums.end(), 0);

    // Write results to stdout, separated by ", "
    std::copy(nums.begin(), nums.end(),
              std::ostream_iterator<int>(std::cout, ", "));

    std::cout << "\nSum: " << total << '\n';
}

Stream iterators are single-pass input/output iterators, so you cannot rewind them or use them with algorithms that require multi-pass traversal (like std::sort). They are best suited for pipeline patterns: read from a stream, transform, and write to another stream.

Back-Insert Iterator

std::back_inserter(container) returns an output iterator that calls push_back for every value written to it, so copy and transform algorithms can append to a container without pre-sizing. Without it, you would need to resize the destination before calling std::copy, which either wastes memory or forces a two-pass approach.

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

int main() {
    std::vector<std::string> words = {"hello", "world", "cpp"};
    std::vector<std::string> upper;

    // transform each word to uppercase and push_back into upper
    std::transform(words.begin(), words.end(),
                   std::back_inserter(upper),
                   [](std::string s) {
                       for (char& c : s) c = static_cast<char>(std::toupper(c));
                       return s;
                   });

    for (const auto& w : upper)
        std::cout << w << ' ';   // HELLO WORLD CPP
}

The symmetric adapters are std::front_inserter (calls push_front, works with std::deque and std::list) and std::inserter(container, pos) (calls insert at a given position, works with associative containers). Choose based on where you want elements to appear.

Writing a Custom Iterator

A custom iterator must define five associated types and the three core operators (++, *, ==) to satisfy the requirements of the iterator category it claims to be. The standard library detects these through std::iterator_traits, which reads nested typedefs on the iterator type.

#include <iterator>
#include <cstddef>

// Iterates over every other element of a vector
template<typename T>
struct StrideIterator {
    using iterator_category = std::forward_iterator_tag;
    using value_type        = T;
    using difference_type   = std::ptrdiff_t;
    using pointer           = T*;
    using reference         = T&;

    T* ptr;
    std::size_t stride;

    StrideIterator(T* p, std::size_t s) : ptr(p), stride(s) {}

    reference operator*() const { return *ptr; }
    pointer   operator->() const { return ptr; }

    StrideIterator& operator++() {
        ptr += stride;
        return *this;
    }
    StrideIterator operator++(int) {
        auto tmp = *this;
        ++(*this);
        return tmp;
    }

    bool operator==(const StrideIterator& other) const { return ptr == other.ptr; }
    bool operator!=(const StrideIterator& other) const { return !(*this == other); }
};

// Usage
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6};
    StrideIterator<int> begin{v.data(), 2};
    StrideIterator<int> end{v.data() + v.size(), 2};
    for (auto it = begin; it != end; ++it)
        std::cout << *it << ' ';   // 1 3 5
}

C++20 simplifies this further with concepts: you can use std::forward_iterator as a constraint and let the compiler verify your type satisfies it, rather than relying on the typedefs alone.

C++20 Sentinels

C++20 generalises the "end of range" from a copy of the same iterator type to any type that can be compared with the iterator — called a sentinel — making it possible to express ranges whose end is determined by a condition rather than a position. Before C++20, begin() and end() had to return the same type; this forced null-terminated string wrappers, for example, to scan the entire string just to produce an end iterator.

#include <iterator>
#include <iostream>

// A sentinel that compares true when the iterator points at '\0'
struct NullTermSentinel {};

struct CharPtr {
    const char* ptr;
    bool operator==(NullTermSentinel) const { return *ptr == '\0'; }
    bool operator!=(NullTermSentinel) const { return *ptr != '\0'; }
    char operator*() const { return *ptr; }
    CharPtr& operator++() { ++ptr; return *this; }
};

// Count characters without pre-computing the length
int main() {
    const char* s = "hello";
    int count = 0;
    for (CharPtr it{s}; it != NullTermSentinel{}; ++it)
        ++count;
    std::cout << count;   // 5
}

C++20 range algorithms (in <algorithm>) accept heterogeneous iterator/sentinel pairs natively. The std::ranges::subrange type also captures iterator-sentinel pairs for passing through APIs. Sentinels are more than a theoretical nicety — they enable lazy ranges over infinite or termination-condition-based sequences.

Iterator Invalidation Rules

Container mutations may silently destroy existing iterators, leaving them pointing at freed memory or garbage values — always check whether an operation invalidates before reusing an iterator. The rules differ by container and by operation type.

Reserve capacity upfront with vector::reserve to prevent reallocation-driven invalidation in a known-size append loop. For node-based containers (list, map, set), insertions never invalidate — only erasure of the specific node does.

What's Next

• STL Algorithms — std::sort, std::transform, std::copy, and forty more algorithms that accept iterator pairs.
• Containers in Depth — understand which iterator category each container provides and why that shapes which algorithms you can use.
• Const Correctness — see how const_iterator fits into C++'s broader const model.
• C++20 introduces ranges, a higher-level layer built on top of iterators that removes many iterator-pair boilerplate patterns. Once you are comfortable with iterators, ranges are the natural next step.