---
title: Algorithms
source: 'https://academia.sh/en/courses/cpp-standard-library/algorithms'
course: 'Resource Management and the Standard Library'
language: en
updated: '2026-09-26T03:02:47+00:00'
license: 'CC BY-SA 4.0'
objectives:
    - "Measures that std::sort changes a container's element order in place"
    - 'Shows that read-only algorithms (count, find_if, accumulate) leave the source unchanged'
    - 'Explains how algorithms that take a comparison predicate apply a custom ordering rule'
    - 'Recognizes that an algorithm works with an iterator pair and does not depend on the container'
---

# Algorithms

The measurement of how std::sort changes a vector in place, and how read-only algorithms such as std::count leave the source unchanged.

The previous lesson showed that reading an iterator after `erase` is
**unspecified**, while the new iterator `erase` returns stays valid. That
lesson tracked a single position. This lesson widens the boundary back
out: it turns to the standard library's ready-made algorithms that
operate on **all** of a container's elements. What does `std::sort` leave
in the source when it sorts a `vector`? This same question will be asked
again for every algorithm in this lesson; some algorithms read the source
and never change it, while others permanently reorder the source itself,
and this difference is drawn not from the algorithm's name but from its
standard definition.

## `std::sort`: An Algorithm That Changes in Place

`std::sort` arranges the elements in the given iterator range according
to the specified ordering rule **in place** — it returns no new container,
it changes the given range itself. The default rule is `operator<`.

```cpp
// sort-in-place.cpp — how std::sort changes a vector
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> numbers{40, 10, 30, 20};

    std::sort(numbers.begin(), numbers.end());

    std::printf("sorted array:");
    for (int value : numbers) {
        std::printf(" %d", value);
    }
    std::printf("\n");
    return 0;
}
```

```text
sorted array: 10 20 30 40
```

**SL13.** After the call to `std::sort`, `numbers`'s element count did not
change, but the elements' **order** changed — the kind of this operation
is **changed**. The standard guarantees exactly which final arrangement
results after sorting (ascending, by the `operator<` rule), so the
outcome is not unspecified, it is on the contrary predictable and
repeatable. This is what separates `sort` from `erase` in the previous
lesson: the iterator `erase` left behind was unspecified, but the array
`sort` leaves behind is defined.

## Read-Only Algorithms: The Ones That Leave the Source Unchanged

Not every algorithm changes the source. `std::count` returns the number
of elements equal to the given value; `std::find_if` returns an iterator
to the first element that satisfies a predicate; `std::accumulate`
accumulates the elements by summing them. All three only read the range.

```cpp
// read-only-algorithms.cpp — do count, find_if, accumulate change the source
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> numbers{4, 7, 2, 7, 9};
    auto before = numbers;

    long count = std::count(numbers.begin(), numbers.end(), 7);
    auto it = std::find_if(numbers.begin(), numbers.end(),
        [](int value) { return value > 8; });
    int total = std::accumulate(numbers.begin(), numbers.end(), 0);

    std::printf("count of 7 %ld\n", count);
    std::printf("first value greater than 8 %d\n", *it);
    std::printf("total %d\n", total);
    std::printf("did the source change %s\n", (numbers != before) ? "yes" : "no");
    return 0;
}
```

```text
count of 7 2
first value greater than 8 9
total 29
did the source change no
```

**SL14.** All three algorithms only read `numbers`; at the end of the
operation the source is equal to its pre-operation copy — the kind is
**unchanged**. This stands in direct contrast to `std::sort`: both
operate on the same `vector`, but `sort` changes the ordering while these
three algorithms never touch the ordering at all. An algorithm's name
usually indicates its intent — the verbs `count`, `find`, `accumulate`
say "query," the verbs `sort`, `reverse`, `transform` say "change" — but
this is a convention, not a guarantee; the definitive answer is always in
the algorithm's standard definition.

## This Course Does Not Count: The Measurement Axis Is Not Run Count

