{"title":"Iterators","description":null,"content":"An iterator is the STL's answer to a simple question: how to write code that walks through a `std::vector`, a `std::list`, a `std::set`, and a `std::map` the same way, without caring about the internal storage of each one. An iterator is a small object that behaves like a generalised pointer. Dereference it to get the current element, increment it to advance, and compare two iterators to know when the end is reached. This chapter covers the iterator concept, the `begin()` and `end()` family of accessors, how the range-based `for` loop uses them, `const_iterator`, iterator invalidation, and the insert and stream iterator adapters. The next chapter classifies iterators into categories and shows why those categories matter for algorithms.\n\n---\n\n# The Generalised Pointer\n\nA raw pointer into an array is the simplest possible iterator. Dereference it with `*`, advance it with `++`, and compare two of them with `==` or `!=`. The STL takes that interface and lifts it to every container.\n\n\n```cpp\n#include \n\nint main() {\n int prices[] = {1999, 1499, 999, 4999, 1999};\n int* it = prices; // first element\n int* end = prices + 5; // one past the last\n\n while (it != end) {\n std::cout << *it << \" \";\n ++it;\n }\n std::cout << std::endl;\n return 0;\n}\n```\n\n\nThe pointer `it` walks the array. `*it` reads the current element, `++it` moves to the next, and the loop stops when `it` reaches `end`, which sits one past the last valid element. That \"one past the last\" position is a sentinel: a valid iterator value that must not be dereferenced, but that can be compared against.\n\nThe STL generalises this pattern. Every standard container provides a `begin()` that returns an iterator to the first element and an `end()` that returns an iterator one past the last. The iterator type is specific to the container, but the four operations stay the same: `*it`, `++it`, `it == other`, `it != other`. The loop body doesn't know whether it's walking a vector or a linked list.\n\n\n```cpp\n#include \n#include \n\nint main() {\n std::vector prices = {1999, 1499, 999, 4999, 1999};\n\n std::vector::iterator it = prices.begin();\n std::vector::iterator end = prices.end();\n\n while (it != end) {\n std::cout << *it << \" \";\n ++it;\n }\n std::cout << std::endl;\n return 0;\n}\n```\n\n\nThe shape of the loop is identical to the raw-pointer version. The only difference is the type of `it`: a `std::vector::iterator` instead of an `int*`. For a `std::vector` those are nearly interchangeable in behaviour, but for a `std::list` the iterator is structured differently internally. The loop above still works against `std::list` with no changes to the body.\n\n\n```cpp\n#include \n#include \n\nint main() {\n std::list prices = {1999, 1499, 999, 4999, 1999};\n\n std::list::iterator it = prices.begin();\n std::list::iterator end = prices.end();\n\n while (it != end) {\n std::cout << *it << \" \";\n ++it;\n }\n std::cout << std::endl;\n return 0;\n}\n```\n\n\nThat uniformity is the entire point of iterators. They are the glue between containers and algorithms. A function that takes a `begin` and an `end` works against any container that supplies those, which is why `std::sort`, `std::find`, and friends can operate on most STL containers without caring how the elements are stored.\n\n---\n\n# begin() and end()\n\nEvery standard container provides a pair of member functions that return iterators delimiting its contents.\n\n\n| Function | Returns | Pointing to |\n|----------|---------|-------------|\n| `begin()` | `iterator` | The first element |\n| `end()` | `iterator` | One past the last element |\n| `cbegin()` | `const_iterator` | The first element, read-only |\n| `cend()` | `const_iterator` | One past the last, read-only |\n| `rbegin()` | `reverse_iterator` | The last element |\n| `rend()` | `reverse_iterator` | One before the first |\n\n\nThe important part of this table is `end()`. It does not point to a real element. It points to a position that sits one slot past the last valid element. This is called the **half-open range** `[begin, end)`, and the STL uses it everywhere.\n\n\n```mermaid\nflowchart LR\n B[begin]:::cyan --> E0[1999]:::orange --> E1[1499]:::orange --> E2[999]:::orange --> E3[4999]:::orange --> E4[1999]:::orange --> END[end
past-the-last]:::green\n\n classDef cyan fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe cyan node is the position `begin()` returns. The orange nodes are the actual elements. The green node is `end()`, which marks \"no more elements\". Dereferencing `end()` is undefined behaviour. Comparing `it == end()` is how the boundary is detected.\n\nThere are three reasons the standard uses a half-open range instead of an inclusive `[begin, last]`.\n\nFirst, an empty container has `begin() == end()`. With a closed range, a special \"no elements\" flag would be needed because there's no valid \"last\" position to point to. The half-open range encodes \"empty\" naturally.\n\nSecond, the loop condition is `it != end`, not `it <= end`. That works even for iterators that don't support `<` (like `std::list` iterators), and it works without off-by-one errors.\n\nThird, the length of the range is exactly `end - begin` (for iterators that support subtraction). With an inclusive range it would be `end - begin + 1`, and the `+ 1` is a constant source of bugs.\n\nAn empty vector demonstrating the convention:\n\n\n```cpp\n#include \n#include \n\nint main() {\n std::vector empty;\n std::cout << \"begin == end: \" << (empty.begin() == empty.end()) << std::endl;\n std::cout << \"size: \" << empty.size() << std::endl;\n return 0;\n}\n```\n\n\n`begin()` and `end()` compare equal because both point to the same imaginary \"no elements\" position. The half-open convention makes the empty case fall out of the same code path as the non-empty case.\n\n---\n\n# Iterator Operations\n\nThe four operations every iterator supports are dereference, member access, increment, and comparison. These are the same operations a raw pointer supports.\n\n\n```cpp\n#include \n#include \n#include \n\nstruct Product {\n std::string name;\n double price;\n};\n\nint main() {\n std::vector cart = {\n {\"Wireless Headphones\", 79.99},\n {\"USB Cable\", 9.99},\n {\"Mouse Pad\", 14.99}\n };\n\n auto it = cart.begin();\n std::cout << \"first name: \" << (*it).name << std::endl; // operator*\n std::cout << \"first price: \" << it->price << std::endl; // operator->\n\n ++it; // pre-increment\n std::cout << \"second name: \" << it->name << std::endl;\n\n auto same = it;\n std::cout << \"same? \" << (it == same) << std::endl;\n return 0;\n}\n```\n\n\n`*it` gives a reference to the element, so `(*it).name` reads its `name` field. `it->name` is the same thing, shorter. `++it` advances to the next element. `==` and `!=` compare two iterators by position, not by the value they point to.\n\nThere's a small but real distinction between pre-increment `++it` and post-increment `it++`. Pre-increment advances the iterator and returns it. Post-increment makes a copy of the iterator, advances the original, and returns the copy. For most STL iterators the copy is cheap, but pre-increment is still the default in C++ code because it avoids the copy.\n\nUse `++it` rather than `it++` in loops. Pre-increment skips the temporary copy. The difference is negligible for most iterators but real for some custom iterator types, and the habit costs nothing.\n\nThe four core operations are universal. Not every iterator supports more than that. Some support backward stepping (`--it`), some support jumps (`it + 5`), some support comparison with `<` or subtraction between two iterators for a distance. The available extras depend on the iterator's category.\n\n---\n\n# auto with Iterators\n\nIterator types are long. `std::vector::iterator` is a mouthful; nested containers get worse. The `auto` keyword, available since C++11, lets the compiler deduce the type from the initialiser, and it's how iterator variables are typically declared.\n\n\n```cpp\n#include \n#include \n#include \n\nint main() {\n std::map stock = {\n {\"Wireless Headphones\", 12},\n {\"USB Cable\", 47},\n {\"Mouse Pad\", 5}\n };\n\n for (auto it = stock.begin(); it != stock.end(); ++it) {\n std::cout << it->first << \" -> \" << it->second << std::endl;\n }\n return 0;\n}\n```\n\n\nThe deduced type of `it` is `std::map::iterator`. Spelling that out adds noise without adding information. `auto` keeps the loop readable.\n\nThe `std::map` output is sorted by key because `std::map` orders elements by key internally. That's a property of the container, not the iterator: the iterator walks the elements in whatever order the container stores them.\n\n`auto` is also the only practical option for iterators whose type involves another deduced type, like the iterator into a vector of lambdas or a vector of iterators. Type inference handles those automatically; spelling them out by hand is tedious.\n\n---\n\n# The Range-Based For Loop\n\nC++11 added the range-based `for` loop, the cleanest way to iterate. It's not a new mechanism, just shorthand for the `begin()`/`end()`/`++` pattern.\n\n\n```cpp\n#include \n#include \n\nint main() {\n std::vector prices = {29.99, 14.99, 9.99, 49.99};\n\n for (double p : prices) {\n std::cout << p << \" \";\n }\n std::cout << std::endl;\n return 0;\n}\n```\n\n\nWhat the compiler generates (in spirit, modulo a few details) is the explicit iterator loop:\n\n\n```cpp\n{\n auto&& __range = prices;\n auto __begin = __range.begin();\n auto __end = __range.end();\n for (; __begin != __end; ++__begin) {\n double p = *__begin;\n std::cout << p << \" \";\n }\n}\n```\n\n\nThe range-based loop calls `begin()` once, calls `end()` once, dereferences the iterator into the loop variable, and increments per iteration. Knowing this desugaring matters for two reasons.\n\nFirst, the loop variable receives a **copy** of the element by default. Iterating a vector of large objects with `for (Order o : orders)` copies every order. Use `for (const auto& o : orders)` to take a const reference and avoid the copy. Use `for (auto& o : orders)` to modify the elements in place.\n\n\n```cpp\n#include \n#include \n#include \n\nstruct Product {\n std::string name;\n int stock;\n};\n\nint main() {\n std::vector catalog = {\n {\"Wireless Headphones\", 12},\n {\"USB Cable\", 47},\n {\"Mouse Pad\", 5}\n };\n\n for (auto& p : catalog) {\n p.stock += 10;\n }\n\n for (const auto& p : catalog) {\n std::cout << p.name << \": \" << p.stock << std::endl;\n }\n return 0;\n}\n```\n\n\nThe first loop modifies stock counts through `auto&`. The second loop reads through `const auto&` and avoids copying the `Product` structs. Picking the right access mode for each loop keeps the cost predictable.\n\n`for (auto x : v)` copies every element. For `int` or `double` that's free, but for `std::string`, `std::vector`, or any class with a non-trivial copy constructor, it adds an allocation per iteration. `for (const auto& x : v)` reads the elements without copying, the right default for non-trivial types.\n\nSecond, the range-based loop assumes `begin()` and `end()` work on whatever range it receives. Standard containers all qualify, raw arrays of known size qualify, and custom types qualify as long as they provide `begin()` and `end()` (member functions or free functions found via argument-dependent lookup).\n\n---\n\n# const_iterator and Read-Only Access\n\nFor iteration without modification, use a `const_iterator`. It walks the container the same way but dereferences to a `const` reference, so the compiler reports an error on accidental writes.\n\n\n```cpp\n#include \n#include \n\nint main() {\n std::vector stock = {12, 47, 5, 9, 23};\n\n for (std::vector::const_iterator it = stock.cbegin(); it != stock.cend(); ++it) {\n std::cout << *it << \" \";\n // *it = 0; // would not compile: assigning through const_iterator\n }\n std::cout << std::endl;\n return 0;\n}\n```\n\n\nThere are three ways to land on a `const_iterator`.\n\nFirst, call `cbegin()` and `cend()`, which always return `const_iterator` regardless of whether the container is `const`. This is the explicit way and the most clearly intentional.\n\nSecond, call `begin()` and `end()` on a `const` container. The non-`const` overloads aren't visible, so the `const` overloads take over and return `const_iterator`.\n\n\n```cpp\n#include \n#include \n\nvoid printAll(const std::vector& stock) {\n for (auto it = stock.begin(); it != stock.end(); ++it) {\n std::cout << *it << \" \";\n }\n std::cout << std::endl;\n}\n\nint main() {\n std::vector stock = {12, 47, 5};\n printAll(stock);\n return 0;\n}\n```\n\n\nInside `printAll`, `stock` is `const std::vector&`, so `stock.begin()` is the `const` overload and the deduced `auto` type is `std::vector::const_iterator`. Writing through `it` wouldn't compile.\n\nThird, store the iterator in `auto` from a `cbegin()` call. That's the modern, succinct version of the first option.\n\nWhy use `const_iterator` when ordinary `iterator` works? Two reasons. It documents intent: a reader of the function knows the loop won't modify the elements. It catches bugs at compile time. A refactor that adds `*it = ...` inside a read-only loop makes the compiler stop the change instead of letting the bug slip into production.\n\n---\n\n# Reverse Iterators\n\nFor walking a container backwards, `rbegin()` returns an iterator pointing to the last element, and `rend()` returns one pointing to the position **before** the first element. The same `++` operator that advances forward on a regular iterator advances backward on a reverse iterator.\n\n\n```cpp\n#include \n#include \n\nint main() {\n std::vector orderHistory = {\"ORD-1\", \"ORD-2\", \"ORD-3\", \"ORD-4\"};\n\n for (auto it = orderHistory.rbegin(); it != orderHistory.rend(); ++it) {\n std::cout << *it << \" \";\n }\n std::cout << std::endl;\n return 0;\n}\n```\n\n\nThe output is the elements in reverse order. The reverse iterator does the bookkeeping internally: it stores a forward iterator one position ahead of where it conceptually points, so `++` on the reverse iterator becomes `--` on the underlying forward iterator. None of that is visible from outside. The same `*it`/`++it`/`it != end` pattern works.\n\nReverse iterators exist mainly to plug into algorithms. Anywhere a function takes a `begin` and an `end`, passing `rbegin()` and `rend()` makes it process the range backwards.\n\n---\n\n# Iterator Invalidation\n\nThe trickiest part of iterators is that they can become invalid. An iterator stores a position inside the container, and if the container reorganises its memory, that position no longer points to the expected element. Reading through an invalidated iterator is undefined behaviour and is one of the most common sources of bugs in STL code.\n\nThe rules differ by container.\n\n### std::vector\n\nA `std::vector` stores its elements in a single contiguous block of heap memory. When an element is added and the block is already full, the vector allocates a new (larger) block, copies or moves the elements over, and frees the old block. Every iterator that pointed into the old block is now dangling.\n\n\n```cpp\n#include \n#include \n\nint main() {\n std::vector prices = {10, 20, 30};\n auto it = prices.begin();\n std::cout << \"before push_back: \" << *it << std::endl;\n\n for (int i = 0; i < 100; ++i) {\n prices.push_back(i); // may reallocate\n }\n // *it is now potentially dangling\n std::cout << \"after push_back: \" << *it << std::endl; // undefined behaviour\n return 0;\n}\n```\n\n\nThe output of the second print depends on whether the vector reallocated. If it did, `it` points to freed memory. If it didn't, it still works. Either way, the code is broken because it depends on knowledge the vector doesn't guarantee.\n\nFor `std::vector`, the invalidation rules are:\n\n- `push_back`, `emplace_back`, `insert`, `resize`, `reserve` (if it grows): invalidate all iterators if the capacity changes; otherwise iterators at or after the insertion point are invalidated.\n- `pop_back`: invalidates the iterator to the removed element and `end()`.\n- `erase(it)`: invalidates `it` and every iterator after it.\n- `clear()`: invalidates all iterators.\n\nRepeatedly calling `push_back` on a `std::vector` triggers occasional reallocations, each one O(n). Iterators captured before the reallocation become dangling. Call `reserve(expected_size)` first to remove the reallocations and keep iterators valid for the life of the loop.\n\n### std::deque\n\nA `std::deque` stores elements in chunks rather than a single block. Inserting or removing at either end is O(1) and does not invalidate iterators to elements that didn't move. Inserting or removing in the middle invalidates all iterators, because the deque has to shift chunks around to maintain its layout.\n\n### std::list and std::forward_list\n\nLinked lists hold each element in its own node. Adding or removing nodes elsewhere in the list doesn't touch the existing nodes, so iterators pointing to those nodes stay valid. The only iterator that becomes invalid is the one pointing to a node that was just erased.\n\n\n```cpp\n#include \n#include \n\nint main() {\n std::list stock = {10, 20, 30, 40, 50};\n auto it = stock.begin();\n ++it; // points to 20\n\n stock.push_front(99); // doesn't touch existing nodes\n stock.push_back(88);\n\n std::cout << \"still 20? \" << *it << std::endl;\n return 0;\n}\n```\n\n\n`it` still points to the same node it always did. The new elements went into newly-allocated nodes that don't disturb the existing chain.\n\n### std::set, std::map (and their multi-* variants)\n\nThese are typically implemented as balanced binary search trees. Insertions and deletions rearrange tree pointers but don't move existing nodes in memory, so iterators to nodes that weren't erased stay valid. The iterator to an erased element is the only one invalidated.\n\n### std::unordered_set, std::unordered_map\n\nHash tables have a wrinkle. As elements are inserted, the load factor (elements per bucket) grows. When it crosses a threshold, the table **rehashes**: it allocates a new bucket array, recomputes hashes, and redistributes elements. Iterators into the old buckets are invalidated. Iterators don't move within their bucket, but the bucket itself may have moved.\n\nThe summary table:\n\n\n| Container | Insert (at end / front) | Insert (middle) | Erase |\n|-----------|-------------------------|-----------------|-------|\n| `std::vector` | All invalidated if reallocates; else iterators after insert point | All after insert point | `it` and after |\n| `std::deque` | All iterators (some references survive) | All | All |\n| `std::list` | None | None | Only `it` |\n| `std::forward_list` | None | None | Only `it` |\n| `std::set` / `std::map` | None | None | Only `it` |\n| `std::unordered_*` | None unless rehash; then all | None unless rehash | Only `it` |\n\n\n---\n\n# Insert Iterators\n\nMost algorithms in `` write to an output range that already has room for the results. `std::copy(first, last, dest)` writes through `dest` by assignment, which means `*dest = value; ++dest`. If `dest` is a plain vector iterator, the vector must already have enough size for the writes.\n\nInsert iterators wrap a container and turn assignment into a container operation. `*it = value` becomes `container.push_back(value)`, `push_front(value)`, or `insert(pos, value)` depending on which insert iterator was used. The container grows as the algorithm writes to it.\n\n\n```cpp\n#include \n#include \n#include \n#include \n\nint main() {\n std::vector source = {1, 2, 3, 4, 5};\n std::vector dest;\n\n std::copy(source.begin(), source.end(), std::back_inserter(dest));\n\n for (int x : dest) std::cout << x << \" \";\n std::cout << std::endl;\n return 0;\n}\n```\n\n\n`std::back_inserter(dest)` returns a small iterator object that, on assignment, calls `dest.push_back(...)`. The `std::copy` algorithm doesn't know or care that the destination is a back-inserter; it just performs `*it = value; ++it` in a loop, and the wrapper turns those operations into the right container calls. `dest` started empty and ended up holding all five values.\n\nThere are three insert iterators in ``:\n\n\n| Adapter | Container operation | Requires |\n|---------|---------------------|----------|\n| `std::back_inserter(c)` | `c.push_back(value)` | Container with `push_back` (vector, deque, list) |\n| `std::front_inserter(c)` | `c.push_front(value)` | Container with `push_front` (deque, list, forward_list) |\n| `std::inserter(c, pos)` | `c.insert(pos, value)` | Any container with `insert(pos, value)` |\n\n\n`front_inserter` reverses order, because each new element is pushed in front of the previous one.\n\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n\nint main() {\n std::vector source = {1, 2, 3, 4, 5};\n std::deque dest;\n\n std::copy(source.begin(), source.end(), std::front_inserter(dest));\n\n for (int x : dest) std::cout << x << \" \";\n std::cout << std::endl;\n return 0;\n}\n```\n\n\n`1` was pushed to the front, then `2` was pushed in front of `1`, and so on, leaving the deque with elements in reverse order. `back_inserter` would have preserved the order.\n\n`std::inserter(c, pos)` is the general one. It inserts at the position given by `pos` and updates `pos` as it goes, so successive inserts happen in order.\n\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n\nint main() {\n std::vector source = {5, 1, 4, 2, 3};\n std::set dest;\n\n std::copy(source.begin(), source.end(), std::inserter(dest, dest.end()));\n\n for (int x : dest) std::cout << x << \" \";\n std::cout << std::endl;\n return 0;\n}\n```\n\n\n`std::set` doesn't have `push_back`, so `back_inserter` wouldn't work. `inserter` calls `dest.insert(pos, value)`, which is what `std::set` provides, and the set sorts as it goes.\n\n---\n\n# Stream Iterators\n\nThe other useful pair of adapters treats input and output streams as iterator ranges. `std::istream_iterator` reads `T` values one at a time from a stream; `std::ostream_iterator` writes `T` values to a stream one at a time. They're useful for plugging algorithms into I/O without writing custom loops.\n\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n\nint main() {\n std::istringstream input(\"10 25 3 17 42\");\n std::vector stock;\n\n std::copy(std::istream_iterator(input),\n std::istream_iterator(),\n std::back_inserter(stock));\n\n std::copy(stock.begin(), stock.end(),\n std::ostream_iterator(std::cout, \" \"));\n std::cout << std::endl;\n return 0;\n}\n```\n\n\n`std::istream_iterator(input)` is the beginning of the range: it reads one `int` from `input` on each dereference and increment. `std::istream_iterator()` (no argument) is the end-of-stream sentinel: comparing the live iterator to a default-constructed one detects when the stream has run out of data.\n\n`std::ostream_iterator(std::cout, \" \")` builds an iterator that, on assignment, writes its argument to `std::cout` followed by a space. `std::copy` walks the vector and assigns each element through it, producing the printed output.\n\nThe stream-iterator approach is most useful for reading or writing a range of values without writing the loop. For one-off `std::cin` reads it's overkill; for piping data through algorithms it's clean.\n\n`istream_iterator` performs one stream extraction per increment. That's not free, but it's the same cost the equivalent loop would pay. The wrapper is a convenience, not a performance win.","pageType":"cpp"}

Iterators

Get Premium