STL
STL Iterators in C++
Table of Contents
What are Iterators
Iterators are the glue between STL containers and algorithms. They provide a uniform way to access elements regardless of the underlying container type.
The Iterator Concept Visualized
┌──────────────────────────────────────────────────────────────────────────────┐
│ WHY ITERATORS MATTER │
├──────────────────────────────────────────────────────────────────────────────┤
│ │
│ WITHOUT Iterators: WITH Iterators: │
│ ────────────────── ─────────────── │
│ │
│ // Different access for each // Same code for all containers! │
│ // container type │
│ template<typename Iter> │
│ for (int i = 0; i < vec.size(); i++) void process(Iter begin, Iter end) { │
│ process(vec[i]); for (auto it = begin; it != end; ++it) │
│ process(*it); │
│ for (auto& e : list) } │
│ process(e); │
│ // Works with ANY container: │
│ Node* n = head; process(vec.begin(), vec.end()); │
│ while (n) { process(list.begin(), list.end()); │
│ process(n->data); process(set.begin(), set.end()); │
│ n = n->next; │
│ } │
│ │
└──────────────────────────────────────────────────────────────────────────────┘
Iterator as a Generalized Pointer
┌────────────────────────────────────────────────────────────────────────────┐
│ ITERATOR = GENERALIZED POINTER │
├────────────────────────────────────────────────────────────────────────────┤
│ │
│ Container: [ 1 | 2 | 3 | 4 | 5 ] │
│ ▲ ▲ │
│ │ │ │
│ begin() end() │
│ (first element) (past-the-end) │
│ │
│ Like pointers: Unlike raw pointers: │
│ • *it (dereference) • Works with any container │
│ • ++it (increment) • Knows its category/capabilities │
│ • it1 == it2 • Type-safe │
│ │
└────────────────────────────────────────────────────────────────────────────┘
Iterator Basics
Iterators provide uniform access to container elements:
vector<int> v = {1, 2, 3, 4, 5};
// Begin and end
auto it = v.begin(); // Points to first element
auto end = v.end(); // Points PAST last element (sentinel)
// Dereference to access value
cout << *it; // 1
// Increment to move forward
++it;
cout << *it; // 2
// Classic loop pattern
for (auto it = v.begin(); it != v.end(); ++it) {
cout << *it << " "; // 1 2 3 4 5
}
Visual: begin() and end()
vector<int> v = {10, 20, 30, 40, 50};
Index: [0] [1] [2] [3] [4]
Memory: ┌──────┬──────┬──────┬──────┬──────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │ [past-end]
└──────┴──────┴──────┴──────┴──────┘
▲ ▲
│ │
v.begin() v.end()
⚠️ v.end() does NOT point to an element!
Dereferencing it is UNDEFINED BEHAVIOR!
Iterator Categories Hierarchy
C++ defines five iterator categories with increasing capabilities. Each category supports all operations of the categories above it.
Iterator Category Hierarchy Diagram
┌────────────────────────────────────────────────────────────────────────────┐
│ ITERATOR CATEGORIES HIERARCHY │
├────────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌───────────────────────┐ │
│ │ Input Iterator │ ─── Read only, single pass │
│ │ (istream_iterator) │ │
│ └───────────┬───────────┘ │
│ │ │
│ ┌───────────────────────┐ │
│ │ Output Iterator │ ─── Write only, single pass │
│ │ (ostream_iterator) │ │
│ └───────────┬───────────┘ │
│ │ │
│ ▼ │
│ ┌───────────────────────┐ │
│ │ Forward Iterator │ ─── Read/write, multi-pass │
│ │ (forward_list) │ ++ only │
│ └───────────┬───────────┘ │
│ │ │
│ ▼ │
│ ┌───────────────────────┐ │
│ │ Bidirectional Iterator│ ─── Forward + backward │
│ │ (list, set, map) │ ++ and -- │
│ └───────────┬───────────┘ │
│ │ │
│ ▼ │
│ ┌───────────────────────┐ │
│ │ Random Access Iterator│ ─── Pointer-like operations │
│ │ (vector, deque, arr) │ + - [] < > etc. │
│ └───────────────────────┘ │
│ │
└────────────────────────────────────────────────────────────────────────────┘
Capability Comparison Table
┌────────────────────────────────────────────────────────────────────────────┐
│ ITERATOR CAPABILITIES MATRIX │
├──────────────────┬──────┬──────┬─────────┬─────────────┬──────────────────┤
│ Operation │Input │Output│ Forward │Bidirectional│ Random Access │
├──────────────────┼──────┼──────┼─────────┼─────────────┼──────────────────┤
│ *it (read) │ ✅ │ ❌ │ ✅ │ ✅ │ ✅ │
│ *it = x (write) │ ❌ │ ✅ │ ✅ │ ✅ │ ✅ │
│ ++it │ ✅ │ ✅ │ ✅ │ ✅ │ ✅ │
│ it++ │ ✅ │ ✅ │ ✅ │ ✅ │ ✅ │
│ --it │ ❌ │ ❌ │ ❌ │ ✅ │ ✅ │
│ it1 == it2 │ ✅ │ ❌ │ ✅ │ ✅ │ ✅ │
│ it + n │ ❌ │ ❌ │ ❌ │ ❌ │ ✅ │
│ it - n │ ❌ │ ❌ │ ❌ │ ❌ │ ✅ │
│ it[n] │ ❌ │ ❌ │ ❌ │ ❌ │ ✅ │
│ it1 < it2 │ ❌ │ ❌ │ ❌ │ ❌ │ ✅ │
│ it2 - it1 │ ❌ │ ❌ │ ❌ │ ❌ │ ✅ │
│ Multi-pass │ ❌ │ ❌ │ ✅ │ ✅ │ ✅ │
├──────────────────┼──────┴──────┴─────────┴─────────────┴──────────────────┤
│ Containers │istream│ostream│fwd_list │list,set,map │ vector,deque, │
│ │ │ │ │ │ array, string │
└──────────────────┴─────────────────────────────────────────────────────────┘
Which Algorithms Need Which Iterators
┌────────────────────────────────────────────────────────────────────────────┐
│ ALGORITHMS AND THEIR ITERATOR REQUIREMENTS │
├────────────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT ITERATORS (single pass reading): │
│ • find(), count(), accumulate() │
│ • equal(), copy() (source) │
│ │
│ OUTPUT ITERATORS (single pass writing): │
│ • copy() (destination), fill_n() │
│ • transform() (output) │
│ │
│ FORWARD ITERATORS (multi-pass): │
│ • replace(), unique(), rotate() │
│ • search(), remove() │
│ │
│ BIDIRECTIONAL ITERATORS (++ and --): │
│ • reverse(), prev_permutation() │
│ • reverse_copy() │
│ │
│ RANDOM ACCESS ITERATORS (full pointer-like): │
│ • sort(), nth_element(), binary_search() │
│ • random_shuffle(), partial_sort() │
│ │
└────────────────────────────────────────────────────────────────────────────┘
Iterator Operations
Standard Functions
#include <iterator>
vector<int> v = {1, 2, 3, 4, 5};
// Advance
auto it = v.begin();
advance(it, 3); // Move 3 forward
cout << *it; // 4
// Distance
auto d = distance(v.begin(), v.end()); // 5
// Next/Prev
auto it2 = next(v.begin(), 2); // 3rd element
auto it3 = prev(v.end(), 1); // Last element
// Begin/End (non-member)
begin(v);
end(v);
cbegin(v); // const
cend(v); // const
rbegin(v); // reverse
rend(v); // reverse
Const Iterators
vector<int> v = {1, 2, 3};
// Cannot modify through const iterator
for (auto it = v.cbegin(); it != v.cend(); ++it) {
cout << *it; // OK
// *it = 10; // ERROR
}
Reverse Iterators
vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.rbegin(); it != v.rend(); ++it) {
cout << *it << " ";
}
// Output: 5 4 3 2 1
Iterator Adaptors
Insert Iterators
#include <iterator>
vector<int> v = {1, 2, 3};
// Back inserter - push_back
back_insert_iterator<vector<int>> bi(v);
*bi = 4; // v is now {1, 2, 3, 4}
// Front inserter (deque/list)
deque<int> dq;
auto fi = front_inserter(dq);
*fi = 1; // dq is {1}
*fi = 2; // dq is {2, 1}
// Insert at position
auto ii = inserter(v, v.begin() + 1);
*ii = 10; // v is {1, 10, 2, 3, 4}
Stream Iterators
#include <iterator>
#include <sstream>
// Input stream iterator
istringstream iss("1 2 3 4 5");
istream_iterator<int> iit(iss), end;
vector<int> v(iit, end); // v = {1, 2, 3, 4, 5}
// Output stream iterator
ostream_iterator<int> oit(cout, ", ");
*oit++ = 1;
*oit++ = 2;
// Output: 1, 2,
Move Iterator
vector<string> src = {"hello", "world"};
vector<string> dest;
// Move elements instead of copy
dest.insert(dest.end(),
make_move_iterator(src.begin()),
make_move_iterator(src.end()));
Range-Based For
Modern iteration:
vector<int> v = {1, 2, 3, 4, 5};
// Read-only
for (const auto& x : v) {
cout << x;
}
// Modify
for (auto& x : v) {
x *= 2;
}
// Copy (avoid for large objects)
for (auto x : v) {
cout << x;
}
Custom Types
class MyRange {
int start, stop;
public:
MyRange(int s, int e) : start(s), stop(e) {}
struct Iterator {
int value;
int operator*() const { return value; }
Iterator& operator++() { ++value; return *this; }
bool operator!=(const Iterator& o) const {
return value != o.value;
}
};
Iterator begin() { return {start}; }
Iterator end() { return {stop}; }
};
for (int x : MyRange(1, 5)) {
cout << x << " "; // 1 2 3 4
}
Recommended Conventions
✅ Do
// 1. Use auto for iterator types
for (auto it = container.begin(); it != container.end(); ++it)
// 2. Prefer range-based for when possible
for (const auto& elem : container)
// 3. Use const iterators for read-only
for (auto it = v.cbegin(); it != v.cend(); ++it)
// 4. Use pre-increment
++it; // More efficient than it++
// 5. Use algorithms with iterators
sort(v.begin(), v.end());
find(v.begin(), v.end(), target);
❌ Don't
// 1. Don't use invalid iterators
v.push_back(x); // May invalidate iterators!
// 2. Don't compare iterators from different containers
// if (v1.begin() == v2.begin()) // UNDEFINED
// 3. Don't dereference end()
// *v.end(); // UNDEFINED BEHAVIOR
Cheat Sheet
// Get iterators
container.begin() container.end()
container.cbegin() container.cend() // const
container.rbegin() container.rend() // reverse
// Iterator operations
*it // Dereference
++it --it // Move
it += n it -= n // Jump (random access)
it1 - it2 // Distance (random access)
// Standard functions
advance(it, n) // Move n positions
distance(it1, it2) // Get distance
next(it, n) // Return advanced iterator
prev(it, n) // Return moved-back iterator
// Insert iterators
back_inserter(c) // push_back
front_inserter(c) // push_front
inserter(c, pos) // insert at pos
// Stream iterators
istream_iterator<T>(stream)
ostream_iterator<T>(stream, delimiter)
Compile & Run
g++ -std=c++17 -Wall examples.cpp -o examples && ./examples