C++: STL Iterators

Q: Q: What is const_iterator?

A: const_iterator is a read-only iterator that cannot modify element values.

In lessons 34-35 we learned about STL containers and algorithms.

Now, we'll dive into the "glue" of the STL — iterators.

Understanding iterators is key to truly understanding the STL's design philosophy.

1. Iterator Overview

(1) 1.1 What Are Iterators?

Iterators are a core concept of the STL that connect containers and algorithms.

Real-life analogy:

Container = warehouse
Algorithm = worker
Iterator = the pick-up slip in the worker's hand (telling the worker which shelf to go to)

(2) 1.2 Basic Iterator Operations

All iterators support the following operations:

Operation	Description	Example
`*it`	Dereference	`int x = *it;`
`it++`	Advance to next element	`++it;`
`it--`	Move back to previous element	`--it;`
`it1 == it2`	Compare equality	`if (it1 == it2)`
`it1 != it2`	Compare inequality	`while (it != end())`

2. Iterator Categories

(1) 2.1 Five Iterator Types

The STL defines 5 iterator types, from weakest to strongest:

Iterator Type	Capabilities	Representative Container
Input iterator	Read-only, one-directional	`istream_iterator`
Output iterator	Write-only, one-directional	`ostream_iterator`
Forward iterator	Read/write, one-directional	`forward_list`
Bidirectional iterator	Read/write, bidirectional	`list`, `set`, `map`
Random-access iterator	Read/write, random access	`vector`, `deque`, `array`

(2) 2.2 Iterator Capability Comparison

TEXT 📖 Display only

Input iterator ← Weakest
 ↓
Forward iterator
 ↓
Bidirectional iterator
 ↓
Random-access iterator ← Strongest

The stronger the capability, the more operations are supported:

Operation	Input	Forward	Bidirectional	Random Access
Dereference `*`	✅	✅	✅	✅
Advance `++`	✅	✅	✅	✅
Move back `--`	❌	❌	✅	✅
Random access ``	❌	❌	❌	✅
Arithmetic `+` `-`	❌	❌	❌	✅

(3) 2.3 Example: Iterators for Different Containers

CPP

#include <iostream>
#include <vector>
#include <list>
#include <forward_list>

int main() {
 std::vector<int> v = {1, 2, 3};
 std::list<int> l = {1, 2, 3};
 std::forward_list<int> fl = {1, 2, 3};
 
 // vector: random-access iterator
 auto it_v = v.begin();
 std::cout << it_v[2] << std::endl; // Random access works
 
 // list: bidirectional iterator
 auto it_l = l.begin();
 ++it_l; // Can advance
 --it_l; // Can move back
 // it_l[2]; // ❌ Error! list doesn't support random access
 
 return 0;
}

Output:

TEXT 📖 Display only

3. Iterator Invalidation

(1) 3.1 What Is Iterator Invalidation?

Iterator invalidation occurs when a container operation causes an iterator's position to become invalid.

Common causes:

