Iterators are an important component of the STL. They act like a “navigator” for containers, allowing you to accurately traverse each element, whether you are dealing with a vector, list, or map. Learning STL requires mastering the basic usage of iterators, so let’s take a look.
What exactly is an iterator?
To illustrate, when you go to a library to find a book, you don’t need to know the exact location of the book in the storage; you just need to use the shelf number and the retrieval system to find your target. An iterator plays a similar role—it allows us to access elements in a container without needing to understand the internal storage structure of the container.
An iterator is essentially ageneralized pointer abstraction, which defines the access and traversal operations for container elements. It implements auniversal mechanism for accessing container elements
Why do we need iterators? If you have written C code, you know that different data structures like arrays, linked lists, trees, and graphs each have their own traversal methods. Moreover, the more complex the data structure, the more complicated the traversal algorithm becomes.
The emergence of iterators allows us to traverse all containers using the same logic, whether you are dealing with a contiguous memory<span>vector</span>, a doubly linked list<span>list</span>, or other complex containers. Iterators can mask the differences in underlying implementations, allowing you to easily navigate between elements using the same<span>++</span> and <span>*</span> operations.
This is also the core design philosophy of the STL (Standard Template Library)—to separate data storage from algorithms, which is the essence of C++ generic programming..
The Core Role of Iterators: Bridging Containers and Algorithms
The most critical value of iterators lies instandardizing traversal logic, achieving a decoupled design between containers and algorithms. STL algorithms never directly operate on containers; instead, they access elements indirectly through iterators—this means that the same<span>sort</span> sorting algorithm can handle both<span>vector</span>‘s contiguous memory data and<span>list</span>‘s linked list nodes, and even custom containers.
Its core functions can be summarized in three points:
- Traversing containers supports moving forward (
<span>++it</span>), backward (<span>--it</span>, for some iterators), or random access, making it easy to traverse element sequences; - Unified interface all STL containers provide
<span>begin()</span>(starting iterator) and<span>end()</span>(ending iterator), forming the standard range for algorithm operations<span>[begin, end)</span>; - Generalized reuse universal algorithms (such as
<span>for_each</span>and<span>find</span>) can be reused across container types through the iterator interface, significantly reducing development costs.
Let’s look at a simple example.
#include <iostream>
#include <vector>
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
// Use iterator to traverse vector
for (auto it = nums.begin(); it != nums.end(); ++it) {
std::cout << *it << " "; // Access elements like pointers
}
// Output: 1 2 3 4 5
return 0;
}The above code demonstrates the basic usage of iterators, which can be seen as very similar to pointers. However, iterators are more powerful and safer than pointers, as they automatically adapt to the best access method based on the container type.
Differences Between Iterators and Pointers
From the above example, we can see that the operations of iterators and pointers are very similar, both allowing the use of *, ++, and — operations. However, they are fundamentally different. Let’s examine the essential differences between the two from two dimensions:
1. Essential Positioning: “Abstract Interface” VS “Memory Address”
- Pointers are a direct mapping to the underlying hardware, essentially a “variable that stores a memory address”; it only knows the “address” and does not know “which container the data behind the address belongs to.”
- Iterators are “container-specific access interfaces”; they not only contain address information but also know which container they belong to and how to move (for example, a list iterator needs to find the next pointer of a linked list node, while a vector iterator jumps directly in memory).
Example: Using a pointer to traverse a linked list will crash directly.
#include <list>
#include <iostream>
int main() {
std::list<int> nums = {1, 2, 3};
int* p = &nums.front(); // Get the address of the first element (pointer)
// Error! List elements are not contiguous, p+1 will point to random memory
for (int i = 0; i < 3; ++i) {
std::cout << *(p + i) << " "; // Undefined behavior, likely to crash
}
// Correct! The iterator knows how to traverse the linked list
for (auto it = nums.begin(); it != nums.end(); ++it) {
std::cout << *it << " "; // Output: 1 2 3
}
return 0;
}2. Type Safety: “Container-Specific” VS “Arbitrary Access”
- Pointers have no type binding; as long as you force a conversion, you can access any memory (for example, converting an int pointer to a char pointer), which can easily lead to memory overflow.
- Iterators are strongly bound to the container; for example, std::list<int>::iterator can only access int elements of the list and cannot access elements of a vector; the compiler will help you intercept errors.
Example:
std::vector<int> vec = {10, 20};
std::list<int> lst = {30, 40};
// Pointer: can access "cross-container" after forced conversion (dangerous!)
int* p_vec = &vec[0];
int* p_lst = (int*)&lst.front(); // Forced conversion, compiler does not report an error
std::cout << *(p_vec + 1); // 20 (lucky)
std::cout << *(p_lst + 1); // Random value (crash risk)
// Iterator: direct error when assigning across containers (safe!)
std::vector<int>::iterator it_vec = vec.begin();
std::list<int>::iterator it_lst = lst.begin();
// it_vec = it_lst; // Compilation error: type mismatch, cannot assignClassification of Iterators
The underlying structure of different containers determines the types of iterators they can provide. There are five types of iterators, as shown in the table below:
|
Iterator Type |
Function Description |
Supported Operations |
Typical Applicable Containers |
|
Input Iterator |
Can only read, single-direction movement |
++, *, ->, ==, != |
istream |
|
Output Iterator |
Can only write, single-direction movement |
++, * |
ostream |
|
Forward Iterator |
Readable and writable, single-direction movement |
All operations of input and output iterators |
forward_list, unordered_set |
|
Doubly Iterator |
Readable and writable, bidirectional movement |
All operations of forward iterators, — |
list, set, map |
|
Random Access Iterator |
Readable and writable, random access |
All operations of bidirectional iterators, [], +, -, +=, -, <, > etc. |
vector, deque, array |
In actual development, choosing the right container-iterator combination can maximize efficiency:
- When fast random access is needed (for example, accessing elements by index): choose
<span>vector</span>/<span>deque</span>random access iterators, which can “jump” to the target position in constant time, like an elevator going directly to a floor. - When frequent insertions and deletions are needed (especially in the middle): choose
<span>list</span>with doubly iterators, as the linked list structure allows insertions and deletions to only require pointer adjustments, unlike<span>vector</span>, which would cause a lot of elements to move. - When processing data streams use
<span>istream_iterator</span>/<span>ostream_iterator</span>, which act like valves in a water pipe, reading and writing data in order without supporting backtracking.
When using iterators with algorithms, it is essential to choose the appropriate iterator based on the algorithm. For example, when using <span>std::ranges::sort()</span><span>, if you pass in </span><code><span>std::forward_list</span> (forward iterator), the compiler will report an error directly—because the sorting algorithm requires random access iterators to swap elements at any position. Remember: the iterator type of a container is “innate” and will not change due to algorithm requirements; you must consider what algorithms you will use when selecting a container.
Common algorithms corresponding to iterators:
| Algorithm Type | Minimum Iterator Requirement | Applicable Container Examples |
|---|---|---|
| std::find | Input Iterator | list, vector, istream |
| std::reverse | Doubly Iterator | list, vector |
| std::sort | Random Access Iterator | vector, deque |
| std::transform | Input + Output Iterator | All containers + Insertion Iterators |
Basic Operations of Iterators
-
Getting an iterator
std::vector<int> vec = {10, 20, 30};
auto it_begin = vec.begin(); // Iterator pointing to the first element
auto it_end = vec.end(); // Iterator pointing to the position after the last element (sentinel position)
auto cit_begin = vec.cbegin(); // const iterator, cannot modify elements through it-
Moving the iterator
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();
++it; // Move to the next element (recommended, more efficient)
it++; // Return the current element, then move to the next element
it += 3; // Random access iterator supports jumping 3 steps
--it; // Bidirectional and random iterators support-
Accessing elements
std::vector<int> vec = {1, 2, 3};
auto it = vec.begin();
*it = 10; // Modify element value
std::cout << *it; // Read element value
std::vector<std::string> strs = {"hello", "world"};
auto sit = strs.begin();
std::cout << sit->size(); // Access member, equivalent to (*sit).size()Three Ways to Traverse Containers
Traditional for loop:
std::vector<int> nums = {1, 2, 3, 4, 5};
for (auto it = nums.begin(); it != nums.end(); ++it) {
std::cout << *it << " ";
}Range for loop (essentially still using iterators):
// The compiler will automatically convert to iterator form
for (int num : nums) {
std::cout << num << " ";
}
Reverse traversal:
// rbegin() points to the last element, rend() points to the position before the first element
for (auto it = nums.rbegin(); it != nums.rend(); ++it) {
std::cout << *it << " "; // Output: 5 4 3 2 1
}Note that although the above is traversing from back to front, because it is a reverse iterator, you still need to use ++ instead of –.
Using Iterators with Algorithms
Iterators and STL algorithms are often used together, such as for finding elements, sorting, etc.:
#include <algorithm> // Include algorithm library
std::vector<int> nums = {10, 20, 30, 40};
// Find the element with value 30
auto it = std::find(nums.begin(), nums.end(), 30);
if (it != nums.end()) {
std::cout << "Found element: " << *it << " at position: " << it - nums.begin();
} else {
std::cout << "Element not found";
}
// Sort in descending order
std::sort(nums.begin(), nums.end(), descending);
for(auto i:nums) {
std::cout << i; // Output: 40, 30, 20, 10
}Common Pitfalls in Using Iterators
While iterators are convenient, one can easily fall into pitfalls. These common mistakes must be remembered:
-
Iterator Invalidity Issues (Most Common!)
When a container changes, iterators may become invalid, and continued use can lead to undefined behavior.
For example, the insertion/deletion trap of vectors
std::vector<int> vec = {1, 2, 3, 4};
auto it = vec.begin() + 2; // Pointing to 3
// After inserting an element, the original iterator may become invalid
vec.insert(it, 100);
// *it; // Dangerous! May have already become invalid
// Correct approach: use the return value of insert
it = vec.insert(it, 100); // insert returns the iterator of the newly inserted element
// Deleting elements is similarly dangerous
vec.erase(it);
// *it; // Invalid!
// Correct approach
it = vec.erase(it); // erase returns the iterator of the next valid element
Why do iterators become invalid?
The underlying structure of a vector is a dynamically allocated array, and insertion/deletion operations may lead to memory reallocation, making the memory address pointed to by the original iterator invalid.
Invalidation Rules for Different Containers:
- Vector: Insertion may invalidate all iterators; deletion invalidates the iterators at and after the deletion point.
- List: Insertion/deletion only affects the iterators of the deleted elements; others remain unaffected.
- Map/Set: Insertion does not invalidate; deletion only affects the iterators of the deleted elements.
- Unordered_*: Insertion may cause rehashing, invalidating all iterators.
-
Out-of-Bounds Access
std::vector<int> vec = {1, 2, 3};
auto it = vec.begin();
// Error: moved to after end()
while (it <= vec.end()) { // Should use != instead of <=
std::cout << *it++;
}
Note that end() returns “the position after the last element” and cannot be dereferenced (*it). To check if the iterator has reached the end, use != instead of <=, as not all iterators support < comparison.
-
Using Const Iterators
Const iterators represent read-only iterators, meaning you cannot modify elements through them. For scenarios where you only need read access to elements, using const iterators can prevent accidental modifications, for example:
std::vector<int> vec = {1, 2, 3};
auto it = vec.cbegin(); // const iterator
// *it = 10; // Error! Const iterator cannot modify elements
// Correct: use non-const iterator if modification is needed
auto mut_it = vec.begin();
*mut_it = 10; // No problem
In C++11, cbegin() and cend() return const iterators, ensuring that elements cannot be modified even if the container itself is not const.
-
Lifecycle of Iterators
The lifecycle of an iterator cannot exceed that of the container it points to; once the container is destroyed, the iterator becomes invalid.
std::vector<int> get_vector() {
return {1, 2, 3};
}// Dangerous! auto it = get_vector().begin();
// *it; // Temporary vector has been destroyed, iterator is invalidSummary: Precautions for Using Iterators
- Prefer using auto to declare iterators
Reduces code redundancy and avoids type errors.
// Recommended
auto it = vec.begin();
// Not recommended
std::vector<int>::iterator it = vec.begin();
- Prefer using iterators over indices
Unless you are sure it is a random access container, iterators have better universality.
// General writing, applicable to all containers
for (auto it = container.begin(); it != container.end(); ++it)
// Only applicable to random access containers, accessing via index
for (size_t i = 0; i < container.size(); ++i)
- When handling insertions and deletions, avoid iterator invalidation
// Correct deletion method
for (auto it = vec.begin(); it != vec.end(); ) {
if (*it % 2 == 0) {
it = vec.erase(it); // Update iterator using return value
} else {
++it;
}
}
- When read-only access is needed, use const iterators
Improves code readability and safety.
for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
*it = 2; // Compilation error, cannot modify- Do not treat iterators like pointers
Avoid using pointer-like thinking to operate iterators (e.g., taking the address of *it and holding it for a long time), to prevent memory invalidation after container modifications.