Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Algorithms are the loops

A hand-written loop hides intent. Chapter 04 showed that a loop can miss an off-by-one error and can expose lifetime bugs when a pointer is taken to an element that later moves. A named algorithm states exactly what happens: find the value, count the matches, transform each element. The reader understands the code without inspecting the body.

Algorithms operate on iterator pairs, making them generic over containers and element types. The same call works for std::vector, std::array, std::list, or any range providing iterators, and for int, std::string, or a user type with operator<. This uniformity removes boilerplate, reduces bugs, and lets one algorithm serve every container.

Every standard algorithm carries a documented complexity guarantee. std::find and std::count_if run in linear time because they can inspect each element. std::sort guarantees O(n log n) comparisons in the worst case. Knowing these bounds helps you choose the right tool on a performance-critical path. If you need only the smallest element, std::min_element is cheaper than a full sort because it stops after a single linear scan.

The iterator pair model

All standard containers expose begin() and end(). They define a half-open range [begin, end). The range includes the element pointed to by begin and excludes the element pointed to by end. This convention lets algorithms stop exactly at the last element without an extra check.

#include <vector>
#include <algorithm>
#include <print>

int main() {
    std::vector<int> v{1,4,7,10};
    int target = 7;
    auto it = std::find(v.begin(), v.end(), target);
    if (it != v.end())
        std::println("found {}", *it);
    else
        std::println("not found");
    return 0;
}

The program creates a std::vector<int>, calls std::find, and prints whether the target value was found.

Non-modifying sequence algorithms

The library provides many read-only algorithms. std::find returns an iterator to the first element equal to a value. std::count returns the number of elements equal to a value. The trio std::all_of, std::any_of, and std::none_of evaluates a predicate over a range. std::count_if counts elements that satisfy a predicate.

Beyond std::find, std::count, and the all_of family, the library offers std::mismatch to find the first differing position between two ranges, std::equal to test equality, and std::search to locate a subrange. These algorithms never alter the container, so you can call them on a const object.

std::find_if takes a predicate instead of a value, locating the first element that satisfies a condition. std::find_first_of finds the first element that matches any value from a second range. These variants cover the common cases where you search by property rather than by equality.

std::for_each applies a callable to each element. It is the algorithm-shaped alternative to a raw range-for loop, and it makes the intent visible at the call site. std::adjacent_find locates the first pair of neighbouring elements that satisfy a condition, which is useful for detecting duplicates or trends in a sequence.

Modifying algorithms

Algorithms that write to a destination include std::copy, std::transform, std::fill, and std::replace. They accept iterator pairs for the source and destination. std::transform applies a unary operation to each source element and writes the result to the destination range.

#include <vector>
#include <algorithm>
#include <print>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5};
    std::vector<int> out(v.size());
    std::transform(v.begin(), v.end(), out.begin(), [](int x){ return x * x; });
    std::println("squared:");
    for (int n : out) std::print("{} ", n);
    std::println("");
    return 0;
}

The program prints the squared numbers. The destination must have room for every written element. std::back_inserter grows the container as needed.

std::remove and std::remove_if shift the kept elements to the front and return a new logical end. They do not erase anything. The erase-remove idiom combines the two: call erase with the iterator pair the algorithm returns to drop the unwanted tail in one statement. This avoids building a second container and reuses the original storage.

Beyond transform and remove, the library offers std::fill to assign a value to every element, std::replace to swap one value for another, std::rotate to cycle a subrange, and std::partition to group elements that satisfy a predicate before those that do not. Each returns the iterator or range you need to continue working without re-scanning.

std::unique removes consecutive duplicates, so it is effective only on a sorted range. Pair it with std::sort to drop all duplicates, then erase the trailing run as with remove.

std::sort rearranges elements into ascending order using operator<. std::stable_sort preserves the relative order of equal elements. After sorting, binary search algorithms become valid. std::binary_search reports whether a value exists in a sorted range. std::lower_bound returns the first position where a value can be inserted without breaking order. std::upper_bound returns the position after the last equal element.

The precondition matters. Running std::lower_bound on an unsorted range yields undefined results. The algorithm assumes monotonic ordering and will silently produce the wrong answer.

#include <vector>
#include <algorithm>
#include <print>

int main() {
    std::vector<int> v{5, 2, 9, 1, 5, 6};
    std::sort(v.begin(), v.end());
    std::println("sorted:");
    for (int n : v) std::print("{} ", n);
    std::println("");
    int key = 5;
    auto it = std::lower_bound(v.begin(), v.end(), key);
    if (it != v.end() && *it == key)
        std::println("lower_bound of {} is at index {}", key, std::distance(v.begin(), it));
    else
        std::println("key not found");
    return 0;
}

The program sorts a vector and uses std::lower_bound to locate the first occurrence of a value.

When you need only part of the order, do not pay for a full sort. std::partial_sort orders the first K elements and leaves the rest unspecified. std::nth_element places the Kth element in its sorted position and partitions the rest around it, all in linear time. These are the right tools for top-K and median queries.

