The Algorithm Library and Why to Prefer It to a Loop

Part I · Module 20 · Chapter 20.4 · The Algorithm Library and Why to Prefer It to a Loop

1. What the Library Contains

The algorithms live in <algorithm> and <numeric>, and they are function templates taking iterator ranges rather than containers. Grouped by what they do, the useful ones are:

Non-modifying inspection — find, find_if, find_if_not, count, count_if, all_of, any_of, none_of, for_each, search, adjacent_find, mismatch, equal, min_element, max_element, minmax_element. Chapter 20.5.

Binary search on sorted input — binary_search, lower_bound, upper_bound, equal_range. Also Chapter 20.5.

Ordering — sort, stable_sort, partial_sort, nth_element, is_sorted, is_sorted_until. Chapter 20.6.

Modifying and producing — copy, copy_if, copy_n, move, transform, fill, generate, replace, replace_if, reverse, rotate, shuffle, swap_ranges, unique, remove, remove_if. Chapter 20.7 covers transform; remove was Chapter 20.3 §7.

Partitioning — partition, stable_partition, partition_point, is_partitioned.

Numeric folds — accumulate, reduce, inner_product, partial_sum, adjacent_difference, iota. Chapter 20.7.

Set operations on sorted ranges — set_union, set_intersection, set_difference, set_symmetric_difference, includes, merge.

Heap operations — make_heap, push_heap, pop_heap, sort_heap.

That is the recall problem solved: nine groups, and knowing the group is enough to find the name.

Two naming conventions are worth internalising. A _if suffix means the algorithm takes a predicate instead of a value — find versus find_if. A _copy suffix means it writes to a separate destination instead of modifying in place — remove_copy, reverse_copy, replace_copy.

2. The Claim This Chapter Does Not Make

The usual argument for the library is that it is faster, on the grounds that implementers tune it and you do not. The honest version of that argument is narrower, and it is worth measuring rather than repeating.

Two functions, each marked noinline so the comparison is between their bodies and not between inlining decisions:

__attribute__((noinline))
std::ptrdiff_t byHand(const std::vector<int>& v, int target)
{
    for (std::size_t i = 0; i < v.size(); ++i)
        if (v[i] == target) return (std::ptrdiff_t)i;
    return -1;
}
__attribute__((noinline))
std::ptrdiff_t byAlgorithm(const std::vector<int>& v, int target)
{
    auto it = std::find(v.begin(), v.end(), target);
    return it == v.end() ? -1 : it - v.begin();
}

The generated code is genuinely different:

byHand      : 13 instructions, 0 calls  -- a scalar loop
byAlgorithm : 22 instructions, 1 call   -- bl _wmemchr

That bl _wmemchr is the interesting part. libc++ recognises std::find over a trivially-comparable four-byte type and dispatches to the C library's wmemchr, which is hand-written and typically vectorised. The hand loop cannot reach that routine — it compiles to a thirteen-instruction scalar compare-and-branch.

So the library is doing something cleverer. Now the timing, scanning four million integers to the last element so the whole range is traversed:

byHand         4.014 ms  [ 2.993- 7.184]
byAlgorithm    4.258 ms  [ 3.181- 9.724]

And across seven whole-process runs the ratio came out 0.18, 0.74, 0.93, 1.04, 0.83, 1.17 and 0.80 — scattered around 1.0, with the spread dominated by machine load rather than by either implementation.

They are indistinguishable. The reason is Chapter 19.8 §5's: four million ints is sixteen megabytes, the scan is limited by how fast memory can be delivered, and whether the inner loop issues a scalar compare or a SIMD one makes no difference when both are waiting. The wmemchr dispatch is real in the codegen and invisible in the measurement.

The same holds for a predicate, where no such dispatch exists:

hand loop      3.747 ms     count_if       3.361 ms

with a ratio of 0.70 to 5.58 across runs and a median near 1.1 — also indistinguishable.

So: the standard algorithms are not measurably faster than competent hand-written loops on this platform for these operations. Anyone who tells you otherwise should be asked for their measurement. The case for using them is made on other grounds, and those grounds are strong enough not to need a false one.