Memory reallocation (vector's push_back)
Element deletion (erase)

(2) 3.2 Iterator Invalidation Rules by Container

Container	Operation	Invalidation
`vector`	`push_back`	May invalidate (when reallocation occurs)
`vector`	`erase`	Iterators at and after the deleted element are invalidated
`list`	`push_back`	Not invalidated
`list`	`erase`	Only the iterator to the deleted element is invalidated
`map`/`set`	`erase`	Only the iterator to the deleted element is invalidated

(3) 3.3 Example: vector Iterator Invalidation (Difficulty ⭐⭐)

▶ Example 1: STL Container Usage (Difficulty ⭐)

CPP

#include <iostream>
#include <vector>

int main() {
 std::vector<int> v = {1, 2, 3, 4, 5};
 
 auto it = v.begin();
 std::cout << "*it = " << *it << std::endl; // Output: 1
 
 // push_back may cause reallocation, invalidating iterators
 v.push_back(6);
 
 // ❌ Dangerous! it may be invalidated
 // std::cout << "*it = " << *it << std::endl; // Undefined behavior
 
 // ✅ Correct approach: re-acquire the iterator
 it = v.begin();
 std::cout << "*it = " << *it << std::endl; // Output: 1
 
 return 0;
}

▶ Try it Yourself

Output:

TEXT 📖 Display only

*it = 1
*it = 1

(4) 3.4 Safely Removing Elements

Wrong approach:

TEXT 📖 Display only

for (auto it = v.begin(); it != v.end(); ++it) {
### ▶ Example 2: Modern C++ Feature Application (Difficulty ⭐)

 if (*it % 2 == 0) {
 v.erase(it); // ❌ it is invalidated!
 }
}

Correct approach:

CPP

for (auto it = v.begin(); it != v.end(); ) {
 if (*it % 2 == 0) {
 it = v.erase(it); // ✅ erase returns the next valid iterator
 } else {
 ++it;
 }
}

Output:

TEXT 📖 Display only

(program output)

4. Reverse Iterators

(1) 4.1 What Are Reverse Iterators?

Reverse iterators traverse a container from the end to the beginning.

Example: Reverse output (Difficulty ⭐)

CPP

#include <iostream>
#include <vector>

int main() {
 std::vector<int> v = {1, 2, 3, 4, 5};
 
 // Using reverse iterator
 for (auto it = v.rbegin(); it != v.rend(); ++it) {
 std::cout << *it << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

Result:

TEXT 📖 Display only

5 4 3 2 1

5. Insert Iterators

(1) 5.1 What Are Insert Iterators?

Insert iterators are output iterators used to insert elements into a container.

Three types of insert iterators:

Iterator	Function	Example
`back_inserter`	Insert at the back	`std::back_inserter(v)`
`front_inserter`	Insert at the front	`std::front_inserter(l)`
`inserter`	Insert at specified position	`std::inserter(v, v.begin())`

(2) 5.2 Example: Copying with back_inserter (Difficulty ⭐⭐)

CPP

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
 std::vector<int> src = {1, 2, 3, 4, 5};
 std::vector<int> dst; // Empty container
 
 // ❌ Wrong! dst doesn't have enough space
 // std::copy(src.begin(), src.end(), dst.begin());
 
 // ✅ Correct! Use back_inserter for automatic expansion
 std::copy(src.begin(), src.end(), std::back_inserter(dst));
 
 std::cout << "Copy result: ";
 for (int x : dst) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

Output:

TEXT 📖 Display only

1 2 3 4 5

6. Stream Iterators

(1) 6.1 Input Stream Iterators

Function: Read data from an input stream.

Example: Reading from standard input (Difficulty ⭐⭐)

TEXT 📖 Display only

#include <iostream>
#include <vector>
#include <iterator>

int main() {
 std::vector<int> v;
 
 std::cout << "Enter some numbers (Ctrl+Z to end):" << std::endl;
 
 // Read from standard input
 std::copy(std::istream_iteratorint(std::cin),
 std::istream_iteratorint(),
 std::back_inserter(v));
 
 std::cout << "You entered: ";
 for (int x : v) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

(2) 6.2 Output Stream Iterators

Function: Write data to an output stream.

Example: Output to file (Difficulty ⭐⭐)

CPP

#include <iostream>
#include <vector>
#include <iterator>
#include <fstream>

int main() {
 std::vector<int> v = {1, 2, 3, 4, 5};
 
 // Output to standard output
 std::copy(v.begin(), v.end(),
 std::ostream_iteratorint(std::cout, " "));
 std::cout << std::endl;
 
 // Output to file
 std::ofstream file("output.txt");
 std::copy(v.begin(), v.end(),
 std::ostream_iteratorint(file, "\n"));
 file.close();
 
 return 0;
}

❓ FAQ

Q Why doesn't list support random access?

A list is a linked list — elements are not contiguous in memory, so you can't access them directly by index.

Q How do I avoid iterator invalidation?

A 1. Re-acquire iterators after each container operation 2. Use erase's return value to update iterators 3. Prefer using algorithms over manual iterator manipulation

Q: What is const_iterator? A: const_iterator is a read-only iterator that cannot modify element values.

TEXT 📖 Display only

std::vector<int> v = {1, 2, 3};
std::vector<int>::const_iterator it = v.cbegin();
// *it = 10; // ❌ Error! Cannot modify

▶ Example 3: Iterator Traversal (Difficulty ⭐)

CPP

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

▶ Try it Yourself

Output:

TEXT 📖 Display only

1 2 3 4 5

💡 Tip: Iterators work like pointers — use * to dereference, ++ to move, and != to compare positions.

Topic	Key Points
Iterator categories	Input → Forward → Bidirectional → Random Access
Iterator invalidation	vector may invalidate, list does not
Reverse iterators	`rbegin()`/`rend()`
Insert iterators	`back_inserter` etc.
Stream iterators	Connect STL and I/O

📖 Summary

Iterators: pointer-like objects used to traverse container elements
Iterator categories: input/output/forward/bidirectional/random access
begin()/end(): get iterators to the beginning and end of a container
Iterator invalidation: insertion/deletion may invalidate iterators

📝 Exercises

Basic (Difficulty ⭐): Use iterators to traverse vector<int> and output all elements. Do it both with begin/end and with range-based for.
Intermediate (Difficulty ⭐⭐): Use reverse iterators rbegin/rend to traverse a vector in reverse and output. Observe the difference from forward traversal.
Challenge (Difficulty ⭐⭐⭐): Implement a custom iterator that wraps an integer range (e.g. 1 to 10), supporting ++ and * operators.

Iterators are the bridge between containers and algorithms
Five iterator types: input/output/forward/bidirectional/random access
Range-based for loops are implemented using iterators underneath
Iterator invalidation: some iterators become unusable after insert/delete
const_iterator provides read-only access to elements

Next lesson: STL Function Objects (#38)

Web-Tutorial Tech Team

A team of developers maintaining programming tutorials. Each tutorial is written and reviewed by developers with expertise in that field. We work to keep our content accurate and reliable — if you spot an issue, please let us know.

About Us

C++: STL Iterators

1. Iterator Overview

(1) 1.1 What Are Iterators?

(2) 1.2 Basic Iterator Operations

2. Iterator Categories

(1) 2.1 Five Iterator Types

(2) 2.2 Iterator Capability Comparison

(3) 2.3 Example: Iterators for Different Containers

3. Iterator Invalidation

(1) 3.1 What Is Iterator Invalidation?

(2) 3.2 Iterator Invalidation Rules by Container

(3) 3.3 Example: vector Iterator Invalidation (Difficulty ⭐⭐)

▶ Example 1: STL Container Usage (Difficulty ⭐)

(4) 3.4 Safely Removing Elements

4. Reverse Iterators

(1) 4.1 What Are Reverse Iterators?

5. Insert Iterators

(1) 5.1 What Are Insert Iterators?

(2) 5.2 Example: Copying with back_inserter (Difficulty ⭐⭐)

6. Stream Iterators

(1) 6.1 Input Stream Iterators

(2) 6.2 Output Stream Iterators

❓ FAQ

▶ Example 3: Iterator Traversal (Difficulty ⭐)

📖 Summary

📝 Exercises

🙏 帮我们做得更好