Chapter 18: Algorithms and Ranges

The algorithms library is a treasure chest of generic building blocks. You provide iterator or range boundaries and a policy, then the algorithm performs well tested operations that respect complexity guarantees. The ranges library extends this with composable views that form pipelines and evaluate lazily; the result is expressive code that stays efficient and predictable.

Classic algorithms and complexity

Classic algorithms operate directly on iterator pairs and follow well understood asymptotic rules. Sorting and partitioning are logarithmic or linearithmic; searches and transforms are linear; constant time operations apply to moves and swaps. Understanding these rules helps avoid quadratic traps and guides container choices.

Sorting, partitioning, and searching

std::sort is the workhorse with average complexity O(n log n); std::stable_sort preserves order of equal elements with higher space cost. Partitioning splits ranges based on predicates. Binary search family functions (such as lower_bound) work on sorted ranges and give logarithmic time for lookups.

std::vector<int> v{3,1,4,1,5,9};
std::sort(v.begin(), v.end());
auto it = std::lower_bound(v.begin(), v.end(), 4);

Transformations and accumulations

Transform algorithms apply functions or functors element by element. Accumulations reduce a range into a single value using an initial seed. These operations act on value types and avoid manual loops while keeping complexity linear.

std::vector<int> v{1,2,3};
std::transform(v.begin(), v.end(), v.begin(),
               [](int x){ return x * x; });
int sum = std::accumulate(v.begin(), v.end(), 0);

In place reordering

Rotations, shuffles, swaps, and reversal algorithms modify the ordering of elements. They provide both readability and correct complexity so you can adjust structure without reinventing the operations.

std::vector<int> v{1,2,3,4};
std::rotate(v.begin(), v.begin() + 2, v.end());
std::reverse(v.begin(), v.end());

Range views and adaptors

Views are lightweight range facades that compute elements on demand. They do not own storage; instead they transform, filter, or slice underlying data. Adaptors combine views in pipeline expressions, giving clear structure over sequences without materializing intermediate containers.

Core views: filter, transform, take, drop

Using views follows the pattern input | adaptor1 | adaptor2 …. Filter keeps elements that satisfy a predicate; transform applies a function lazily; take and drop select leading or trailing segments; all operate with constant storage.

auto odds = std::views::iota(1, 20)
           | std::views::filter([](int x){ return x % 2; })
           | std::views::transform([](int x){ return x * 2; })
           | std::views::take(5);

Slicing and joining

std::views::drop_while, take_while, slide, and join offer finer structure. Sliding windows expose fixed width frames across the range; joining flattens nested ranges into a single stream of elements.

std::string s = "hello";
for (auto w : s | std::views::slide(2)) {
  // each w is a two character view …
}

Projections and custom comparators

Many algorithms accept projections, which extract a member or compute a surrogate value before comparison. This replaces hand written lambdas and keeps intent close to the algorithm call. Custom comparators let you define ordering rules for sorting or searching that match your domain.

Projections for cleaner algorithms

Projections let algorithms sort or search by fields without restructuring data. The projection applies to each element before the comparator; typically you use a pointer to member or a simple lambda.

struct Item { int id; std::string name; };
std::vector<Item> items{{2,"beta"},{1,"alpha"}};
std::ranges::sort(items, std::less<>{}, &Item::id);

Comparators for order and equality

A comparator is a strict weak ordering. It defines what counts as less than and must be consistent for algorithms to behave. Equality under a comparator does not imply bit equality; it only means neither element is less than the other.

std::ranges::sort(items,
  [](auto& a, auto& b){ return a.name < b.name; });

Pipelines and lazy evaluation

Pipelines chain adaptors and algorithms to express flowing transformations. Because views evaluate lazily, only the elements demanded by the sink are touched. This enables infinite sequences, on the fly computation, and efficient filtering.

Lazy processing with views

Most views do not allocate; they create small wrapper objects that pass through elements when iterated. Effects like transformation or filtering happen during iteration rather than at composition time. This keeps memory use low and keeps pipelines predictable.

auto squares = std::views::iota(1)
             | std::views::transform([](int x){ return x * x; });

for (int x : squares | std::views::take(4)) {
  // x visits 1,4,9,16 …
}

Composing pipelines

You can mix algorithms and views in expressive chains. Algorithms like std::ranges::find operate directly on view pipelines without breaking the lazy structure. This style makes dataflow clear and minimizes intermediate work.

auto data = std::views::iota(0, 100)
          | std::views::filter([](int x){ return x % 3 == 0; });
int first = *std::ranges::find(data, 33);

Parallel algorithms

Parallel algorithms use execution policies to run work across threads. They keep interfaces similar to sequential counterparts while enabling speedups on large data sets. Not every algorithm benefits from parallelism; overhead and cache effects still matter.

Execution policies and behavior

Policies such as std::execution::par and std::execution::par_unseq control concurrency and vectorization. Sequential policies preserve order; unsequenced ones allow aggressive reordering and require operations to be free of data races. Results are defined when the policy permits them; nondeterministic ordering is possible under parallel policies.

std::vector<int> v(1'000'000);
std::iota(v.begin(), v.end(), 0);
std::sort(std::execution::par, v.begin(), v.end());

When parallelism helps

Parallel sorts, transforms, and reductions show gains when data sizes are large and operations are simple. Memory bandwidth becomes the limiter. Measure with realistic workloads and hardware; small ranges often run faster with sequential algorithms.