`Traits, Generics and Error Handling` (Rust, M10/K03) made the runtime
cost of abstraction visible by measuring how many times a body **runs** —
what was measured there was how many times a call was repeated. This
course works on a different axis and **does not count**: a number such as
the `2` that `std::count` returns is a **result** that states how many
elements equal the sought value, not a measurement of how many times the
algorithm was called or how many times a body ran. The question this
lesson always asks is the same: which kind (unchanged/changed/empty/unspecified)
did an operation leave the source in? `std::count` itself is called once
and leaves the source **unchanged**; how many comparisons it performs
internally is not this measurement's subject. This distinction matters so
a reader does not mix up the two courses: a reader who wants to learn the
runtime cost of abstraction looks to `rust-soyutlama`; a reader who wants
to learn what state an operation leaves the source in looks to this
course.

## A Custom Comparison Predicate

`std::sort` can take a third argument: a predicate that compares two
elements. This predicate replaces `operator<`, and the programmer defines
the ordering rule.

```cpp
// sort-predicate.cpp — descending order with a custom comparison
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> numbers{40, 10, 30, 20};

    std::sort(numbers.begin(), numbers.end(),
        [](int a, int b) { return a > b; });

    std::printf("descending:");
    for (int value : numbers) {
        std::printf(" %d", value);
    }
    std::printf("\n");
    return 0;
}
```

```text
descending: 40 30 20 10
```

**SL15.** When the predicate returns `a > b`, it states that `a` comes
before `b`; this is why the array was sorted from largest to smallest.
This operation's kind is also **changed** — the same kind as the previous
`sort` call, because both are the same algorithm called with a different
rule. The predicate itself never read or changed `numbers`; it only
compared two `int` values. This distinction matters: what makes `sort`
mutating is that it writes into the iterator range, while what keeps the
predicate non-mutating is that it is only a value comparison.

## Algorithms Work with an Iterator Pair, Not a Container

None of the standard algorithms take a container type; all of them take a
begin and end iterator. This lets the same algorithm work on all of a
`vector`, a sub-range of a `vector`, or a C array.

```cpp
// iterator-pair.cpp — the same algorithm over different ranges
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> numbers{5, 3, 8, 1, 9, 2};

    std::sort(numbers.begin(), numbers.begin() + 3);

    std::printf("partially sorted array:");
    for (int value : numbers) {
        std::printf(" %d", value);
    }
    std::printf("\n");
    return 0;
}
```

```text
partially sorted array: 3 5 8 1 9 2
```

**SL16.** `std::sort(numbers.begin(), numbers.begin() + 3)` sorted only
the first three elements; the remaining three (`1 9 2`) stayed in their
input order. This shows that the same `std::sort` call produces a
different result with a different range — the algorithm sees not the
whole container but only the iterator pair it was given. This
operation's kind is again **changed**, because part of `numbers` (the
first three elements) changed in ordering; but this time the scope of the
change is limited to the given range, not the whole container. One
consequence of this design is that algorithms never know a container's
own bounds: the iterator `numbers.begin() + 3` given to `std::sort` does
not denote the container's own end, only the bound the caller specified.
The same algorithm works the same way on a raw C array too, called with a
pointer pair — the concept of a container never appears in the
algorithm's interface, only the iterator category (here, random access)
is what the interface requires.

## `std::transform`: An Algorithm That Writes to a New Destination

`std::sort` changed the source range itself. `std::transform` offers a
different pattern: it reads the source, applies a function to each
element, and writes the result to a **separate** destination. As long as
the source is a container separate from the destination, `std::transform`
never touches the source.

```cpp
// transform-separate-destination.cpp — does std::transform change the source or the destination
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> source{1, 2, 3, 4};
    std::vector<int> destination(source.size());

    std::transform(source.begin(), source.end(), destination.begin(),
        [](int value) { return value * value; });

    std::printf("source:");
    for (int value : source) {
        std::printf(" %d", value);
    }
    std::printf("\n");

    std::printf("destination:");
    for (int value : destination) {
        std::printf(" %d", value);
    }
    std::printf("\n");
    return 0;
}
```

