AdvancedC++ Programming · Lesson 17 of 17 · Updated ·
Iterators in C++ — begin and end, Iterator Categories and Iterator Invalidation
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().
#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;
}
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.
#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;
}
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*itbut 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 aheadprev(it, n)— n steps back (bidirectional or better)advance(it, n)— moveititself n stepsdistance(a, b)— number of steps from a to b
#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;
}
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:
// 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:
#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;
}
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.
| 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
++iton the erased iterator. - Keeping an iterator, pointer or reference into a vector across
push_back. - Calling
sorton alist(needs random access); uselist::sort(). - Comparing iterators from two different containers — the result is meaningless.
- Using
it < v.end()with alistormapiterator; 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).*itreads the element,it->xreads a member,++itmoves on;autosaves typing.rbegin/rendwalk backwards;cbegin/cendare read-only.- Categories: input/output, forward, bidirectional, random access. Algorithms need a minimum category.
next,prev,advance,distancework 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.