# 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.

```cpp
{{#include ../../examples/ch12/ch12_find.cpp}}
```

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.

```cpp
{{#include ../../examples/ch12/ch12_transform.cpp}}
```

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.

## Sorting and binary search

`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.

```cpp
{{#include ../../examples/ch12/ch12_sort.cpp}}
```

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.

```cpp
{{#include ../../examples/ch12/ch12_ranges.cpp}}
```

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:

```cpp
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.

```cpp
{{#include ../../examples/ch12/ch12_accumulate.cpp}}
```

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.

```cpp
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.

```cpp
// Write your solution here.
```

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