In the last few chapters we used begin() and end() again and again: to sort a vector, to walk through a map, to call std::find in STL Algorithms. Those calls return iterators. We have been using them like a black box. In this chapter we open the box.
Iterators are the glue of the STL. Containers store data, algorithms process data, and iterators are the common language between them. Because std::find only talks to iterators, the same function works on a vector, a list, a set, an array, or even a file stream. Once you understand iterators properly (what they can do, which kinds exist, and when they become invalid) a lot of STL behaviour stops being "magic" and starts making sense.
What Is an Iterator?
An iterator is an object that points to an element inside a sequence and knows how to move to the next element. It behaves like a generalized pointer:
*itgives the element,++itmoves forward, andit1 == it2checks whether two iterators point to the same position.
Why not just use pointers? A pointer works for an array because the elements sit next to each other in memory, so "next element" simply means "next address". In a std::list, the next element is wherever the current node's next link says. In a std::set, it is the in-order successor in a red-black tree. Each container provides its own iterator class whose ++ does the right thing for that data structure, while the outside looks the same.
Same interface, different machinery behind ++
vector: [10][20][30][40] ++it → address + sizeof(int)
↑
list: [10] ⇄ [20] ⇄ [30] ++it → follow the node's next link
↑
set: (20) ++it → in-order successor in the tree
/ \
(10) (30)
↑The Half-Open Range [begin, end)
Every container gives two iterators:
begin()points to the first element.end()points one past the last element. It is a position, not an element, and must never be dereferenced.
index: 0 1 2 3
[72] [85] [64] [90] [ ]
↑ ↑
begin() end() ← "one past the last", not a real element
Range [begin, end) contains exactly end - begin = 4 elements.
Empty container: begin() == end().This half-open convention is not an accident. It makes the empty range natural (begin == end), makes the element count simply end - begin, and lets loops use it != end as the stopping condition, exactly like i < n in an index loop.
Basic Operations
All iterators support a small common core:
| Expression | Meaning |
|---|---|
*it | The element the iterator refers to (a reference, so you can often modify it) |
it->member | Same as (*it).member, for elements that are objects |
++it / it++ | Move to the next element |
it1 == it2, it1 != it2 | Do they refer to the same position? |
#include <iostream>
#include <vector>
int main() {
std::vector<int> marks = {72, 85, 64, 90};
// it is a std::vector<int>::iterator
for (auto it = marks.begin(); it != marks.end(); ++it) {
std::cout << *it << ' '; // read the element
}
std::cout << '\n';
for (auto it = marks.begin(); it != marks.end(); ++it) {
*it += 5; // write through the iterator
}
auto first = marks.begin();
auto last = marks.end() - 1; // end() itself must not be dereferenced
std::cout << "first = " << *first << ", last = " << *last << '\n';
std::cout << "size via iterators = " << (marks.end() - marks.begin()) << '\n';
}Output:
72 85 64 90
first = 77, last = 95
size via iterators = 4Notice three things. Writing *it += 5 changed the elements in the vector, because *it is a reference to the real element. We got the last element with end() - 1, not end(). And subtracting two vector iterators gives the distance between them, just like subtracting two pointers.
Prefer ++it over it++ in loops. For a class-type iterator, postfix it++ has to make a copy of the old iterator to return it. With optimization the compiler usually removes the copy, but ++it never needs it in the first place.
Range-Based for Is Iterators in Disguise
The range-based for loop you know from earlier chapters is defined by the standard in terms of iterators. The compiler rewrites
for (int x : marks) { /* body */ }into roughly
{
auto&& range = marks;
auto it = range.begin(); // or begin(range) for arrays and other types
auto end = range.end();
for (; it != end; ++it) {
int x = *it;
/* body */
}
}So any type that has begin() and end() returning something with *, ++ and != works in a range-for. We will use this at the end of the chapter to write our own iterable class. Note that end() is computed once, before the loop starts. That detail matters for iterator invalidation, as we will see.
const, Reverse and const-Reverse Iterators
Each standard container provides four flavours of iterator:
| Functions | Type | Direction | Can modify element? |
|---|---|---|---|
begin(), end() | iterator | forward | yes |
cbegin(), cend() | const_iterator | forward | no |
rbegin(), rend() | reverse_iterator | backward | yes |
crbegin(), crend() | const_reverse_iterator | backward | no |
A const_iterator is to an iterator what const int* is to int*: the iterator itself can move, but the element it refers to is read-only. Calling begin() on a const container also gives a const_iterator. Use the c versions whenever you only read; the compiler then stops you from modifying data by accident.
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> names = {"Asha", "Ravi", "Meena"};
// const_iterator: read-only access
for (auto it = names.cbegin(); it != names.cend(); ++it) {
std::cout << *it << " has " << it->size() << " letters\n";
// *it = "X"; // error: cannot assign through a const_iterator
}
// reverse_iterator: ++ moves backwards
std::cout << "Reversed: ";
for (auto it = names.rbegin(); it != names.rend(); ++it) {
std::cout << *it << ' ';
}
std::cout << '\n';
// base() converts a reverse_iterator back to a normal iterator
auto r = names.rbegin(); // refers to "Meena"
auto f = r.base(); // refers to one past "Meena", i.e. end()
std::cout << std::boolalpha << (f == names.end()) << '\n';
}Output:
Asha has 4 letters
Ravi has 4 letters
Meena has 5 letters
Reversed: Meena Ravi Asha
true rend() rbegin()
↓ ↓
[ ][Asha][Ravi][Meena][ ]
↑ ↑
begin() end()
A reverse_iterator stores a normal iterator (its base()) and dereferences
the element just BEFORE it. rbegin().base() == end(), rend().base() == begin()This "one before" rule explains why r.base() was equal to end() even though *r was "Meena". It matters when you want to erase using a reverse iterator: you must erase std::prev(r.base()), not r.base().
Note that std::unordered_set, std::unordered_map and std::forward_list have no reverse iterators, because their iterators cannot move backwards. That brings us to the most important idea of this chapter.
Iterator Categories
Not every iterator can do everything. A vector iterator can jump 1000 positions in one step; a list iterator has to follow 1000 links. The STL groups iterators into categories according to the operations they support efficiently:
| Category | Adds these operations | Example |
|---|---|---|
| Input | *it (read), ++it; single pass only | std::istream_iterator |
| Output | *it = value (write), ++it; single pass only | std::ostream_iterator, std::back_inserter |
| Forward | Input + multi-pass (you can save a copy and walk again) | std::forward_list, unordered_* |
| Bidirectional | Forward + --it | std::list, set, map |
| Random access | Bidirectional + it + n, it - n, it[n], it2 - it1, <, >, all in O(1) | std::deque |
| Contiguous (C++20) | Random access + elements are adjacent in memory | std::vector, std::array, std::string, raw pointers |
Each category is a superset of the one above it (output iterators are a separate branch). An algorithm states the minimum category it needs. For example:
std::find,std::count,std::accumulateneed only input iterators: they walk once from left to right.std::reverseneeds bidirectional iterators: it walks from both ends.std::sortandstd::nth_elementneed random access iterators: they jump around.std::binary_searchandstd::lower_boundaccept forward iterators, but they make O(log n) comparisons and O(n) iterator steps on non-random-access iterators. So on alistthey are not really fast.
This is why std::sort(myList.begin(), myList.end()) does not compile, and why std::list has its own member function myList.sort() (a merge sort that relinks nodes).
Moving Iterators Generically: advance, next, prev, distance
The header <iterator> provides helper functions that work for every category and automatically pick the fastest way:
| Function | Does | Cost (random access) | Cost (others) |
|---|---|---|---|
std::advance(it, n) | Moves it itself by n (negative n needs bidirectional) | O(1) | O(|n|) |
std::next(it, n) (C++11) | Returns a copy moved forward by n (default 1) | O(1) | O(n) |
std::prev(it, n) (C++11) | Returns a copy moved backward by n; needs bidirectional | O(1) | O(n) |
std::distance(a, b) | Number of steps from a to b | O(1) | O(n) |
#include <forward_list>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>
int main() {
std::vector<int> v = {10, 20, 30, 40, 50};
std::list<int> l = {10, 20, 30, 40, 50};
auto vi = v.begin() + 3; // random access: jump directly, O(1)
std::cout << "*vi = " << *vi << ", vi[1] = " << vi[1]
<< ", vi - v.begin() = " << (vi - v.begin()) << '\n';
// auto li = l.begin() + 3; // error: list iterators are only bidirectional
auto li = std::next(l.begin(), 3); // walks 3 steps, O(n)
std::cout << "4th list element: " << *li << '\n';
std::cout << "one before it: " << *std::prev(li) << '\n';
std::advance(li, -2); // bidirectional: may move backwards
std::cout << "after advance(-2): " << *li << '\n';
std::cout << "distance(begin, li) = " << std::distance(l.begin(), li) << '\n';
std::forward_list<int> fl = {1, 2, 3};
auto fi = fl.begin();
++fi; // forward only: no --fi, no std::prev
std::cout << "forward_list second: " << *fi << '\n';
}Output:
*vi = 40, vi[1] = 50, vi - v.begin() = 3
4th list element: 40
one before it: 30
after advance(-2): 20
distance(begin, li) = 1
forward_list second: 2The commented line l.begin() + 3 would be a compile error. The STL deliberately does not give list iterators a + operator, so that an O(n) operation never hides behind syntax that looks O(1). std::next is allowed, because its documentation clearly says it is linear for non-random-access iterators.
Checking Categories with C++20 Concepts
C++20 added iterator concepts in <iterator> such as std::input_iterator, std::forward_iterator, std::bidirectional_iterator, std::random_access_iterator and std::contiguous_iterator. They are compile-time true/false tests (we use them here with if constexpr from the Templates chapter):
#include <deque>
#include <forward_list>
#include <iostream>
#include <iterator>
#include <list>
#include <set>
#include <vector>
template <typename It>
void describe(const char* name) {
std::cout << name << ": ";
if constexpr (std::contiguous_iterator<It>) std::cout << "contiguous\n";
else if constexpr (std::random_access_iterator<It>) std::cout << "random access\n";
else if constexpr (std::bidirectional_iterator<It>) std::cout << "bidirectional\n";
else if constexpr (std::forward_iterator<It>) std::cout << "forward\n";
else if constexpr (std::input_iterator<It>) std::cout << "input\n";
else std::cout << "output only\n";
}
int main() {
describe<std::vector<int>::iterator>("vector");
describe<int*>("raw pointer");
describe<std::deque<int>::iterator>("deque");
describe<std::list<int>::iterator>("list");
describe<std::set<int>::iterator>("set");
describe<std::forward_list<int>::iterator>("forward_list");
describe<std::istream_iterator<int>>("istream_iterator");
describe<std::ostream_iterator<int>>("ostream_iterator");
}Output:
vector: contiguous
raw pointer: contiguous
deque: random access
list: bidirectional
set: bidirectional
forward_list: forward
istream_iterator: input
ostream_iterator: output onlyBefore C++20 the category was expressed with "tag" types like std::random_access_iterator_tag, available through std::iterator_traits<It>::iterator_category. You will still see tags in older code and in custom iterators (we use one below), but concepts give much clearer error messages.
Iterator Adaptors: Inserters and Stream Iterators
Algorithms like std::copy and std::transform write through an output iterator, overwriting existing elements. They never grow a container by themselves. Writing into an empty vector with std::copy(src.begin(), src.end(), dest.begin()) is undefined behaviour, because dest has no elements to overwrite.
An insert iterator solves this: it is an output iterator whose assignment *it = value calls an insertion function on the container.
| Adaptor | *it = x becomes | Works with |
|---|---|---|
std::back_inserter(c) | c.push_back(x) | vector, deque, list, string |
std::front_inserter(c) | c.push_front(x) | deque, list, forward_list |
std::inserter(c, pos) | c.insert(pos, x), then moves past the new element | any container with insert, including set/map |
Stream iterators treat a stream as a sequence. An std::ostream_iterator<T>(out, sep) prints each value assigned to it followed by sep. An std::istream_iterator<T>(in) reads values with >>; a default-constructed std::istream_iterator<T>() is the "end of stream" iterator.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <set>
#include <sstream>
#include <vector>
int main() {
std::vector<int> src = {5, 3, 8, 1};
// back_inserter: every assignment becomes push_back
std::vector<int> doubled;
std::transform(src.begin(), src.end(), std::back_inserter(doubled),
[](int x) { return x * 2; });
// front_inserter: every assignment becomes push_front (order reverses)
std::list<int> lst;
std::copy(src.begin(), src.end(), std::front_inserter(lst));
// inserter: every assignment becomes insert (works for set too)
std::set<int> s;
std::copy(src.begin(), src.end(), std::inserter(s, s.end()));
// ostream_iterator: every assignment prints the value and a separator
std::ostream_iterator<int> out(std::cout, " ");
std::copy(doubled.begin(), doubled.end(), out); std::cout << '\n';
std::copy(lst.begin(), lst.end(), out); std::cout << '\n';
std::copy(s.begin(), s.end(), out); std::cout << '\n';
// istream_iterator: reads values until the stream ends or fails
std::istringstream input("4 9 16 25");
std::vector<int> nums{std::istream_iterator<int>(input),
std::istream_iterator<int>()};
std::cout << "read " << nums.size() << " numbers, last = " << nums.back() << '\n';
}Output:
10 6 16 2
1 8 3 5
1 3 5 8
read 4 numbers, last = 25The front_inserter line printed 1 8 3 5: each new element was pushed to the front, so the order reversed. The set printed sorted values because the set itself keeps order; inserter just calls insert. The last part built a vector directly from a stream with the iterator-pair constructor, which you can use with std::cin as well.
Iterator Invalidation
This is the topic interviewers love, and the source of many real crashes.
An iterator is invalidated when the element or memory it refers to has been moved or destroyed by a change to the container. Using an invalidated iterator (dereferencing, incrementing or comparing it) is undefined behaviour. The same applies to pointers and references to elements.
Why does it happen? Remember from the vector chapter that a vector stores its elements in one heap block with some spare capacity. When push_back finds no room, it allocates a bigger block, moves the elements there and frees the old block. Every iterator, pointer and reference into the old block is now dangling.
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3};
std::cout << "capacity = " << v.capacity() << std::endl; // endl flushes before the crash
auto it = v.begin(); // points into the current buffer
v.push_back(4); // size would exceed capacity: reallocation!
std::cout << *it << '\n'; // undefined behavior: it points to freed memory
}Compiled with -fsanitize=address, AddressSanitizer catches the bug (output trimmed; addresses and the process number vary):
capacity = 3
=================================================================
==1045==ERROR: AddressSanitizer: heap-use-after-free on address 0x7bacb31e0010 ...
READ of size 4 at 0x7bacb31e0010 thread T0
#0 ... in main invalid_asan.cpp:9Without the sanitizer the program may print 1, print garbage, or crash. That is what "undefined" means: there is no guaranteed wrong answer, which is exactly why such bugs survive testing. Calling v.reserve(4) before taking the iterator would have avoided the reallocation in this specific case, but the general fix is: re-obtain iterators after modifying a container.
Invalidation Rules for Standard Containers
| Container | Insertion | Erasure |
|---|---|---|
vector, string | If reallocation happens: all iterators, pointers and references invalid. Otherwise: those at or after the insertion point (including end()) | Those at or after the erased position (including end()) |
deque | At either end: all iterators invalid, but pointers and references stay valid. In the middle: everything invalid | At either end: only the erased elements (erasing the last element also invalidates end()). In the middle: everything invalid |
list, forward_list | Nothing invalidated | Only iterators to the erased elements |
set, map, multiset, multimap | Nothing invalidated | Only iterators to the erased elements |
unordered_set, unordered_map and multi versions | If a rehash happens: all iterators invalid (references and pointers stay valid). Otherwise nothing | Only iterators to the erased elements |
The pattern is easy to remember if you think about the data structure. Node-based containers (list, trees, hash table nodes) never move existing nodes, so their elements stay put. Array-based containers (vector, deque's internal map) shift or reallocate memory, so iterators go stale. Container adaptors such as stack and queue have no iterators at all.
Erasing While Iterating
The classic bug is erasing inside a loop and then doing ++it on the erased iterator:
for (auto it = v.begin(); it != v.end(); ++it)
if (*it % 2 == 0)
v.erase(it); // WRONG: it is now invalid, and ++it is undefined behaviourEvery container's erase returns an iterator to the element that followed the erased one. Use that return value, and only increment when you did not erase:
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
// Correct: erase returns an iterator to the element after the erased one
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0)
it = v.erase(it); // do NOT ++it here
else
++it;
}
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
// C++20: one line, and O(n) instead of O(n^2)
std::vector<int> w = {1, 2, 3, 4, 5, 6, 7, 8};
auto removed = std::erase_if(w, [](int x) { return x % 2 == 0; });
std::cout << "removed " << removed << ", left: ";
for (int x : w) std::cout << x << ' ';
std::cout << '\n';
}Output:
1 3 5 7
removed 4, left: 1 3 5 7 The loop version is correct but O(n²) for a vector in the worst case, because every erase shifts all later elements left. C++20 added the free functions std::erase_if (for every standard container except std::array, whose size is fixed) and std::erase (for sequence containers such as vector, deque, list and string). For a vector they use the erase–remove idiom you saw in STL Algorithms, which is a single O(n) pass, and they return how many elements were removed. Prefer them when you have C++20.
Also never modify a container's size inside a range-based for over that same container. The hidden end was computed before the loop, so after a push_back or erase both the hidden iterator and end may be invalid.
Writing Your Own Iterator
To make your own class work with range-for and with STL algorithms, give it begin() and end() that return an iterator type. A minimal forward iterator needs:
operator*, prefix and postfixoperator++, andoperator==(C++20 generates!=from==, as you saw in Operator Overloading).A default constructor and copying (the compiler-generated ones are fine here).
The member types
value_typeanddifference_type, plus a category tag:iterator_categoryfor pre-C++20 code and (optionally)iterator_conceptfor the C++20 concepts.
Here is an iterable range of numbers with a step, similar in spirit to Python's range(0, 18, 5). It does not store any numbers; the iterator computes them on the fly.
#include <cstddef>
#include <iostream>
#include <iterator>
#include <numeric>
// The numbers first, first+step, first+2*step, ... that are less than last
class StepRange {
int first_, last_, step_;
public:
StepRange(int first, int last, int step) : first_(first), last_(last), step_(step) {}
class iterator {
int value_ = 0;
int step_ = 1;
public:
// Member types that algorithms and std::iterator_traits look for
using iterator_concept = std::forward_iterator_tag; // read by C++20 concepts
using iterator_category = std::input_iterator_tag; // read by pre-C++20 code (see below)
using value_type = int;
using difference_type = std::ptrdiff_t;
iterator() = default; // forward iterators must be default-constructible
iterator(int v, int s) : value_(v), step_(s) {}
int operator*() const { return value_; } // a computed value, returned by value
iterator& operator++() { value_ += step_; return *this; } // prefix
iterator operator++(int) { iterator old = *this; ++*this; return old; } // postfix
bool operator==(const iterator&) const = default; // C++20; != is generated
};
iterator begin() const { return {first_, step_}; }
iterator end() const {
// number of values in the range, so that end() is reached exactly
int count = (last_ - first_ + step_ - 1) / step_;
return {first_ + count * step_, step_};
}
};
static_assert(std::forward_iterator<StepRange::iterator>); // checked at compile time
int main() {
StepRange r(0, 18, 5);
for (int x : r) std::cout << x << ' '; // range-for needs only begin() and end()
std::cout << '\n';
std::cout << "sum = " << std::accumulate(r.begin(), r.end(), 0) << '\n';
std::cout << "count = " << std::distance(r.begin(), r.end()) << '\n';
}Output:
0 5 10 15
sum = 30
count = 4The static_assert line asks the compiler to prove that our type satisfies the C++20 std::forward_iterator concept. If we forgot, say, the postfix ++ or the default constructor, compilation would fail with a message pointing at the missing requirement. Because it qualifies, std::accumulate and std::distance from the standard library work with it unchanged. This is the power of the iterator abstraction: write one iterator, and dozens of algorithms come for free.
Why does operator* return int and not const int&? Our range stores no numbers, so there is no element that a reference could refer to. Returning a reference to the iterator's own member value_ (a so-called "stashing" iterator) compiles, but that reference dies with the iterator, and the standard requires references obtained from a forward iterator to stay valid as long as the range exists. So we return by value. The pre-C++20 rules, however, insist that a forward iterator's operator* return a real reference, so for older code we honestly advertise only std::input_iterator_tag. C++20 relaxed that rule: the iterator_concept member tells the C++20 concepts that the iterator really is multi-pass, which the static_assert confirms. The standard library's own std::views::iota (C++20) uses exactly this combination.
The old way of writing iterators was to inherit from std::iterator<...>. That helper was deprecated in C++17; declare the member types yourself as above.
Iterators vs Indexes vs Pointers
Index v[i] | Raw pointer | Iterator | |
|---|---|---|---|
Works on vector/array | Yes | Yes | Yes |
Works on list, set, map | No | No | Yes |
| Works with STL algorithms | No | Yes (a pointer is a contiguous iterator) | Yes |
| Survives vector reallocation | Yes (index still meaningful) | No | No |
| Bounds-checked option | v.at(i) | No | Only in debug modes (e.g. -D_GLIBCXX_DEBUG) |
That "survives reallocation" row is a useful trick: if you must keep a position in a vector while pushing new elements, store the index instead of an iterator.
Common Mistakes
1. Dereferencing end()
*v.end() is undefined behaviour. Also check search results before using them: auto it = std::find(...); if (it != v.end()) use(*it);. On an empty container, even *v.begin() is undefined, because begin() == end().
2. Using an iterator after the container changed
Saving auto it = v.begin();, then calling push_back, insert or erase, then using it. Check the invalidation table, or simply get a fresh iterator.
3. Mixing iterators from different containers
std::sort(a.begin(), b.end()) compiles if a and b have the same type, but it is undefined behaviour: both iterators of a range must come from the same container. This also happens with temporaries: std::sort(getVec().begin(), getVec().end()) calls the function twice and gets two different vectors.
4. Using + on a non-random-access iterator
myList.begin() + 2 and mySet.begin() + 2 do not compile. Use std::next(it, 2), and remember it is O(n) there.
5. Ignoring the return value of erase
Doing v.erase(it); ++it; instead of it = v.erase(it);. Same for map and set (their erase(iterator) has returned the next iterator since C++11).
6. Expecting std::copy to grow the destination
Copying into an empty vector through dest.begin() writes past the end. Use std::back_inserter(dest), or dest.resize(n) first.
Interview / GATE-Style Questions
Q1. Why is end() one past the last element instead of pointing to the last element?
A half-open range [begin, end) represents an empty container naturally (begin == end), gives the element count as end - begin, and allows the simple loop condition it != end. If end pointed to the last element, an empty container would need a special case and loops would need <=, which forward-only iterators cannot even evaluate.
Q2. Why can't you call std::sort on a std::list? How do you sort a list?
std::sort requires random access iterators (it jumps to arbitrary positions, e.g. for partitioning), and list iterators are only bidirectional. Use the member function lst.sort(), which is a merge sort that relinks nodes in O(n log n) without moving element values.
Q3. A vector has size 3 and capacity 4. You hold an iterator to element 0 and an iterator to element 2, then insert at position 1. Which iterators are still valid?
No reallocation happens (size becomes 4, which fits the capacity), so iterators before the insertion point stay valid. The iterator to element 0 is valid; the iterator to element 2 is invalidated (elements at or after the insertion point were shifted). If the capacity had been 3, both would be invalid because of reallocation.
Q4. Does inserting into a std::map invalidate an iterator you are holding? What about std::unordered_map?
std::map: no, insertion never invalidates iterators or references (tree nodes do not move). std::unordered_map: iterators are invalidated if the insertion causes a rehash; references and pointers to elements remain valid even then.
Q5. What is the output? std::vector<int> v{1,2,3,4}; auto r = v.rbegin(); ++r; std::cout << *r << ' ' << *(r.base());
It prints 3 4. rbegin() refers to 4; after ++r it refers to 3. Its base() is the normal iterator one position to the right of the referred element, which is the iterator to 4.
Q6. What is the time complexity of std::distance(first, last) for a std::set? For a std::vector?
For set (bidirectional iterators) it is O(n): it must step through each element. For vector (random access) it is O(1): it just computes last - first.
Summary
An iterator is a generalized pointer:
*itreads or writes the element,++itadvances,==/!=compare positions.Containers expose the half-open range
[begin(), end());end()must never be dereferenced. Range-based for is rewritten into an iterator loop.Use
cbegin/cendfor read-only access andrbegin/rendto walk backwards.Categories: input, output, forward, bidirectional, random access, contiguous (C++20). Algorithms state the minimum they need;
std::sortneeds random access.std::advance,next,prevanddistanceare O(1) for random access iterators and O(n) otherwise.Inserters (
back_inserter,front_inserter,inserter) let algorithms grow containers; stream iterators connect algorithms to I/O.Know the invalidation rules: vector reallocation invalidates everything; node-based containers only invalidate erased elements. Use
it = c.erase(it)or C++20std::erase_if.A custom iterator needs
*, both++,==and a few member types (including a category tag); then range-for and STL algorithms work with your class.
In several examples we passed small functions like [](int x) { return x * 2; } to algorithms. In the next chapter, Lambda Expressions, we learn exactly how these work: captures, return types, generic lambdas and more.