Prefer std::stable_sort when equal elements carry order-dependent meaning, such as log entries that must stay chronological. The extra cost is small and the guarantee prevents subtle bugs when the sorted result feeds another pass.

Ranges (C++20)

C++20 introduced std::ranges. Ranges remove the need to pass iterator pairs. An algorithm can operate directly on a range object. The pipe syntax | composes adaptors that transform or filter the data before a terminal algorithm consumes it. Views are lazy: no intermediate container is allocated, and a pipeline can stop early.

#include <vector>
#include <ranges>
#include <print>

int main() {
    std::vector<int> v{1,2,3,4,5,6};
    auto pipeline = v
        | std::views::filter([](int x){ return x % 2 == 0; })
        | std::views::transform([](int x){ return x * x; });
    std::println("even squares:");
    for (int n : pipeline) std::print("{} ", n);
    std::println("");
    return 0;
}

The pipeline filters even numbers, squares them, and prints the result.

The adaptor set is larger than filter and transform. std::views::take keeps the first N elements, std::views::drop skips them, std::views::reverse inverts order, and std::views::split breaks a range on a delimiter. Because each view is lazy, v | std::views::filter(f) | std::views::take(3) examines elements only until three match. A ranges algorithm returns a view or subrange, so the result can feed another pipeline directly.

std::views::iota generates a numeric sequence without storing it, so std::views::iota(0, n) replaces a hand-written counter loop. Combined with filter and transform, it builds lazy numeric pipelines that allocate nothing. Ranges algorithms also accept projections on the terminal call, so std::ranges::sort(v, {}, &Point::x) sorts by the x member directly. std::ranges::to materialises a view into a concrete container when you finally need ownership, for example auto v = range | std::views::filter(f) | std::ranges::to<std::vector>(). This keeps the pipeline lazy until the boundary where storage is required.

Projection and comparator

std::ranges algorithms accept a projection argument. A projection extracts a member or computes a value before the algorithm compares or orders elements. This removes the need for an explicit comparator lambda. For example, sorting a vector of Point structs by the y coordinate needs no lambda:

struct Point { int x; int y; };
std::vector<Point> pts = {{1,5},{2,3},{4,7}};
std::ranges::sort(pts, {}, &Point::y);

The projection &Point::y tells the algorithm to compare the y members directly. The same idea applies to std::ranges::unique or std::lower_bound when you compare on a particular attribute.

Reduction

For many problems you need to combine a sequence of values into a single result. std::accumulate takes a beginning iterator, an ending iterator, and an initial value, then applies a binary operation (addition by default) to combine each element with the running total. std::ranges::fold_left is the ranges equivalent.

#include <vector>
#include <numeric>
#include <print>

int main() {
    std::vector<int> v{1,2,3,4,5};
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::println("sum = {}", sum);
    return 0;
}

The example builds a vector of five integers and computes their sum.

std::reduce is the parallel-friendly sibling of std::accumulate. It permits reordering of the operations, which lets an execution policy split the work across cores, but it requires the operation to be associative and the initial value to be an identity. Use std::accumulate when order matters and std::reduce when you only need the combined value.

std::inner_product combines two ranges with two operations. It multiplies corresponding elements and adds the products, which computes a dot product in one call. This is the reduction form of a zip operation, and it shows how a single algorithm can express what is otherwise a nested loop. The two-operation form generalises to any pair of associative combiners, so it can compute weighted sums or concatenations across two sequences in a single pass.

Algorithmic design patterns

Common tasks compose standard algorithms. Use filter‑map‑reduce: std::views::filter, std::views::transform, then std::accumulate or std::ranges::fold_left. Apply the erase‑remove idiom to discard elements without extra storage. Recognising these patterns yields concise code that leverages library guarantees.

Parallel policies

Many algorithms accept an execution policy as the first argument. std::execution::par asks the implementation to run the work in parallel when it can. Support for parallel policies is optional in the standard and depends on the compiler and its runtime backend. On some toolchains std::execution::par is unavailable or falls back to sequential execution. Treat parallel overloads as a performance option, not a correctness feature. When you use them, remember that order-unstable algorithms can reorder equal elements, so tests must check value-level properties such as sums rather than exact sequence.

std::vector<int> v = {3, 1, 4, 1, 5};
std::sort(std::execution::par, v.begin(), v.end());

Common pitfalls

  • Binary search on an unsorted range is undefined behaviour. Sort first.
  • Invalidated iterators. std::sort can invalidate all iterators. Reacquire them after sorting.
  • Iterator category mismatch. std::sort requires random‑access iterators. std::list iterators fail to compile.
  • Destination too small. std::copy and std::transform write exactly as many elements as the source supplies. Use std::back_inserter or size the destination first.
  • Sorting a node‑based container. std::list lacks random‑access iterators. Use its member list::sort instead.
  • Projection side effects. A projection must be pure. State‑modifying projections break algorithm invariants.

Try this

Use std::ranges to keep only the even elements of a std::vector<int>, square them, sort the result, and print each number on a single line.

// Write your solution here.

No solution is provided. The reader must fill in the code.