Skip to content
Tutorials Center
My learning

Topics

Lesson 95 of 171 ยท The Standard Library (STL)

Iterators

Learn C++ iterators - begin and end, iterator categories, const and reverse iterators, insert iterators, iterator invalidation rules, and std::advance, next and distance.

An iterator is an object that points to an element in a sequence and knows how to move to the next one. It's the STL's universal adapter: containers hand out iterators, and algorithms consume them. Because every algorithm talks only to iterators, std::find doesn't care whether it walks a vector, a linked list, a set or the characters of a string. In the STL overview you saw iterators returned by algorithms; this lesson explains what they are and how to use them safely.

Iterators deliberately look like pointers: *it gives the element, ++it moves forward, it->member reaches into it. For a std::vector they may even be little more than a pointer. But a std::map iterator walks a tree and a std::list iterator follows links, all behind the same syntax. You'll learn the half-open range convention, the iterator categories that decide which algorithms you may use, const and reverse iterators, special iterators that insert or read streams, the helper functions std::advance, std::next, std::prev and std::distance, and the invalidation rules that cause some of the nastiest bugs in C++.

begin, end and half-open ranges

Every container has begin(), which points to the first element, and end(), which points one past the last element. end() is never dereferenced; it's a marker. A range written [begin, end) includes the first position and excludes the last, which is why it's called half-open.

C++ Walking a container with iterators

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Half-open ranges have nice properties that explain the whole STL design:

  • An empty range is simply begin == end; no special case needed.
  • The number of elements is end - begin (for random-access iterators).
  • Splitting [first, last) at mid gives [first, mid) and [mid, last) with no overlap and no gap.
  • "Not found" can be reported by returning end, a position that's never a valid element.

Range-based for (auto x : c) is translated by the compiler into exactly the iterator loop above, using begin(c) and end(c). Anything with begin/end works, including C arrays, std::string_view and your own types.

Prefer the free functions std::begin(c), std::end(c), std::size(c) (or std::ranges::begin and friends) in generic code: they also work on plain C arrays, which have no member functions.

Iterator categories

Not every iterator can do everything. A singly linked list can only move forward; a tree can move both ways but can't jump; a vector can jump straight to any position. The standard groups iterators into categories, each adding abilities to the previous one:

Category Adds Examples
Input read *it once, ++it, compare std::istream_iterator
Output write *it = x, ++it std::back_insert_iterator, std::ostream_iterator
Forward read many times, multi-pass std::forward_list, std::unordered_map
Bidirectional --it std::list, std::set, std::map
Random access it + n, it[n], it2 - it1, < std::deque
Contiguous (C++20) elements are adjacent in memory std::vector, std::array, std::string, pointers

Algorithms state the category they need. std::find needs only input iterators; std::reverse needs bidirectional; std::sort and std::nth_element need random access. That's why sorting a std::list with std::sort doesn't compile, and why std::list has its own sort() member. In C++20 each category is also a concept, such as std::random_access_iterator<It>.

C++ What each iterator category can do

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

const iterators and reverse iterators

A const_iterator lets you read elements but not modify them, like a pointer to const. You get one from cbegin()/cend(), or from begin()/end() on a const container. Use them whenever you only read; the compiler will then catch accidental writes.

A reverse iterator walks backwards: rbegin() points to the last element and rend() to "one before the first". ++ on a reverse iterator moves toward the front, so every algorithm works backwards unchanged. crbegin()/crend() combine both.

C++ const and reverse iterators

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The base() off-by-one is a common trap. A reverse iterator r refers to the element before r.base(). So to erase what r points at, erase std::prev(r.base()) (or std::next(r).base()).

advance, next, prev and distance

Only random-access iterators support it + 5 and it2 - it1. The functions in <iterator> give you the same operations for every category, picking the fastest implementation:

  • std::advance(it, n) moves it by n steps in place (negative n needs bidirectional).
  • std::next(it, n = 1) and std::prev(it, n = 1) return a moved copy, leaving it alone.
  • std::distance(first, last) counts the steps from first to last.

On a vector these are O(1); on a list or map they walk step by step, O(n). They make code generic, but they don't make linked lists fast.

C++ advance, next, prev and distance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

std::next and std::prev don't check bounds. Moving past end() or before begin() is undefined behavior, just like with pointers.

Iterators that do more: inserters and streams

Some iterators don't point into a container at all. Insert iterators turn writes into insertions, so an algorithm can fill a container that starts out empty:

  • std::back_inserter(c) calls c.push_back(x) for every *it = x.
  • std::front_inserter(c) calls c.push_front(x) (for deque, list).
  • std::inserter(c, pos) calls c.insert(pos, x) (works for sets and maps too).

