Don't write that loop
Suppose you have a list of exam marks and need the number of failing marks, the marks sorted, the distinct values, and a letter grade for each. You could write four loops, each with an index, a condition and a chance to be off by one. Or you could write count_if, sort, unique and transform, each a single line whose name says what it does, each tested by millions of programs before yours.
The C++ standard library's containers and algorithms grew out of Alexander Stepanov's Standard Template Library, and its central idea is still the best lesson in it: separate the data structures from the algorithms, and connect them with iterators. Any algorithm works with any container that offers the right kind of iterator. Twenty containers and a hundred algorithms do not need two thousand implementations, only a hundred and twenty. C++20 added ranges, which make the same algorithms easier to call and add lazy, composable views.
Professional C++ developers know this library well enough to reach for an algorithm before they reach for a loop. A well-known conference talk by Sean Parent, C++ Seasoning (2013), made "no raw loops" a slogan; it is a direction rather than a law, but code that follows it is usually shorter, clearer and as fast.
Definitions
Definition— container
An object that owns a collection of elements and manages their memory: std::vector, std::array, std::deque, std::list, std::map, std::set, std::unordered_map, std::unordered_set, and others. The container adaptors std::stack, std::queue and std::priority_queue restrict another container to a particular interface.
Definition— iterator and half-open range
An iterator is an object that refers to an element and can move to the next one (++it) and be dereferenced (*it), like a generalised pointer. A pair of iterators [first, last) describes a half-open range: first is included, last points one past the end and is never dereferenced. An empty range has first == last, and the number of elements is last - first where that subtraction is allowed.
Definition— iterator categories
Iterators differ in what they allow. A forward iterator can only move ahead; a bidirectional one (of std::list or std::map) can also go back; a random-access one (of std::vector, std::deque, std::array) can jump by any amount in constant time. An algorithm states which kind it needs: std::sort needs random access, which is why you cannot sort a std::list with it.
Definition— range, view and range adaptor
A range is anything with a begin() and an end(), such as a container. A view is a range that is cheap to copy and usually does not own its elements; it computes them on demand. A range adaptor such as std::views::filter turns a range into a view, and adaptors can be chained with |.
Definition— projection
An extra argument to a std::ranges algorithm that says which part of each element to look at, such as &Reading::celsius, so that you can sort or search objects by one member without writing a comparison function.
Containers and how to choose one
#include <array>
#include <map>
#include <print>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
int main() {
// vector: contiguous, growable. The default choice.
std::vector<int> v{5, 3, 8};
v.push_back(1);
std::println("vector size {} capacity {} front {} back {}", v.size(), v.capacity(), v.front(), v.back());
// array: fixed size known at compile time, no heap allocation.
std::array<double, 3> rgb{0.2, 0.6, 1.0};
std::println("array size {}", rgb.size());
// map: sorted by key (a balanced tree). unordered_map: hashed, no order.
std::map<std::string, int> stock{{"teff", 12}, {"quinoa", 4}, {"millet", 9}};
stock["sorghum"] = 7; // inserts
stock["teff"] -= 2; // updates
for (const auto& [grain, kg] : stock) std::print("{}={} ", grain, kg);
std::println("");
if (auto it = stock.find("rice"); it == stock.end()) std::println("no rice");
std::println("contains quinoa: {}", stock.contains("quinoa")); // C++20
std::unordered_map<std::string, std::string> capital{{"Peru", "Lima"}, {"Ghana", "Accra"}};
capital.try_emplace("Laos", "Vientiane");
std::println("{} entries; Ghana -> {}", capital.size(), capital.at("Ghana"));
// set: sorted unique keys.
std::set<char> letters;
for (char c : std::string("mississippi")) letters.insert(c);
for (char c : letters) std::print("{}", c);
std::println("");
// priority_queue: always pops the largest (a heap on top of a vector).
std::priority_queue<int> pq;
for (int x : {4, 9, 1, 7}) pq.push(x);
while (!pq.empty()) { std::print("{} ", pq.top()); pq.pop(); }
std::println("");
}vector size 4 capacity 6 front 5 back 1
array size 3
millet=9 quinoa=4 sorghum=7 teff=10
no rice
contains quinoa: true
3 entries; Ghana -> Accra
imps
9 7 4 1 A vector stores its elements contiguously and keeps spare capacity, growing by a constant factor when it runs out (GCC's library doubles, which is why the capacity became 6), so push_back is O(1) on average. std::map keeps keys sorted, so it printed the grains alphabetically. stock["sorghum"] = 7 inserts a missing key; be careful, because stock["rice"] also inserts (a zero) if you only meant to look, which is why the program uses find and contains for lookups. at throws an exception for a missing key, try_emplace inserts only if the key is absent, and priority_queue always hands back its largest element.
| Container | Lookup by key or position | Insert or erase | Keeps order? | Notes |
|---|---|---|---|---|
std::vector | O(1) by index | O(1) amortised at the end, O(n) elsewhere | insertion order | contiguous; the default choice |
std::array | O(1) by index | fixed size | — | no heap; size known at compile time |
std::deque | O(1) by index | O(1) at both ends | insertion order | chunks of contiguous memory |
std::list | O(n) | O(1) at a known position | insertion order | one allocation per element |
std::map, std::set | O(log n) | O(log n) | sorted by key | balanced tree; ordered iteration |
std::unordered_map, std::unordered_set | O(1) average | O(1) average | none | hash table |
Big-O is only half the story; memory layout is the other half. Modern processors are fast when they read memory in sequence, because whole cache lines arrive at once, and slow when they chase pointers around the heap. A vector of a few thousand elements often beats a list or a map at operations the table says the others do better, simply because its elements sit next to each other. That is why experienced programmers use std::vector unless they have measured a reason not to, and keep a small sorted vector instead of a std::map for small, read-mostly tables. (C++23's std::flat_map packages that idea; GCC's library added it in version 15, so it is not used here.)
Note
std::span (C++20) is to contiguous containers what std::string_view is to strings: a pointer and a length, cheap to copy, owning nothing. A function declared double mean(std::span<const double> xs) accepts a std::vector<double>, a std::array, a plain C array or a part of any of them, without copying and without being a template. Use it for parameters that only need to read (or write) a run of elements; like every view, it must not outlive the elements it refers to.
Iterators and algorithms
#include <algorithm>
#include <numeric>
#include <print>
#include <string>
#include <vector>
int main() {
std::vector<int> marks{72, 45, 91, 58, 66, 91, 30, 84};
// Iterators: begin() points at the first element, end() one past the last.
auto first = marks.begin();
std::println("first {} second {} count {}", *first, *(first + 1), marks.end() - marks.begin());
// Classic algorithms take an iterator range [first, last).
int total = std::accumulate(marks.begin(), marks.end(), 0);
auto failing = std::count_if(marks.begin(), marks.end(), [](int m) { return m < 50; });
std::println("total {} failing {}", total, failing);
// Range versions (C++20) take the container directly.
std::ranges::sort(marks);
std::print("sorted:");
for (int m : marks) std::print(" {}", m);
std::println("");
// Binary search in a sorted range: O(log n).
auto it = std::ranges::lower_bound(marks, 60);
std::println("first mark >= 60 is {} at index {}", *it, it - marks.begin());
// Remove duplicates from a sorted vector: unique moves them to the end, erase drops them.
auto dupes = std::ranges::unique(marks);
marks.erase(dupes.begin(), dupes.end());
std::println("{} distinct marks", marks.size());
// C++20: erase_if does the remove-and-erase in one call.
std::erase_if(marks, [](int m) { return m < 50; });
std::println("{} passing marks", marks.size());
// transform writes results through an output iterator.
std::vector<std::string> grades;
std::ranges::transform(marks, std::back_inserter(grades),
[](int m) { return m >= 80 ? std::string("A") : std::string("B"); });
std::print("grades:");
for (const auto& g : grades) std::print(" {}", g);
std::println("");
}first 72 second 45 count 8
total 537 failing 2
sorted: 30 45 58 66 72 84 91 91
first mark >= 60 is 66 at index 3
7 distinct marks
5 passing marks
grades: B B B A AThe classic algorithms, like std::accumulate and std::count_if, take two iterators. Their C++20 versions in std::ranges (std::ranges::sort, std::ranges::lower_bound and so on) take the container itself, check their requirements with concepts, and accept projections; prefer them in new code. (std::accumulate lives in <numeric> and has no ranges version in C++20; C++23 added std::ranges::fold_left.)
Three of these deserve a closer look.
lower_boundfinds the first element not less than the value in a sorted range, in O(log n) steps. It returns an iterator, and subtractingbegin()gives an index. On an unsorted range it silently gives a wrong answer, a precondition the compiler cannot check.uniquedoes not shrink the vector, because algorithms work through iterators and cannot change a container's size. It moves the kept elements to the front and returns the leftover tail, anderaseremoves that tail. This two-step dance confused programmers for decades, so C++20 addedstd::erase_ifandstd::erase, which do both in one call.std::back_inserteris an output iterator that callspush_backon each write, sotransformcan fill an empty vector.
Example— Iterator invalidation
An iterator, pointer or reference into a container is only valid while the container keeps the element where it was. Growing a vector beyond its capacity moves every element to new memory:
std::vector<int> v{1, 2, 3};
int& first = v[0];
auto it = v.begin();
v.push_back(4); // may reallocate
std::println("{}", first); // undefined behaviour if it did: first refers to freed memoryEach container documents which operations invalidate what. For std::vector: anything that may reallocate invalidates everything, and inserting or erasing invalidates everything after the position. Node-based containers (std::list, std::map) keep iterators to other elements valid. A loop that erases from the container it is iterating over is the classic place this goes wrong; std::erase_if exists partly to make that loop unnecessary.
Ranges and views: lazy pipelines
The temperatures below are invented: one afternoon at seven weather stations.
#include <algorithm>
#include <print>
#include <ranges>
#include <string>
#include <vector>
struct Reading {
std::string station;
double celsius;
};
int main() {
std::vector<Reading> readings{
{"Ushuaia", 4.5}, {"Dakar", 27.0}, {"Oslo", -3.0}, {"Chennai", 33.5},
{"Reykjavik", 1.0}, {"Manaus", 31.0}, {"Ulaanbaatar", -18.5}};
// A lazy pipeline: nothing runs until the for loop asks for elements.
auto warm = readings
| std::views::filter([](const Reading& r) { return r.celsius > 20.0; })
| std::views::transform([](const Reading& r) { return r.station; });
for (const auto& name : warm) std::print("{} ", name);
std::println("");
// Projections: sort by a member without writing a comparison.
std::ranges::sort(readings, {}, &Reading::celsius);
std::println("coldest {} hottest {}", readings.front().station, readings.back().station);
// enumerate (C++23) gives index and element together.
for (const auto& [i, r] : std::views::enumerate(readings) | std::views::take(3)) {
std::println("{}. {:<12} {:>6.1f}", i + 1, r.station, r.celsius);
}
// iota generates numbers; ranges::to (C++23) collects a view into a container.
auto squares = std::views::iota(1, 8)
| std::views::transform([](int n) { return n * n; })
| std::ranges::to<std::vector>();
std::println("{} squares, last {}", squares.size(), squares.back());
// zip walks two ranges in step; chunk splits one into groups.
std::vector<std::string> days{"Mon", "Tue", "Wed"};
std::vector<int> steps{8200, 10450, 6900};
for (const auto& [d, s] : std::views::zip(days, steps)) std::print("{}:{} ", d, s);
std::println("");
for (auto group : std::views::iota(1, 11) | std::views::chunk(4)) {
std::print("[");
for (int n : group) std::print(" {}", n);
std::print(" ] ");
}
std::println("");
}Dakar Chennai Manaus
coldest Ulaanbaatar hottest Chennai
1. Ulaanbaatar -18.5
2. Oslo -3.0
3. Reykjavik 1.0
7 squares, last 49
Mon:8200 Tue:10450 Wed:6900
[ 1 2 3 4 ] [ 5 6 7 8 ] [ 9 10 ] readings | std::views::filter(...) | std::views::transform(...) builds a view without touching a single element. Only when the for loop asks for the next element does the view pull one from readings, test it, and transform it. Views are lazy: no intermediate vectors, and work proportional to what you consume. std::views::take(3) after a sort means only three elements are ever visited.
Two C++23 additions make pipelines much more pleasant. std::views::enumerate pairs each element with its index, replacing the classic index loop. std::ranges::to collects a view into a real container, so a pipeline can end in a std::vector. std::views::zip and std::views::chunk are C++23 too. All of them work in GCC 14; the compiler support table on cppreference tells you about others.
One C++23 feature is missing in GCC 14: formatting a whole range with std::println("{}", v). It arrived in GCC 15, which is why these programs print elements in loops.
Common misconceptions
Misconception
"std::list is faster than std::vector when you insert in the middle." Inserting into a list is O(1) once you have found the position, and finding it is O(n) pointer-chasing through scattered memory. For most sizes, a vector's search plus a shift of contiguous memory is faster. Measure before choosing a list.
Misconception
"std::unordered_map is always faster than std::map." Hashing is O(1) on average, but each lookup computes a hash and may chase pointers through buckets; for small maps, string keys with expensive hashes, or code that needs ordered iteration, std::map or a sorted vector can win. The standard unordered containers are also constrained by their specification to use separate chaining, which is why libraries like Abseil and Boost offer faster open-addressing hash maps.
Misconception
"A view holds its data." Most views refer to the range they were built from. A view built from a temporary vector, or returned from a function whose local vector it refers to, dangles. The ranges library refuses some of these at compile time (a "dangling" result type), but not all. Keep views short-lived, and collect with std::ranges::to when the result must outlive its source.
Misconception
"Views run their lambdas once per element." A view may call them more or less often than you expect. filter evaluates its predicate to find each next element, sometimes one element beyond what you consume (see the exercises), and calling begin() on a filter view caches the first match. Keep lambdas in pipelines free of side effects, and the question never matters.
How professionals use the library
Know the algorithm names. find_if, any_of, all_of, count_if, transform, sort, stable_sort, partition, lower_bound, equal_range, min_element, max_element, minmax, accumulate, fold_left, iota, reverse, rotate, nth_element: a large share of everyday loops is one of these. When a reviewer sees std::ranges::any_of, they know what the code does without reading a loop body.
Reserve when you know the size. v.reserve(n) allocates once instead of repeatedly while growing, and keeps references valid until the vector exceeds n. The opposite request, shrink_to_fit, asks a vector to return spare capacity, though the library is allowed to ignore it.
Prefer clarity, then measure. Pipelines of views are elegant, but deep ones can be harder to debug and occasionally slower than a plain loop, because each layer adds iterator logic the optimiser must see through. Write the clearest version, profile, and rewrite only what the profiler points at.
Go beyond the standard when you need to. Production codebases often add Abseil or Boost containers (faster hash maps, small vectors that keep a few elements without a heap allocation). They follow the same iterator conventions, so the standard algorithms work with them unchanged.
Exercises
1. The standard library: containers, iterators, algorithms and ranges
Warm-upComputationalWhat does this program print?
#include <map>
#include <print>
#include <string>
int main() {
std::map<std::string, int> m;
m["pear"] = 3;
m["apple"] = 5;
m["fig"] = 1;
m["apple"] += 2;
for (const auto& [k, v] : m) std::print("{}{} ", k, v);
std::println("");
}
2. The standard library: containers, iterators, algorithms and ranges
CoreComputationalWhat does this program print?
#include <algorithm>
#include <print>
#include <vector>
int main() {
std::vector<int> v{2, 4, 4, 4, 7, 9};
auto lo = std::ranges::lower_bound(v, 4);
auto hi = std::ranges::upper_bound(v, 4);
std::println("{} {} {}", lo - v.begin(), hi - v.begin(), hi - lo);
}
3. The standard library: containers, iterators, algorithms and ranges
CoreComputationalThe program below prints the values from a view pipeline, then |, then how many times the filter's predicate was called. What do you expect the values part to be? Type only the two numbers before the |.
std::vector<int> v{3, 8, 1, 9, 4, 7};
int calls = 0;
auto odd = [&calls](int x) { ++calls; return x % 2 == 1; };
auto r = v | std::views::filter(odd)
| std::views::transform([](int x) { return x * 10; })
| std::views::take(2);
for (int x : r) std::print("{} ", x);
std::println("| {} calls", calls);
4. The standard library: containers, iterators, algorithms and ranges
StretchComputationalIn the previous exercise's program, how many times was the predicate odd called in total, as printed by GCC 14? (Think about what the range-for loop does after it receives the second element.)
5. The standard library: containers, iterators, algorithms and ranges
Warm-upComputationalThis program inserts the characters of a word into a std::set and prints them. Enter the characters it prints (each as one answer).
std::set<char> letters;
for (char c : std::string("banana")) letters.insert(c);
for (char c : letters) std::print("{}", c);
6. The standard library: containers, iterators, algorithms and ranges
CoreHumanA program reads about 200,000 (word, count) updates from a text, looks up words very often, and at the end prints every word in alphabetical order once. Which approach is the most sensible starting point?
7. The standard library: containers, iterators, algorithms and ranges
CoreHumanstd::vector<int> v holds 4 elements and has capacity 4. int* p = &v[1]; Which of the following operations may leave p dangling? Select all that apply.
Further reading and resources
- Containers library · cppreference.comEvery container, with the complexity of each operation and its iterator-invalidation rules.
- Algorithms library · cppreference.com
- Ranges library · cppreference.com
- Abseil: Swiss tables and other containersGoogle's open-source C++ library, whose hash maps are a common faster alternative to std::unordered_map.