STL Algorithms & Iterators

iterators are the glue

An algorithm like std::sort doesn't know anything about vector or list specifically — it's written once, generically, against a pair of iterators (a "begin" and an "end"). Every container exposes .begin()/.end() returning iterators appropriate to its own internal layout, which is what lets the same algorithm work across unrelated container types.

Category	Capability	Example containers
Input	read forward, single pass	istream_iterator
Output	write forward, single pass	ostream_iterator, back_inserter
Forward	read/write, multi-pass	forward_list
Bidirectional	forward + backward	list, map, set
Random access	bidirectional + O(1) jump to any position	vector, array, deque

insert iterators

back_inserter wraps a container in an iterator that calls push_back on assignment instead of overwriting an existing element — exactly what you need when an algorithm's output container starts empty and needs to grow as the algorithm writes to it (std::transform, std::copy, std::copy_if are the common ones this pattern shows up with). Not every container supports every insert-iterator flavor: vector has no push_front, so it doesn't support front_inserter — but the general-purpose std::inserter(container, pos), which calls insert(pos, value), still works at any position on a vector (at O(n) cost per insertion, since it has to shift every following element). back_inserter is just the common, O(1)-amortized case.


std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> doubled;

std::transform(src.begin(), src.end(), std::back_inserter(doubled),
                [](int v) { return v * 2; });   // doubled grows to fit — no pre-sizing needed

a working tour of the algorithm library

std::sort(v.begin(), v.end()); | https://en.cppreference.com/w/cpp/algorithm/sort | sort in place, ascending by default; pass a comparator lambda for custom order |'sa1'

std::find(v.begin(), v.end(), x); | https://en.cppreference.com/w/cpp/algorithm/find | first iterator equal to x, or v.end() if not found |'sa2'

std::count_if(v.begin(), v.end(), pred); | https://en.cppreference.com/w/cpp/algorithm/count | how many elements satisfy the predicate |'sa3'

std::accumulate(v.begin(), v.end(), 0); | https://en.cppreference.com/w/cpp/algorithm/accumulate | sum (or, with a custom binary op, any left-fold reduction); needs <numeric> |'sa4'

std::unique(v.begin(), v.end()); | https://en.cppreference.com/w/cpp/algorithm/unique | collapse consecutive duplicates — requires the range to already be sorted to remove ALL duplicates |'sa5'

std::partition reorders a range so every element satisfying a predicate comes before every element that doesn't, and returns an iterator at the boundary between them — neither side is sorted, just grouped. std::stable_partition does the same thing while preserving each group's relative order, at some extra cost:


std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};
auto boundary = std::stable_partition(nums.begin(), nums.end(), [](int i) { return i % 2 != 0; });
// nums is now odds-then-evens, each group in its original relative order; boundary points at the first even

std::nth_element is the one to reach for when you need "the k-th smallest element" without paying for a full sort: it partitions around the n-th position so everything before it is ≤ it and everything after is ≥ it, but neither side is internally sorted — O(n) average, versus O(n log n) for a full std::sort.


std::vector<int> v = {1, 5, 4, 2, 9, 7, 3, 8, 2};
std::nth_element(v.begin(), v.begin() + 4, v.end());   // v[4] is now what it would be after a full sort
// v: something like {1, 2, 2, 3, 4, 7, 9, 8, 5} — v[4] == 4 is guaranteed, the rest is not fully ordered

Both algorithms above, run back to back with the actual output printed: TopNotchNote/cpp/stl_algorithms_partition_nth_element.cpp

const_iterator and reverse_iterator


std::vector<int> v = {1, 2, 3};

for (std::vector<int>::const_iterator it = v.cbegin(); it != v.cend(); ++it) { /* *it is read-only */ }

for (auto it = v.rbegin(); it != v.rend(); ++it) { std::cout << *it; }   // 3 2 1 — walks backward

std::reverse(v.begin(), v.end());   // 3 2 1 — reverses IN PLACE, distinct from iterating with rbegin/rend

Worth distinguishing explicitly: iterating with rbegin()/rend() visits the elements backward without changing the container, while std::reverse actually mutates the container's stored order. Reach for rbegin/rend when you just need to read backward once; use std::reverse when you need the reversed order to persist.

where to go from here

STL Containers — the data structures these algorithms operate on.
Lambdas & Functional C++ — the predicates and comparators most of these algorithms take.
Data Structures & Algorithms — implementing search/sort/traversal by hand, for comparison.

reference

cppreference — algorithms library
cppreference — iterator library