3. The First Real Reason: It States Intent

A loop describes a mechanism. A named call describes a result. Compare:

// mechanism
bool found = false;
for (std::size_t i = 0; i < v.size(); ++i)
    if (v[i] == target) { found = true; break; }

// result
bool found = std::find(v.begin(), v.end(), target) != v.end();

The second version cannot be misread. The first requires a reader to notice the break, confirm the found flag is not used before assignment, and check that the comparison is == and the bound is size() and the start is 0. None of that is hard; all of it is work, and it is work repeated at every reading.

The effect compounds when the operation is less common. A reader who meets std::rotate can look it up once and know it forever; a reader who meets a hand-written rotation has to re-derive it from the index arithmetic every time. Chapter 20.10 builds a complete pipeline out of nine named steps, and the argument there is that the pipeline is readable precisely because no step requires reconstruction.

There is a related benefit that is easy to overlook: the name is searchable and the loop is not. A codebase can be grepped for stable_partition; it cannot be grepped for the loop someone wrote instead.

4. The Second Real Reason: No Index Arithmetic

Every hand-written loop contains a bound, a start and a step, and each is an opportunity for an off-by-one. The named call contains none of them, because the range is [begin, end) and the algorithm supplies the traversal.

This is not hypothetical. The standard off-by-one inventory is: starting at 1 instead of 0, writing <= instead of <, comparing against size() after a modification, and iterating size() - 1 on an empty container where size() is unsigned and the expression wraps to a very large number. That last one is Chapter 3.3 §4's guaranteed unsigned wraparound, and in a loop bound it is a long scan through unmapped memory rather than a visible error.

for (std::size_t i = 0; i < v.size() - 1; ++i) ...   // v empty: i < SIZE_MAX

A named algorithm cannot express that mistake, because it never names a bound.

5. The Third Real Reason, and the Strongest

Chapter 20.3 measured a three-line loop that removes elements while iterating. It returns the correct answer when duplicates are separated and the wrong answer when they are adjacent, and -O0, -O2, AddressSanitizer, UndefinedBehaviorSanitizer and libc++ debug hardening all ran it to completion, exited 0 and printed nothing.

The remove-erase form of the same operation cannot contain that bug:

v.erase(std::remove(v.begin(), v.end(), 2), v.end());

There is no iterator for you to invalidate, no increment for you to misplace, and no position to hold across a modification. The bug is not avoided by care; it is unexpressible.

That is a different kind of argument from the first two. Intent and off-by-ones are about the probability of a mistake. This is about its possibility. And it is the argument that generalises best, because the whole catalogue of loop bugs — invalidating an iterator, modifying the container you are traversing, forgetting to advance in one branch, breaking out of the wrong level — are bugs about iteration, and the algorithm is the thing that owns the iteration.

The C++20 form, std::erase(v, 2), removes even the pairing mistake from Chapter 20.3 §7.

6. When a Loop Is the Right Answer

The advice is to prefer the algorithm, not to ban the loop, and there are cases where the loop wins honestly.

When no algorithm fits. There is no transform_if, so filtering and mapping in one pass over a large range either takes two algorithms and an intermediate container or takes a loop. Chapter 20.7 §6 measures the two-step idiom; for a hot path over a huge range the loop is defensible. C++20's ranges fix this properly with a lazy view.

When the body needs several elements at once. An algorithm hands you one element. A sliding window over three, or a comparison with a running previous value, is often clearer as a loop — though std::adjacent_difference and std::adjacent_find cover the common cases.

When the loop has multiple exits or side effects in several branches. An algorithm with a predicate that has side effects is hard to reason about, and for_each with a stateful lambda is usually worse than the loop it replaced.

When the composed form would need an intermediate container whose allocation is the dominant cost. Measure it before assuming, since Chapter 19.3 §4 showed one reserve often removes the concern.

When you are writing the algorithm. Someone has to.

The test to apply: does the named version say what this does? If it does, use it. If expressing it in algorithms requires three passes and a temporary vector to avoid one loop, the loop is clearer, and clarity was the whole argument in the first place.

