--- title: 'Iterators and Validity' source: 'https://academia.sh/en/courses/cpp-standard-library/iterators' course: 'Resource Management and the Standard Library' language: en updated: '2026-09-26T03:02:47+00:00' license: 'CC BY-SA 4.0' objectives: - 'Shows why an iterator to an erased element can never be read again' - 'Distinguishes which container operations invalidate iterators from which do not' - 'Measures that an iterator that is not invalidated stays unchanged after the operation' - 'Recognizes the difference among iterator categories (input, forward, bidirectional, random access)' --- # Iterators and Validity The measurement of how reading an iterator after erase enters undefined behavior, and how an iterator that stays valid remains unchanged. The previous lesson measured that the call `stock["pear"]` inserts a zero-initialized element into the map, and that this **changes** the source. What changed there was the container as a whole: the element count and the map's contents. This lesson brings the boundary down to a smaller unit: an iterator that points to a **single position** inside a container. When an element is deleted, what happens if an iterator that pointed to that element is kept around? The answer to this question differs from container to container — the same `erase` call invalidates every following iterator on a `vector` but affects only the deleted element itself on a `list` — so the question "is this iterator still valid" can only be answered by looking not just at the operation's name but at which container it was called on. ## Reading an Iterator After `erase` `std::vector::erase` removes the element at the given position and shifts every element after it back by one position. The iterator to the removed element is **invalid** after this operation — it either points to memory that no longer belongs to the container, or to a position that another element has since moved into. Reading this iterator is undefined behavior, and this lesson **never runs it**; it only uses the new, valid iterator that `erase` returns. ```cpp // erase-returned-iterator.cpp — which iterator does erase leave valid #include #include int main() { std::vector numbers{10, 20, 30, 40}; auto it = numbers.begin() + 1; // points to 20 auto next = numbers.erase(it); std::printf("element count after erase %zu\n", numbers.size()); std::printf("value at the position erase returned %d\n", *next); return 0; } ``` ```text element count after erase 3 value at the position erase returned 30 ``` **SL7.** After the call `erase(it)`, the variable `it` is no longer valid — this lesson never reads `it` again after the erase, because reading it enters undefined behavior, and undefined behavior is never run in this course. The `next` iterator that `erase` returns is used instead: the standard guarantees that `erase` returns a new, valid iterator pointing to the position after the removed element. The kind of this operation is **unspecified**: what state `it` itself is left in after the operation is not defined by the standard; the only guarantee is that it must not be read. ## Operations That Do Not Invalidate: Iterators That Stay Unchanged Not every mutating operation invalidates iterators. `std::list::erase` invalidates only the iterator to the deleted element — every other iterator keeps its validity, because a linked list does not keep its elements in contiguous memory, and deleting one node does not move the other nodes. ```cpp // list-erase-other-iterators.cpp — what happens to a non-deleted element's iterator #include #include int main() { std::list values{10, 20, 30}; auto middle = std::next(values.begin()); // 20 auto last = std::next(values.begin(), 2); // 30 values.erase(middle); std::printf("value at the untouched iterator %d\n", *last); std::printf("remaining element count %zu\n", values.size()); return 0; } ``` ```text value at the untouched iterator 30 remaining element count 2 ``` **SL8.** The `last` iterator pointed to a node that `erase(middle)` never touched, and it keeps pointing to the same node after the call — its value is still `30`. This iterator's state is **unchanged**: the standard guarantees its validity because it was not the element that was deleted. `std::vector` carries no such guarantee — when an element is deleted from a `vector`, every element after it shifts back by one position, so every iterator to a position after the deleted one also becomes invalid. This difference shows that the choice of container directly affects how iterators can be used. ## Iterator Categories The standard library sorts iterators into categories by functional capacity. An **input iterator** can only read forward, in a single pass. A **forward iterator** supports making more than one pass with the same iterator. A **bidirectional iterator** (such as `std::list`'s iterator) can move both forward and backward, but cannot jump in constant time. A **random access iterator** (such as `std::vector`'s iterator) supports a constant-time jump such as `it + n`. ```cpp // iterator-category.cpp — the difference between random access and bidirectional #include #include #include #include int main() { std::vector v{1, 2, 3, 4, 5}; std::list l{1, 2, 3, 4, 5}; auto vit = v.begin() + 3; // constant-time jump auto lit = std::next(l.begin(), 3); // advances in linear time std::printf("value reached by jumping over the vector %d\n", *vit); std::printf("value reached by advancing over the list %d\n", *lit); return 0; } ``` ```text value reached by jumping over the vector 4 value reached by advancing over the list 4 ``` **SL9.** Both iterators reached the same result, but with different complexity: `v.begin() + 3` is computed in constant time because it is `vector`'s random access iterator; `std::next(l.begin(), 3)` is equivalent to calling `++` three times on `list`'s bidirectional iterator, and advances in linear time. This lesson does not measure the speed difference — duration is never measured in this course — it only shows that the two categories support different operations: writing `it + 3` on a `list` iterator does not compile, because a bidirectional iterator does not provide `operator+`. ## Range-Based `for` and Implicit Iterators A range-based `for` loop calls `begin()` and `end()` behind the scenes, using iterators implicitly. If elements are inserted into or erased from the container inside the loop body, the implicit iterators are subject to the same validity rules — this is why calling `push_back` inside a range-based `for` body over a `vector` can send the rest of the loop into undefined behavior. This lesson never makes such a change. ```cpp // range-for-read-only.cpp — how a range-based for traverses elements #include #include int main() { std::vector numbers{5, 10, 15}; int total = 0; for (int value : numbers) { total += value; } std::printf("total %d\n", total); std::printf("did the element count change %s\n", (numbers.size() == 3) ? "no" : "yes"); return 0; } ``` ```text total 30 did the element count change no ``` **SL10.** The loop only read each element and never wrote to the container; `numbers` stayed **unchanged** at the end of the operation. The implicit `begin()`/`end()` calls stayed valid throughout the loop for the same reason — since the container's size and contents never changed, no situation that would invalidate the iterators ever arose. ## The Difference Between Empty and Unspecified The `end()` iterator and an invalidated iterator are sometimes confused for the same thing; both seem to mark a position that "should not be read." But the standard attaches entirely different guarantees to the two. `end()` is a value that is always defined and open to comparison, denoting the position one past the container's last element — writing `it == container.end()` is valid under every condition, because `end()` itself is never invalid; only **dereferencing** it with `*end()` is undefined. A container is **empty** when `begin() == end()` — this is a defined way of saying "the sought element is not here," and it is also the value `find` returns when it fails to find one. An invalidated iterator, by contrast, is **unspecified**: its value is not even open to comparison, and writing `it == other_it` can itself enter undefined behavior, because the standard makes no guarantee at all about which operations an invalidated iterator supports. This distinction matters because checking a code's **empty** state (`it == end()`) is always safe, but the question "is this iterator still valid" cannot be answered by asking the iterator itself — validity is not information the iterator carries, it is information that must be inferred from the operations the source has gone through. ## `push_back` and Reallocation: The Operation That Affects Every Iterator `erase` only affects positions after the one it targets; `std::vector::push_back` can leave much wider damage. If a `vector`'s allocated capacity is full, `push_back` allocates a new, larger block of memory, moves every existing element there, and frees the old block — in this case, **every** iterator, pointer and reference taken before the insertion is invalidated, not only the ones belonging to the inserted element. If capacity is sufficient, no move happens at all, and existing iterators stay unchanged; but the caller cannot know this in advance without comparing `size()` and `capacity()`. ```cpp // push-back-reallocation.cpp — how push_back affects iterators once capacity is full #include #include int main() { std::vector numbers; numbers.reserve(2); numbers.push_back(1); numbers.push_back(2); bool capacity_was_full = (numbers.size() == numbers.capacity()); numbers.push_back(3); std::printf("was capacity full before the insertion %s\n", capacity_was_full ? "yes" : "no"); std::printf("element count %zu\n", numbers.size()); std::printf("first element %d\n", numbers.front()); return 0; } ``` ```text was capacity full before the insertion yes element count 3 first element 1 ``` **SL11.** The capacity reserved by `reserve(2)` was exactly full once two elements had been inserted; the third `push_back` call therefore moved the `vector` to a new block. Every iterator that might have been taken before capacity was reached would have entered the **unspecified** state once the move completed — this lesson does not hold onto such an iterator and read it after the move, it only reads from the container itself again through `front()`. `front()` returning `1` shows that the elements' values were not affected by the move; what was affected was not the elements' values but the validity of iterators taken to them beforehand. ## Iterator Stability in `std::map` Associative containers resemble `list` far more than `vector` on this point. `std::map` is implemented as a balanced binary search tree, and its elements do not sit in contiguous memory; when a node is inserted or deleted, the other nodes do not change place, only the tree's links are updated. This is why `std::map::erase`, like `std::list::erase`, invalidates only the iterator to the deleted element; every remaining iterator, pointer and reference stays valid. `std::map::insert` carries a similar guarantee: inserting a new node never moves the existing nodes, so no iterator taken before the insertion is invalidated. ```cpp // map-erase-other-iterators.cpp — does map erase affect other iterators #include #include int main() { std::map table{{1, 10}, {2, 20}, {3, 30}}; auto three = table.find(3); table.erase(table.find(1)); std::printf("value at the untouched key %d\n", three->second); std::printf("remaining element count %zu\n", table.size()); return 0; } ``` ```text value at the untouched key 30 remaining element count 2 ``` **SL12.** The iterator belonging to `table.find(1)` was deleted, but `three` pointed to a different key and was not affected by the `erase` call — `three->second` is still `30`. This outcome's kind is the same as its counterpart on `std::list`: **unchanged**. Had the same scenario been set up on `std::vector` — deleting the first of three elements — the iterators to the second and third elements would have been invalidated as the remaining elements shifted back; the fact that they are not invalidated here comes from `map`'s memory layout being fundamentally different from `vector`'s, not from its erase operation being written "more safely." ## Why an Invalid Iterator Is Never Read A line of code that wants to directly read the old iterator belonging to a deleted element, instead of using the iterator `erase` returns, compiles but **cannot be run** — this is undefined behavior that the compiler cannot catch. The block below carries that line only as a comment and explains why it is never run: ```cpp // invalid-iterator-comment.cpp — the reasoning for never reading an invalid iterator #include #include int main() { std::vector numbers{10, 20, 30, 40}; auto it = numbers.begin() + 1; numbers.erase(it); // The line below is undefined behavior and is therefore never run: // std::printf("%d\n", *it); std::printf("element count after erase %zu\n", numbers.size()); return 0; } ``` ```text element count after erase 3 ``` The compiler does not reject the line `*it`, because `it`'s validity is not a type check, it is a runtime contract. Because the standard leaves the behavior of code that violates this contract undefined, the only safe path is to never write that line at all, or never run it — this is the rule applied in every lesson of this course. This also explains why some static analysis tools cannot fully catch this class of bug: an iterator's validity does not live in the iterator's type, it lives in the history of operations the container that produced it has gone through — unless a tool tracks that history, it cannot see that a call that looks valid is in fact reaching an invalidated position. ## The Bounding Measurement The same `erase` call is bounded by the iterator it targets — what happens to the remaining iterators depends on the **container's type**, not on the operation itself. Consider a four-element `std::list`: delete the two middle elements and read the iterators at the ends again: ```cpp title="edge-iterators-remaining.cpp" #include #include #include int main() { std::list numbers{1, 2, 3, 4}; auto first = numbers.begin(); auto last = std::prev(numbers.end()); auto middle_one = std::next(numbers.begin()); auto middle_two = std::next(numbers.begin(), 2); numbers.erase(middle_one); numbers.erase(middle_two); std::printf("%d %d\n", *first, *last); return 0; } ``` ```text title="output" 1 4 ``` `erase(middle_one)` invalidates only the node `middle_one` points to; `first` and `last` are bound to different nodes and are unaffected. The second `erase` call follows the same rule: `middle_two` becomes invalid along with its own node, but this adds nothing to `middle_one`, which was already deleted — `first` and `last` keep showing their pre-operation values **unchanged**. Had the same scenario been built with a `std::vector`, the result would differ: when an element is deleted, every element after it shifts back by one position, so an iterator taken from the end, like `last`, would also be invalidated. What determines the outcome's kind is not the number of deleted elements or where the iterator was taken from, but the container's memory layout: in a node-based structure only the touched node is invalidated, while a deletion in contiguous memory affects every position after it. ## Summary - `std::vector::erase` invalidates the iterator to the deleted element; reading it after the erase is **unspecified** behavior and is never run. The new iterator the call returns is valid and points to the position after the removed element. Bounding measurement: the same operation on a `std::list` invalidates only the node it targets; untouched iterators stay **unchanged** — validity is determined not by the operation but by the container's memory layout. - `std::list::erase` and `std::map::erase`/`insert`, in their node-based structures, invalidate only the iterator to the touched node; every other iterator stays **unchanged** — since memory is not contiguous, no element shifting ever happens. - Iterators fall into input, forward, bidirectional and random access categories; the category determines which operations are supported. - The kind of this lesson's central measurement is **unspecified**: the state of an iterator belonging to an erased element is not defined by the standard, and the only guarantee is that it must never be read again. - `end()` is always a defined, comparable value; a container being **empty** is expressed by `begin() == end()`. This is separate from the **unspecified** state of an invalidated iterator — one says "there is no element here," the other carries no guarantee at all. - `std::vector::push_back`, if capacity is full, invalidates not only the inserted element's iterator but every iterator taken beforehand; if capacity is sufficient, no iterator is affected. This is why it is unsafe to rely on previously taken iterators while calling `push_back` inside a loop over a `vector`. ## Next Step This lesson focused on the validity of a single iterator. The next lesson moves on to standard algorithms that operate over all of a container's elements: how does `std::sort` change a container in place, and which iterators does that change affect?