C++ STL

Iterators

Complete lesson for Iterators using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with C++ OOP and STL where relevant.

Basics — Iterators

Section: C++ STL. C++ iterators — begin/end ranges, categories, algorithms, and Iterators vs Pointers.

What is an iterator?

An **iterator** is a generalized pointer used to walk elements of a container (or array).
STL algorithms work on **iterator ranges**, not on container types directly.
Most containers provide begin() / end() (and const / reverse variants).
**Real-life:** a bookmark that moves through pages — you read *it and turn with ++it.

Idea	Meaning
`begin()`	Iterator to the first element
`end()`	Iterator one past the last element
`*it`	Access the current element
`++it`	Advance to the next element
Range	Half-open `[begin, end)`

Why use iterators?

One sort / find / count works on vector, deque, arrays, …
Hide container internals — client code walks a uniform interface.
Support reverse and const traversal cleanly.
Enable generic programming (templates + algorithms).

Benefit	What you gain
Generic algorithms	Same API across containers
Encapsulation	No need to know node/array layout
Safety options	`cbegin` / const iterators
Flexibility	Reverse ranges, inserters (advanced)

Differences between Iterators and Pointers

Iterators **behave like** pointers but are not always raw pointers.

Feature	Pointer	Iterator
What it is	Address of an object/array element	Object that navigates a sequence
Works on	Contiguous memory mainly	Any container that provides them
`++` / `*`	Yes arithmetic / dereference	Same syntax (usually)
`end()` idea	Often `a+n` for arrays	Past-the-end sentinel from the container
Categories	Raw pointer ≈ random-access	Input → random-access hierarchy
Invalidation	Dangling if object freed	Container-defined rules
`vector` iterators	Often implemented as pointers	Still use `begin`/`end` API
`list` iterators	Cannot use raw pointer walk of nodes safely	Bidirectional node iterators
Algorithms	Need pointer pair manually	Standard `begin`/`end` pair
Type	`T*`	`vector::iterator`, etc.

begin, end, and the half-open range

Valid elements are begin inclusive through **before** end.
**Never dereference end()** — it does not point to an element.
Empty range: begin() == end().
Loop pattern: for (auto it = c.begin(); it != c.end(); ++it).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};
    for (auto it = v.begin(); it != v.end(); ++it)
        cout << *it << " ";
    cout << "\n";
    return 0;
}

Iterator categories

Categories describe **what operations** an iterator supports.
Stronger categories support everything weaker ones do (roughly).
Algorithms require a minimum category (e.g. sort needs random-access).

Category	Can do	Typical containers
Input	Read forward once	Istream iterators
Output	Write forward	Ostream / insert iterators
Forward	Multi-pass forward	`forward_list`
Bidirectional	Forward + backward `--`	`list`, `set`, `map`
Random-access	`it+n`, `it[i]`, jump	`vector`, `deque`, arrays

Const and reverse iterators

cbegin() / cend() — read-only traversal.
rbegin() / rend() — reverse order (*rbegin() is the last element).
crbegin() / crend() — const reverse.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    for (auto it = v.rbegin(); it != v.rend(); ++it)
        cout << *it << " ";
    cout << "\n";
    for (auto it = v.cbegin(); it != v.cend(); ++it)
        cout << *it << " ";
    cout << "\n";
    return 0;
}

Iterators with algorithms

Pass [first, last) to algorithms in .
Example: find, count, sort, reverse, min_element.
Return value is often an iterator (find → match or end()).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 1, 3, 2};
    sort(v.begin(), v.end());
    auto it = find(v.begin(), v.end(), 3);
    if (it != v.end()) cout << "found " << *it << "\n";
    return 0;
}

Range-for vs iterators

Range-for (for (auto x : v)) is syntactic sugar over begin/end.
Use explicit iterators when you need the **position** (erase, insert, distance).

Style	Best when
Range-for	You only need each element value
Explicit iterators	You need to erase/insert at `it`
Indices `v[i]`	Random-access container + numeric index

Key points to remember

Algorithms use [begin, end) — never dereference end().
Iterator ≠ always a raw pointer (especially on list/map).
Know categories: random-access needed for std::sort.
Prefer ++it (pre-increment) in loops.
Invalidation rules depend on the container.

Advanced — Iterators

Operations by category

Quick capability map.

Operation	Input	Forward	Bidi	Random
`*it` read	Yes	Yes	Yes	Yes
`++it`	Yes	Yes	Yes	Yes
`--it`	No	No	Yes	Yes
`it + n`	No	No	No	Yes
Multi-pass	No	Yes	Yes	Yes

Iterator invalidation (overview)