7. Composing Them

Algorithms compose through ranges, and the two patterns worth knowing are the filter-then-process shape and the in-place shape.

// filter into a new range, then process it
std::vector<Txn> sel;
std::copy_if(log.begin(), log.end(), std::back_inserter(sel), isInteresting);
std::sort(sel.begin(), sel.end(), byAddress);
long long total = std::accumulate(sel.begin(), sel.end(), 0LL, addLatency);

// or partition in place when you want both halves
auto cut = std::stable_partition(all.begin(), all.end(), isFast);
// [begin, cut) are fast, [cut, end) are slow -- one pass, no copy

std::back_inserter is what makes the first form work on an empty destination — Chapter 20.1 §9, and Chapter 20.7 §5 measures what happens without it.

The partition form is worth preferring when you need both halves, because it is one pass and no allocation where two copy_if calls are two passes and two containers. Chapter 20.10 §7 measures it splitting 20,000 transactions in one pass.

8. The Execution Policies, Briefly

C++17 added an optional first argument that asks for parallel or vectorised execution:

std::sort(std::execution::par, v.begin(), v.end());

seq, par, par_unseq and unseq are the policies. This is the one place where the "the library is faster" argument can be true in a way a hand loop cannot easily match, since you are getting multithreading for one extra argument.

Two caveats before reaching for it. The policies are a request; an implementation may ignore them, and support varies — libc++ did not implement them for a long time, so code using them is less portable than it looks. And a parallel policy changes the requirements on your callable: it must be safe to call concurrently on different elements, which rules out anything capturing shared mutable state by reference. A predicate that increments a captured counter is correct under seq and a data race under par.

So: know they exist, check your implementation before relying on them, and measure rather than assume.

9. The Naming Patterns

10. What to Actually Do

• Reach for a name before writing a loop, and use §9's table to find it.
• Do not claim the library is faster. Measured here as indistinguishable; say "clearer and safer" instead.
• Prefer the algorithm most strongly where iteration is the risk — removal, filtering, anything modifying while traversing.
• Use std::erase_if (C++20) or remove-erase, never a hand-written erase loop.
• Use std::back_inserter when the destination has no room.
• Use stable_partition when you want both halves, instead of two copy_if passes.
• Write the loop when no algorithm fits — and §6's test is whether the named version says what it does.
• Learn the _if and _copy suffixes. They halve the names you have to remember.
• Check your implementation before using execution policies, and never pass a callable with shared mutable state to par.
• Keep the predicate pure. A predicate with side effects is hard to reason about under any policy.

11. Mistakes Worth Making Once

Writing the erase loop by hand. Chapter 20.3's measurement is the reason this chapter exists.

std::remove without erase. The size does not change and the tail holds plausible values.

Assuming std::find is faster because it is in the library. Measured indistinguishable — and the codegen difference is real, which makes the wrong conclusion tempting.

Transforming into an empty destination without back_inserter. No storage, no diagnostic.

Reaching for std::for_each with a stateful lambda where a range-based for was clearer. The algorithm is not automatically better.

Composing four algorithms and two temporaries to avoid one loop. You have spent the clarity you were buying.

Calling a set algorithm on unsorted input. Both ranges must be sorted; Chapter 20.5 §6 measures what the binary-search family does when that is violated.

Passing a counter-incrementing lambda to a par algorithm. Correct under seq, a data race under par, and the compiler will not say so.

12. Interview Relevance

The frozen curriculum marks this chapter High, and the question is usually open-ended enough that the quality of the reasoning is what is being assessed.

"Why prefer standard algorithms to hand-written loops?" The answer that stands out leads with correctness rather than speed: a named call cannot contain an iteration bug, it has no index arithmetic, and it states intent. Volunteering that the speed claim is often overstated — and that you have measured it — is a strong signal.

"Is std::find faster than a hand-written loop?" No, measurably. It may compile to something different — here a wmemchr call against a scalar loop — and finish in the same time because the scan is memory-bound.