Stream iterators treat streams as sequences: std::istream_iterator<T> reads values with >> until the input ends, and std::ostream_iterator<T> writes them with <<.

C++ Insert and stream iterators

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The default-constructed std::istream_iterator<int>{} is the end-of-stream marker: the iterator becomes equal to it when reading fails or the input runs out. Without back_inserter, std::copy_if(..., big.begin(), ...) would write into an empty vector's nonexistent elements, which is undefined behavior. Output algorithms never grow a container by themselves.

Iterator invalidation

An iterator is only valid while the thing it points to stays put. Some container operations move or destroy elements, and every iterator, pointer and reference to the affected elements becomes invalidated. Using an invalidated iterator is undefined behavior: it may appear to work, print garbage, or crash.

Container Insertion invalidates Erasure invalidates
vector, string everything if capacity grows; otherwise elements at and after the insertion point elements at and after the erased point (and end())
deque all iterators (references stay valid when inserting at either end) at the ends: only the erased elements (plus end() when erasing the back); in the middle: everything
list, forward_list nothing only the erased elements
set, map, multi versions nothing only the erased elements
unordered_* everything if a rehash happens; otherwise nothing only the erased elements

The classic bug is erasing inside a loop. After v.erase(it), it is invalid, so ++it is undefined behavior. erase returns an iterator to the element after the erased one; use that.

C++ Erasing safely while iterating

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The last part shows why vector iterators die: when push_back exceeds the capacity, the vector allocates a new buffer, moves the elements and frees the old one. Any iterator, pointer or reference into the old buffer now dangles. If you need to keep positions across insertions, store indices instead of iterators, or reserve() enough capacity up front. std::vector in Depth explains the growth strategy.

Two tools catch invalidation bugs while developing: compile with -D_GLIBCXX_DEBUG (GCC's checked library aborts with a message on invalid iterator use) or with -fsanitize=address. See Undefined Behavior and Memory Safety.

Writing iterator-friendly code

  • Use range-for when you visit every element and don't modify the container's structure.
  • Use algorithms (std::ranges::find, std::erase_if, std::ranges::count_if) instead of hand-written iterator loops where one fits.
  • Take auto for iterator types; nobody wants to type std::map<std::string, std::vector<int>>::const_iterator.
  • Compare iterators with != in loops: that works for every category, while < only works for random access.
  • Never mix iterators from different containers in one range; std::sort(a.begin(), b.end()) compiles and corrupts memory. The std::ranges:: algorithms that take a whole container prevent this.
  • Don't hold iterators across operations that may invalidate them.

If you write your own container, giving it begin() and end() that return iterators with *, ++ and != is enough for range-for. To work with standard algorithms and ranges, the iterator also needs the member types and operations of its category, which you can check with static_assert(std::forward_iterator<MyIterator>).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. For std::vector<int> v{1, 2, 3};, what does *v.end() do?

    end() is a marker for the position after the last element. It must never be dereferenced.
  2. 2. Why does std::sort(myList.begin(), myList.end()) fail to compile for a std::list?

    Sorting needs to jump around and compute distances in O(1). Use myList.sort() instead.
  3. 3. In the loop for (auto it = v.begin(); it != v.end(); ++it) { if (*it == 0) v.erase(it); }, what is wrong?

    Erasing invalidates the iterator to the erased element. Write it = v.erase(it) and only increment when nothing was erased, or use std::erase_if.
  4. 4. std::list<int> l{1, 2, 3, 4}; auto it = std::next(l.begin(), 2); What is *it, and is l.begin() changed?

    std::next returns a copy advanced by two steps (to the third element) and leaves its argument alone. std::advance would modify an iterator in place.
  5. 5. std::vector<int> out; std::copy(in.begin(), in.end(), out.begin()); with a non-empty in. What happens?

    Algorithms write through iterators and never resize containers. back_inserter turns each write into push_back.

Summary

  • An iterator points into a sequence: *it reads, ++it advances; begin() and end() define a half-open range [begin, end), and end() is never dereferenced.
  • Categories (input, output, forward, bidirectional, random access, contiguous) decide which algorithms you may use; std::sort needs random access.
  • cbegin/cend give read-only iterators; rbegin/rend walk backwards, and r.base() points one element to the right.
  • std::advance, std::next, std::prev and std::distance work for every category, in O(1) for random access and O(n) otherwise.
  • Insert iterators (back_inserter, inserter) let algorithms grow containers; stream iterators read and write streams as sequences.
  • Know the invalidation rules: vector growth invalidates everything, list and map erasure only the erased element. Use the iterator erase returns, or std::erase_if.

Next: std::vector in Depth, where you'll see how the most important container grows, shrinks and stays fast.