vector: reallocation invalidates all; mid erase invalidates at/after.
deque: insert/erase in middle invalidate; end ops milder (implementation-defined details).
list / associative: erase invalidates only the erased element’s iterators.
After modifying a container, re-acquire iterators if unsure.

distance, advance, next, prev

advance(it, n) moves an iterator (O(n) unless random-access).
next(it, n) / prev(it, n) return a moved copy (C++11).
distance(a, b) — how many steps from a to b.

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

int main() {
    list<int> L = {10, 20, 30, 40};
    auto it = L.begin();
    advance(it, 2);
    cout << *it << "\n"; // 30
    cout << distance(L.begin(), it) << "\n"; // 2
    return 0;
}

Insert iterators (overview)

back_inserter(c) — push_back via assignment.
front_inserter(c) — push_front.
inserter(c, it) — insert at position.
Used with copy to grow a container.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> a = {1, 2, 3}, b;
    copy(a.begin(), a.end(), back_inserter(b));
    for (int x : b) cout << x << " ";
    cout << "\n";
    return 0;
}

Design tips

Prefer algorithms + iterators over hand-rolled index loops when clearer.
Use range-for for simple scans.
Do not store iterators across unsafe modifications.
Match algorithm requirements to iterator category (list::sort vs std::sort).

Tricky Interview Points

Q1) What is an iterator in C++?

Answer An object that navigates a sequence like a generalized pointer, used by STL containers and algorithms.

Q2) What does end() point to?

Answer One past the last element — it must not be dereferenced.

Q3) Iterator vs pointer?

Answer Pointers address memory; iterators abstract traversal for any container. Syntax is similar (*, ++), but list iterators are not raw pointers to contiguous data.

Q4) Name the iterator categories.

Answer Input, output, forward, bidirectional, and random-access.

Q5) Why can std::sort not be used on std::list?

Answer std::sort requires random-access iterators; list provides only bidirectional. Use list::sort.

Q6) What is a half-open range?

Answer [first, last) includes first and excludes last — the STL standard range model.

Q7) cbegin vs begin?

Answer cbegin returns a const iterator so you cannot modify elements through it.

Q8) What is rbegin?

Answer A reverse iterator starting at the last element, moving toward the front.

Q9) How do algorithms use iterators?

Answer They take a pair of iterators defining the range to process, e.g. sort(v.begin(), v.end()).

Q10) What is iterator invalidation?

Answer When a container operation makes existing iterators dangling or unusable; rules depend on the container.

Q11) distance complexity on list vs vector?

Answer On random-access (vector) it can be O(1); on list it is O(n).

Q12) Give an example of an insert iterator.

Answer back_inserter(v) used with copy to append elements into v.

Simple Programs

Classic begin/end loop

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4};
    for (auto it = v.begin(); it != v.end(); ++it)
        cout << *it << " ";
    cout << "\n";
    return 0;
}

Reverse iterators

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    for (auto it = v.rbegin(); it != v.rend(); ++it)
        cout << *it << " ";
    cout << "\n";
    return 0;
}

find with iterators

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 8, 3, 8};
    auto it = find(v.begin(), v.end(), 8);
    if (it != v.end())
        cout << "index " << (it - v.begin()) << "\n";
    return 0;
}

advance and distance on list

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

int main() {
    list<int> L = {10, 20, 30, 40};
    auto it = L.begin();
    advance(it, 3);
    cout << *it << "\n";
    cout << distance(L.begin(), it) << "\n";
    return 0;
}

back_inserter copy

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> a = {1, 2, 3}, b;
    copy(a.begin(), a.end(), back_inserter(b));
    for (int x : b) cout << x << " ";
    cout << "\n";
    return 0;
}

Erase via iterator

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4};
    auto it = v.begin() + 1;
    v.erase(it); // removes 2
    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

Problem Solving Tricks

Iterators = generalized pointers for containers.
[begin, end) — never dereference end().
Algorithms take iterator pairs.
Categories: input → forward → bidi → random-access.
std::sort needs random-access.
list uses bidirectional — list::sort instead.
cbegin for read-only walks.
rbegin walks backward.
Prefer ++it in loops.
Invalidation rules differ by container.
advance/distance are O(n) on non-random iterators.
Iterators vs Pointers table is a common interview ask.

Practice Programs List

Print a vector with an explicit iterator loop.
Print the same vector in reverse with rbegin/rend.
Use find and print the distance from begin.
advance to the 3rd element of a list and erase it.
Copy one vector into another with back_inserter.
Write Iterators vs Pointers table in comments (8 rows).
Write iterator categories table (5 rows).
Explain why sort fails conceptually on list.
Show begin==end for an empty container.
Use cbegin to traverse without modifying.
Compare index loop vs iterator loop for vector.
List three algorithms that return an iterator.