"When would you write the loop instead?" No algorithm fits, the body needs several elements, multiple exits, or the composed version needs a temporary whose cost dominates. Naming transform_if as the specific gap is a good detail.

"What is the difference between remove and erase?" remove is an algorithm with only iterators, so it compacts and returns a new logical end without changing the size; erase is the member that truncates. They are one operation in two calls, and C++20's std::erase merges them.

"What does the _if suffix mean?" Takes a predicate rather than a value. And _copy means it writes elsewhere instead of in place.

"Have you used the execution policies?" The honest answer about portability and about the concurrency requirement on the callable is better than enthusiasm.

13. What You Should Be Able to Say Now

• The nine groups the library divides into, and the _if / _copy conventions.
• That std::find dispatched to wmemchr while the hand loop compiled to 13 scalar instructions — and that the two were indistinguishable in time, with ratios of 0.18–1.17 over seven runs.
• Why that happened: at 16 MB the scan is memory-bandwidth-bound.
• The three arguments that do hold, and that only the third changes what is possible rather than what is likely.
• That v.erase(std::remove(...), v.end()) cannot contain Chapter 20.3's bug because it has no iterator to invalidate.
• The five cases in §6 where a loop is the right answer, and the test to apply.
• That execution policies are a request, vary by implementation, and change the requirements on your callable.
• That a named algorithm is greppable and a loop is not.

14. Exercises

Exercise 1 — the codegen. Reproduce §2's two functions, dump the assembly, and find the wmemchr call. Then change the element type to a struct and see what happens to the dispatch.

Exercise 2 — the timing. Reproduce the comparison with medians and ranges. Report whether your ranges overlap. Then shrink the range to 10,000 elements so it fits in cache and re-measure — state whether the dispatch becomes visible.

Exercise 3 — the rewrite. Take ten loops from your own code and rewrite each as one or more named algorithms. Note which ones got worse and why.

Exercise 4 — the impossible bug. Write the erase bug, then write the remove-erase version, and argue in two sentences why the second cannot have the defect.

Exercise 5 — the off-by-one inventory. Write four loops each containing one of §4's four classic off-by-ones. For each, state whether any tool catches it.

Exercise 6 — the missing algorithm. Implement filter-then-transform three ways: two algorithms with a temporary, one loop, and std::transform into a back_inserter after copy_if. Compare readability and allocations.

Exercise 7 — partition. Replace a two-pass copy_if split with one stable_partition and verify the halves and the allocation count.

Exercise 8 — the policy trap. Write a count_if whose predicate increments a captured counter, run it under seq and under par if your implementation supports them, and explain the result.

15. Summary

• About a hundred algorithms in nine groups, with _if meaning "takes a predicate" and _copy meaning "writes elsewhere".
• Measured codegen: std::find compiles to bl _wmemchr — a tuned libc routine — while the hand loop compiles to 13 scalar instructions, 0 calls.
• Measured speed: indistinguishable. Ratios of 0.18 to 1.17 across seven runs; the predicate comparison likewise, median ~1.1. Sixteen megabytes is memory-bandwidth-bound, so the inner loop's form does not show up.
• So the library is not measurably faster, and the chapter declines to claim it is.
• Three real reasons: it states intent rather than mechanism; it contains no bound, start or step and so no off-by-one; and it structurally cannot contain Chapter 20.3's invalidation bug.
• Only the third changes what is possible rather than what is likely — and that bug was correct on one input, wrong on another, and silent under five tool configurations.
• A loop is right when no algorithm fits, the body needs several elements, there are multiple exits, or the composition would cost a dominating temporary.
• Compose with copy_if + back_inserter, or stable_partition when both halves are wanted.
• Execution policies are a request, vary by implementation, and require a callable that is safe to call concurrently.
• A named algorithm is greppable. A loop is not.

The next three chapters go through the groups that matter most, and each one leads with a measurement of what goes wrong rather than a catalogue of signatures. Chapter 20.5 is searching and counting, and it ends on the precondition that the binary-search family depends on — with a measurement in which every one of six lookups returned the wrong answer on data that contained every value being looked for, while the program exited 0 and no tool said anything at all.