```text
source: 1 2 3 4
destination: 1 4 9 16
```

**SL17.** `source` is still `1, 2, 3, 4` at the end of the operation —
`std::transform` only read the source and never wrote to it; the
source's kind is **unchanged**. `destination` was filled with the array
of squares. `std::transform`'s third argument is the destination's begin
iterator; this argument can also be given as the source itself
(`source.begin()`) — in that case the algorithm reads each element and
writes it back to the same position, and the source then falls into the
**changed** kind instead. Which kind applies depends on whether the
destination is the same range as the source; this lesson keeps the two
separate to show `std::transform`'s default behavior, which is to read
the source and write elsewhere. Because `std::transform`'s destination
argument is an iterator, it is the caller's responsibility to have
already allocated enough size at the destination beforehand — the
algorithm does not insert elements into the destination, it only writes
to existing positions; if the destination is not as large as `source`,
the write runs past the bound of allocated memory, and this is undefined
behavior. This lesson never creates this risk, by always sizing
`destination` with `source.size()`.

## `std::stable_sort`: A Sort That Preserves the Order of Equal Elements

`std::sort` does **not guarantee** preserving the relative order between
two elements considered equal — this is a permitted side effect of the
algorithm, not a bug. `std::stable_sort` does the same sorting work but
carries an additional guarantee: elements considered equal by the
comparison predicate keep their relative position from the input order.
This guarantee is not free — `std::sort` runs with average `O(n log n)`
complexity, while `std::stable_sort` can drop to `O(n log^2 n)` if
sufficient extra memory is not available; if extra memory is available,
it still achieves `O(n log n)`.

```cpp
// stable-sort-equality.cpp — how the order of equal elements differs between sort and stable_sort
#include <algorithm>
#include <cstdio>
#include <utility>
#include <vector>

int main() {
    std::vector<std::pair<int, char>> records{
        {2, 'a'}, {1, 'b'}, {2, 'c'}, {1, 'd'}};

    std::stable_sort(records.begin(), records.end(),
        [](const auto& left, const auto& right) { return left.first < right.first; });

    std::printf("sorted records:");
    for (const auto& record : records) {
        std::printf(" (%d,%c)", record.first, record.second);
    }
    std::printf("\n");
    return 0;
}
```

```text
sorted records: (1,b) (1,d) (2,a) (2,c)
```

**SL18.** The pair `{1, 'b'}` and `{1, 'd'}`, considered equal by key,
kept their relative order from the input after the sort — `b` still comes
before `d`. The same holds for `{2, 'a'}` and `{2, 'c'}`. This
operation's kind is also **changed** — the array was reordered from start
to end — but its difference from `std::sort` is the extra guarantee that
the relative order among equal elements was also preserved. `std::sort`
could have left `(1,d)` and `(1,b)` in reverse order on the same input;
this is not a rule `std::sort` violates, it is a promise it never makes.

## Why `std::list` Carries Its Own `sort`

`std::sort` requires a random access iterator — it needs to jump between
elements in constant time in order to achieve its average `O(n log n)`
complexity. This is why `std::sort` **does not compile** with
`std::list`'s bidirectional iterator. The standard library provides a
separate member function for this case: `std::list::sort`.

```cpp
// list-sort-member-function.cpp — why list needs a separate sort
#include <cstdio>
#include <list>

int main() {
    std::list<int> values{40, 10, 30, 20};

    // The line below does not compile, because std::sort requires a random access iterator:
    // std::sort(values.begin(), values.end());

    values.sort();

    std::printf("sorted list:");
    for (int value : values) {
        std::printf(" %d", value);
    }
    std::printf("\n");
    return 0;
}
```

```text
sorted list: 10 20 30 40
```

