C++ / ITERATORS, ALGORITHMS, AND RANGES
Begin-end pairs and iterator invalidation rules
Read any C++ range as the half-open pair [begin, end) and predict exactly which iterators, pointers, and references each container operation invalidates.
What you will learn
- Treat end() as a position one past the last element, never as a readable element
- Write erase loops as it = c.erase(it) and advance only on the keep branch
- Predict invalidation from storage: one contiguous buffer vs one node per element
- Call reserve() up front when vector pointers must survive later push_back calls
Understanding Begin-end pairs and iterator invalidation rules
Every algorithm and every hand-written loop in C++ operates on a pair of iterators describing a half-open range, written [first, last): first names an element, last names the position one past the last element and cannot be dereferenced. That asymmetry is what makes the pair cheap to use: last - first is the element count, first == last means empty with no special case, and a loop written with != stops exactly once whether the range holds a million elements or none. c.begin()/c.end() are the member form, std::begin(c)/std::end(c) also work on raw arrays, and cbegin/cend hand back const iterators when you only intend to read.
An iterator is not an owner; it is a handle onto storage the container owns, so invalidation follows directly from how that container stores elements. A vector keeps one contiguous block: growing past capacity allocates a new block and moves everything, killing every iterator, pointer, and reference, while erase shifts the tail left and stales everything from the erase point onward. list, map, and set allocate a node per element, so insertion disturbs nothing and erase only kills handles to the removed element. unordered_map keeps nodes in a bucket array, so a rehash rebuilds that array and invalidates iterators, yet pointers and references to elements survive because the nodes themselves never move.
Because mutation moves the ground under your iterators, the mutating members hand you a fresh one: erase returns the position that followed the removed element, insert returns the position of the new element. A correct filter loop therefore has no ++it in the erase branch; it writes it = v.erase(it) and advances only when the element was kept. Re-evaluate c.end() each time around instead of caching it, and remember that push_back invalidates the past-the-end iterator even when capacity was sufficient, because the position one past the last element has moved.
<iostream>
<vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
// end() is a position, not an element: the distance is the size.
std::cout << "end - begin = " << (v.end() - v.begin())
<< ", size = " << v.size() << '\n';
// Drop even values. erase() returns the position that followed the
// removed element, so advance only when nothing was removed.
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0)
it = v.erase(it);
else
++it;
}
for (int x : v)
std::cout << x << ' ';
std::cout << '\n';
v.reserve(8);
const int* before = v.data();
v.push_back(7); // size stays below capacity: nothing moves
std::cout << "buffer moved: " << (v.data() != before ? "yes" : "no") << '\n';
v.resize(v.capacity()); // now size == capacity
before = v.data();
v.push_back(99); // must allocate a bigger block
std::cout << "buffer moved: " << (v.data() != before ? "yes" : "no") << '\n';
std::cout << "front is still " << v.front() << '\n';
}
A range is the half-open pair [begin, end), and an iterator stays valid only while the container leaves the storage it points at exactly where it is.
Worked examples
A list iterator survives insertion
Shows that node-based containers never relocate existing elements, so only erased positions go stale.
<iostream>
<iterator>
<list>
int main() {
std::list<int> l{10, 20, 30};
auto it = std::next(l.begin()); // names the node holding 20
l.push_front(5);
l.push_back(40);
l.insert(l.begin(), 1);
std::cout << "*it = " << *it << '\n';
auto after = l.erase(it); // destroys only that one node
std::cout << "*after = " << *after << '\n';
for (int x : l)
std::cout << x << ' ';
std::cout << '\n';
}
Example explained
Line 1std::next(l.begin()) yields a handle on the second node, not an index into a block of memory.
Line 2After three insertions *it still prints 20: a list allocates one node per element and leaves existing nodes untouched.
Line 3l.erase(it) invalidates only it and returns the iterator to the following node, so *after prints 30.
Line 4The same guarantee holds for std::map and std::set, which is why you can hold iterators across insertions there.
Half-open windows tile a range
Uses adjacent [first, last) windows to show why end sitting one past the last element removes every edge case.
<iostream>
<vector>
int sum(std::vector<int>::const_iterator first,
std::vector<int>::const_iterator last) {
int total = 0;
for (auto it = first; it != last; ++it)
total += *it;
return total;
}
int main() {
const std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8};
for (auto first = v.begin(); first != v.end(); first += 3) {
auto last = first + 3;
std::cout << '[' << first - v.begin() << ',' << last - v.begin()
<< ") sum " << sum(first, last)
<< " count " << last - first << '\n';
}
auto mid = v.begin() + 4;
std::cout << "first == last: count " << mid - mid
<< ", sum " << sum(mid, mid) << '\n';
}
Example explained
Line 1last = first + 3 is a position, not an element, so each window covers exactly three values and last is the begin of the next window.
Line 2last - first gives the element count directly, which only works because end sits one past the final element.
Line 3The loop advances first to exactly v.end() on the final step, which is legal to form and compare but not to dereference.
Line 4When first == last the body never runs, so sum returns 0 without any empty-range special case.
Rehashing kills iterators, not pointers
Demonstrates the unordered container rule: growing the bucket array invalidates iterators while element addresses stay put.
<iostream>
<string>
<unordered_map>
int main() {
std::unordered_map<int, std::string> m;
m.reserve(4);
m[1] = "one";
std::string* p = &m[1];
auto buckets = m.bucket_count();
for (int i = 2; i <= 100; ++i)
m[i] = "x";
std::cout << "bucket array changed: "
<< (m.bucket_count() != buckets ? "yes" : "no") << '\n';
std::cout << "*p = " << *p << '\n';
std::cout << "same object as m.at(1): "
<< (p == &m.at(1) ? "yes" : "no") << '\n';
}
Example explained
Line 1&m[1] takes the address of the mapped string living inside the node that holds key 1.
Line 2Inserting 99 more pairs pushes the load factor past the default 1.0, so a larger bucket array is allocated; the changed bucket_count is the visible sign.
Line 3The rehash relinks nodes into new buckets without moving them, so *p still reads "one" and p == &m.at(1).
Line 4Any iterator saved before the loop would now be invalid, which is why the second lookup goes through m.at(1) rather than a stored iterator.
Important notes
deque is the case worth memorising separately: inserting at either end keeps references and pointers to existing elements valid but invalidates every iterator, and an insert or erase in the middle invalidates everything.
Algorithms such as std::sort, std::remove, and std::rotate never change a container's size, so they cannot invalidate iterators on their own; it is the erase() call you make afterwards that does.
Common mistakes
Erasing inside a ++it loop: for (auto it = v.begin(); it != v.end(); ++it) if (*it == x) v.erase(it); the erase invalidates it, then ++it advances a dangling iterator, so the loop typically skips the next element or runs off the end.
Caching const auto stop = v.end(); and then inserting or push_back-ing before comparing against stop; after a reallocation stop points into the freed buffer and the comparison it != stop never becomes true, so the loop walks past the new array.
Keeping int& r = v[0]; or int* p = v.data(); across a push_back that grows the vector; reading r or p touches freed memory, and it often prints the right value until the allocator reuses that block.
Try it yourself
Change, predict, then run
Fill a vector<int> with 1 through 10, save int* p = &v[2], then remove every multiple of 3 using a hand-written loop with it = v.erase(it), printing v.end() - v.begin() and *p before and after. Explain why p is still safe to read even though it no longer names the value it started on.
Open the C++ workspaceCheck your understanding
A vector<int> has size 4 and capacity 8. You save int* p = &v[0], auto it = v.begin() + 2, and auto stop = v.end(), then call v.push_back(9). Which statement is true?
- p and it are still usable, but stop is not, because the past-the-end position moved
- All three are invalid, because push_back always allocates a new buffer
- p stays valid while it does not, because iterators are tied to the container's internal version counter
- All three stay valid, since no reallocation can happen while size is below capacity
Show answer
The new size (5) fits in the existing capacity (8), so no reallocation occurs and no element is moved: p and it still refer to live elements. But end() names the position after the last element, and that position shifted by one, so the saved stop is stale. Option 3 is tempting because it gets the no-reallocation part right, yet it overlooks that push_back invalidates the past-the-end iterator regardless of capacity. Option 2 describes unordered containers after a rehash, where nodes stay put but iterators die, not a vector.