# Iterators in C++ — begin and end, Iterator Categories and Iterator Invalidation

Source: https://skills101.in/learn/cpp/cpp-iterators — Skills101 free tutorial (C++ Programming). Updated 2026-11-21.

In the STL lessons you wrote `sort(v.begin(), v.end())` many times. What exactly are `begin()` and `end()`? They return **iterators**. An iterator is an object that **points to an element** of a container and can **move to the next one**. Iterators are the glue of the STL: algorithms like `sort`, `find` and `accumulate` never touch a container directly — they only see a pair of iterators. That is why one `find` works on a `vector`, a `list` and a `set`. Understanding iterators also prevents one of the most common C++ bugs: using an iterator after the container has changed.

## 1. begin, end and the basic loop

An iterator behaves much like a pointer:

| Operation | Meaning |
|---|---|
| `*it` | the element it points to |
| `it->member` | a member of that element (same as `(*it).member`) |
| `++it` | move to the next element |
| `it1 == it2`, `it1 != it2` | do they point to the same position? |

`v.begin()` points to the **first** element. `v.end()` points **one past the last** element — it is a stop marker, not an element, and must never be dereferenced. For an empty container, `begin() == end()`.

![A vector of five marks with begin pointing at index 0 and end pointing one position past the last element at index 5; the range from begin to end covers all five elements](https://skills101.in/learn-img/cpp/begin-end.svg)

```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> marks = {72, 85, 64, 90, 58};
    for (vector<int>::iterator it = marks.begin(); it != marks.end(); ++it)
        cout << *it << " ";
    cout << "\n";

    for (auto it = marks.begin(); it != marks.end(); ++it)
        *it += 5;                                   // grace marks: change through the iterator

    for (int m : marks) cout << m << " ";           // range-based for uses begin/end inside
    cout << "\n";
    cout << "count: " << (marks.end() - marks.begin()) << "\n";
    return 0;
}
```

```text
72 85 64 90 58 
77 90 69 95 63 
count: 5
```

Writing `vector<int>::iterator` is long, so code usually says `auto`. The **range-based for** loop `for (int m : marks)` is shorthand: the compiler turns it into the iterator loop above. Use the range-based for when you visit every element; use iterators when you need the position itself (to erase, insert, or compare with another position).

The half-open range **[begin, end)** — start included, end excluded — is used everywhere in C++. It makes the number of elements simply `end - begin`, and an empty range simply `begin == end`.

## 2. The same loop on every container

Every STL container has `begin()` and `end()`, so the same pattern works on all of them. For a `map`, each element is a `pair`, so `it->first` is the key and `it->second` is the value.

```cpp
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main() {
    map<string, int> stock = {{"pen", 40}, {"book", 12}, {"bag", 5}};
    for (auto it = stock.begin(); it != stock.end(); ++it)
        cout << it->first << "=" << it->second << " ";
    cout << "\n";

    set<int> rolls = {104, 101, 103};
    for (auto it = rolls.rbegin(); it != rolls.rend(); ++it)   // reverse iterators
        cout << *it << " ";
    cout << "\n";

    vector<int> v = {3, 1, 4};
    for (auto it = v.cbegin(); it != v.cend(); ++it)           // const: read-only
        cout << *it;
    cout << "\n";
    return 0;
}
```

```text
bag=5 book=12 pen=40 
104 103 101 
314
```

- `rbegin()` / `rend()` give **reverse iterators**: `++` moves backwards.
- `cbegin()` / `cend()` give **const iterators**: you can read `*it` but not assign to it. Use them when a loop should not change anything; the compiler then catches accidental writes.

## 3. Iterator categories

Not every iterator can do everything. A `vector` stores elements next to each other, so its iterator can jump `it + 3` in one step. A `list` is a chain of nodes, so its iterator can only step one node at a time. The STL groups iterators into **categories** by what they can do:

| Category | Extra operations | Containers |
|---|---|---|
| Input / Output | read once / write once, `++` | `istream`, `ostream` iterators |
| Forward | `++`, read many times | `forward_list`, `unordered_map`, `unordered_set` |
| Bidirectional | `++` and `--` | `list`, `set`, `map` |
| Random access | `+ n`, `- n`, `it2 - it1`, `<`, `it[n]` | `vector`, `deque`, `string`, arrays |

Each category can do everything the ones above it can. Algorithms state what they need. `sort` needs **random access**, so `sort(myList.begin(), myList.end())` does not compile; `list` has its own member `myList.sort()` instead.

To move any iterator, use the helpers from `<iterator>`, which work for every category:

- `next(it, n)` — a new iterator n steps ahead
- `prev(it, n)` — n steps back (bidirectional or better)
- `advance(it, n)` — move `it` itself n steps
- `distance(a, b)` — number of steps from a to b

```cpp
#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main() {
    list<char> queue = {'A', 'B', 'C', 'D', 'E'};
    auto it = next(queue.begin(), 2);                // list has no it + 2
    cout << *it << "\n";
    advance(it, 1);
    cout << *it << " is at position " << distance(queue.begin(), it) << "\n";
    cout << *prev(queue.end()) << "\n";              // last element
    return 0;
}
```

```text
C
D is at position 3
E
```

For a `vector`, `next` and `distance` take one step; for a `list`, they walk node by node, so they cost O(n). The code looks the same, but the speed does not.

## 4. Erasing while looping

Suppose we must remove every failing mark (below 40) from a vector. The obvious loop is **wrong**:

```cpp
// WRONG: after erase(it), 'it' is invalid, and ++it is undefined behaviour
for (auto it = v.begin(); it != v.end(); ++it)
    if (*it < 40) v.erase(it);
```

`erase` removes the element and shifts the later elements left. The iterator `it` now refers to a position that has been destroyed — it is **invalidated**. Using it again is undefined behaviour: it may skip elements, crash, or seem to work and fail later.

The fix: `erase` **returns** an iterator to the element after the removed one. Use it, and only do `++it` when you did not erase:

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {35, 72, 20, 18, 66, 39};
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it < 40) it = v.erase(it);     // erase returns the next valid iterator
        else ++it;
    }
    for (int m : v) cout << m << " ";
    cout << "\n";

    vector<int> w = {35, 72, 20, 18, 66, 39};
    w.erase(remove_if(w.begin(), w.end(), [](int m) { return m < 40; }), w.end());
    for (int m : w) cout << m << " ";
    cout << "\n";
    return 0;
}
```

```text
72 66 
72 66 
```

The second version is the **erase–remove idiom**. `remove_if` moves the elements to keep to the front and returns an iterator to the new logical end; `erase` then chops off the leftovers. It does the job in one pass, O(n), while erasing one by one from a vector can be O(n²) because each `erase` shifts the rest.

## 5. Iterator invalidation rules

Erasing is not the only danger. Any change to a container may invalidate iterators (and pointers and references) into it. The most important case: when a `vector` runs out of capacity, `push_back` moves **all** elements to a new, bigger block of memory, and every old iterator now points to freed memory.

![Table of iterator invalidation: vector push_back invalidates all iterators when it reallocates, vector erase invalidates from the erased element onward, list and map insert invalidate nothing and erase invalidates only the erased element](https://skills101.in/learn-img/cpp/invalidation.svg)

| Container | Insert | Erase |
|---|---|---|
| `vector`, `string` | all, if it reallocates; otherwise those after the insert point | the erased element and everything after it |
| `deque` | all iterators (in the middle: also references) | at either end: only the erased element; in the middle: all |
| `list`, `set`, `map` | none | only the erased element |
| `unordered_map`, `unordered_set` | all, if it rehashes | only the erased element |

The practical rule: **after changing a container, do not reuse old iterators** unless you are sure the rules allow it. Get a fresh iterator, use the one returned by `erase`/`insert`, or, for a vector, call `reserve()` first if you know the final size.

## Common mistakes

- Dereferencing `end()`. It is one past the last element, not the last element.
- Erasing inside a loop and then doing `++it` on the erased iterator.
- Keeping an iterator, pointer or reference into a vector across `push_back`.
- Calling `sort` on a `list` (needs random access); use `list::sort()`.
- Comparing iterators from two different containers — the result is meaningless.
- Using `it < v.end()` with a `list` or `map` iterator; use `!=`, which works for every category.

## Quick recap

- `begin()` is the first element, `end()` is one past the last: the half-open range [begin, end).
- `*it` reads the element, `it->x` reads a member, `++it` moves on; `auto` saves typing.
- `rbegin/rend` walk backwards; `cbegin/cend` are read-only.
- Categories: input/output, forward, bidirectional, random access. Algorithms need a minimum category.
- `next`, `prev`, `advance`, `distance` work for every iterator.
- Erase in a loop with `it = v.erase(it)`, or use erase–remove.
- Changing a container can invalidate iterators; vector reallocation invalidates all of them.


Practice quiz and free certificate: https://skills101.in/learn/cpp/cpp-iterators