Algorithms

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

// 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;
}

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.

// 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;
}

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.

// 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;
}

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.

// 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;
}

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.

// 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;
}

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

// 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;
}

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.

// 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;
}

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:

#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;
}

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?