The reason `std::list::sort` exists as a separate member function is this
constraint: because `list`'s nodes do not sit in contiguous memory, the
generic `std::sort` algorithm cannot operate on them, but `list` can
produce the same result at a different complexity by relinking its own
nodes. This is a concrete example of the rule "not every container works
with every algorithm." The same constraint applies to other algorithms
that require random access: `std::nth_element` and binary-search-based
algorithms such as `std::binary_search` and `std::lower_bound` also
cannot be called directly on `std::list`; the standard library does not
fill this gap with a separate member function for every container, it
only offers a few operations that require node linkage, such as
`list::sort`, `list::merge`, `list::unique` and `list::remove`, as member
functions. The choice of container therefore determines not only the
complexity guarantees but also which standard algorithms can be used
directly.

## The Bounding Measurement

When the same data is given to two different algorithms with a comparison
predicate over the same key, the question of how much of the source can
be reliably read depends on the algorithm's **name**. `std::sort` does
not guarantee preserving the relative order between elements with equal
keys — so printing that order would be presenting a promise the standard
never made. The same data is sorted once more below with `std::stable_sort`,
and the two results are compared:

```cpp title="what-a-name-tells-about-order.cpp"
#include <algorithm>
#include <cstdio>
#include <utility>
#include <vector>

int main() {
    std::vector<std::pair<int, char>> keyed{
        {2, 'a'}, {1, 'b'}, {2, 'c'}, {1, 'd'}};
    std::vector<std::pair<int, char>> stable = keyed;

    std::sort(keyed.begin(), keyed.end(),
        [](const auto& left, const auto& right) { return left.first < right.first; });
    std::stable_sort(stable.begin(), stable.end(),
        [](const auto& left, const auto& right) { return left.first < right.first; });

    std::printf("sort key order:");
    for (const auto& record : keyed) {
        std::printf(" %d", record.first);
    }
    std::printf("\n");

    std::printf("stable_sort full order:");
    for (const auto& record : stable) {
        std::printf(" %d%c", record.first, record.second);
    }
    std::printf("\n");
    return 0;
}
```

```text title="output"
sort key order: 1 1 2 2
stable_sort full order: 1b 1d 2a 2c
```

Over `keyed` we printed only the keys (`1 1 2 2`); we did not print the
letters, because which letter `std::sort` leaves first among equal keys
is a detail the standard does not define — even the same compiler may
apply a different internal ordering at a different input size. Over
`stable`, we could print the full records, because `std::stable_sort`
guarantees preserving the relative input order of equal keys: `1b` always
comes before `1d`, `2a` always comes before `2c`. Both calls move the
same data into the **changed** kind — the source is reordered in place —
but which detail of the source can be safely read and reported is
determined by the algorithm's name: `sort` guarantees only the final key
order, `stable_sort` guarantees the key order together with the relative
position among equals.

## Summary

- `std::sort` changes the order of the elements in the given iterator
  range in place; the kind of this lesson's central measurement is
  **changed**. Giving a custom comparison predicate changes the ordering
  rule, but the predicate itself never reads or changes the source;
  `std::stable_sort` also preserves the relative order of elements
  considered equal, and this extra guarantee comes at a complexity cost
  that can rise to `O(n log^2 n)` when sufficient extra memory is not
  available. Bounding measurement: when the same data is given to
  `std::sort` and `std::stable_sort`, both move the source into the
  **changed** kind, but which detail of the source can be safely reported
  depends on the algorithm's name — `sort` guarantees only the key order,
  `stable_sort` also guarantees the relative order among equals.
- Read-only algorithms such as `std::count`, `std::find_if`,
  `std::accumulate` leave the source **unchanged**.
- This course does not count runs: `rust-soyutlama`'s "how many times did
  it run" axis is not this course's measurement axis; what is measured
  here is which kind the source is left in.
- Algorithms take an iterator pair, not a container type; the same
  algorithm operates over a different scope with a different range.
- `std::transform` leaves the source's kind **unchanged** when it reads
  the source and writes to a separate destination; making the destination
  the source itself turns the kind into **changed**.
- `std::sort` requires a random access iterator and does not compile on
  `std::list`; `list` instead provides its own `sort` member function.

## Next Step

This lesson showed how `std::sort` changes a container in place. The next
lesson takes up the two-step idiom required to **remove** elements from a
container: why does `std::remove` not actually delete elements, only move
them toward the end?