Iterators and Validity

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.

// erase-returned-iterator.cpp — which iterator does erase leave valid
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> 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;
}

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.

// list-erase-other-iterators.cpp — what happens to a non-deleted element's iterator
#include <cstdio>
#include <list>

int main() {
    std::list<int> 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;
}

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.

// iterator-category.cpp — the difference between random access and bidirectional
#include <cstdio>
#include <iterator>
#include <list>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5};
    std::list<int> 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;
}

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.

// range-for-read-only.cpp — how a range-based for traverses elements
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> 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;
}

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().

// push-back-reallocation.cpp — how push_back affects iterators once capacity is full
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> 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;
}

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.

// map-erase-other-iterators.cpp — does map erase affect other iterators
#include <cstdio>
#include <map>

int main() {
    std::map<int, int> 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;
}

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:

// invalid-iterator-comment.cpp — the reasoning for never reading an invalid iterator
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> 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;
}

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:

#include <cstdio>
#include <iterator>
#include <list>

int main() {
    std::list<int> 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;
}

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?