STL Algorithms in C++

<algorithm> and <numeric> provide over 100 generic algorithms that work on any container through iterators. They name what you’re doing — sort, find, partition — so readers don’t have to decode a loop.

Sorting

std::sort sorts in place in O(n log n). std::stable_sort also keeps equal elements in their existing order, which is what makes multi-key sorting work.

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

struct Emp { std::string name, dept; };

int main() {
    std::vector<int> v{5, 2, 8, 1, 9, 3};
    std::sort(v.begin(), v.end());
    for (int x : v) std::cout << x << " ";
    std::sort(v.begin(), v.end(), std::greater<int>{});
    std::cout << "| ";
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";

    std::vector<Emp> staff{{"Raj", "ops"}, {"Ann", "dev"}, {"Zoe", "ops"},
                           {"Bob", "dev"}, {"Kim", "ops"}, {"Eve", "dev"}};
    std::sort(staff.begin(), staff.end(),                        // key 2: name
              [](const Emp& a, const Emp& b) { return a.name < b.name; });
    std::stable_sort(staff.begin(), staff.end(),                 // key 1: dept
              [](const Emp& a, const Emp& b) { return a.dept < b.dept; });
    for (const auto& e : staff) std::cout << e.dept << ":" << e.name << " ";
    std::cout << "\n";

    std::vector<int> top{7, 3, 9, 1, 8, 2, 6};
    std::partial_sort(top.begin(), top.begin() + 3, top.end(), std::greater<int>{});
    std::cout << "top 3: " << top[0] << " " << top[1] << " " << top[2] << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o sorting sorting.cpp
$ ./sorting
1 2 3 5 8 9 | 9 8 5 3 2 1 
dev:Ann dev:Bob dev:Eve ops:Kim ops:Raj ops:Zoe 
top 3: 9 8 7

std::greater<int>{} flips the order. The staff example is the multi-key trick: sort by the secondary key (name) first, then stable_sort by the primary key (dept). Because the stable sort never reorders equal depts, names stay alphabetical within each department. std::sort makes no such promise. partial_sort only orders the first three positions — cheaper than a full sort when you want the top k.

Searching

find scans linearly and works on anything. binary_search, lower_bound and upper_bound are O(log n) but require sorted input.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 3, 5, 7, 7, 7, 9, 11};
    auto it = std::find(v.begin(), v.end(), 7);                   // linear, first match
    std::cout << "find 7 at index " << (it - v.begin()) << "\n";

    auto big = std::find_if(v.begin(), v.end(), [](int x) { return x > 8; });
    std::cout << "first > 8: " << *big << "\n";

    std::cout << std::boolalpha << "binary_search 5: "
              << std::binary_search(v.begin(), v.end(), 5) << "\n";
    auto lb = std::lower_bound(v.begin(), v.end(), 7);             // first >= 7
    auto ub = std::upper_bound(v.begin(), v.end(), 7);             // first > 7
    std::cout << "7s occupy [" << (lb - v.begin()) << ", " << (ub - v.begin())
              << "), count " << (ub - lb) << "\n";
    auto ins = std::lower_bound(v.begin(), v.end(), 6);
    std::cout << "6 would go at index " << (ins - v.begin()) << "\n";

    std::vector<int> unsorted{9, 1, 7, 3, 5};
    std::cout << "binary_search 9 on UNSORTED data: "
              << std::binary_search(unsorted.begin(), unsorted.end(), 9) << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o searching searching.cpp
$ ./searching
find 7 at index 3
first > 8: 9
binary_search 5: true
7s occupy [3, 6), count 3
6 would go at index 3
binary_search 9 on UNSORTED data: false

lower_bound(7) is the first element ≥ 7 and upper_bound(7) the first > 7, so together they bracket all the 7s — three of them — and lower_bound(6) gives the insertion point that keeps the vector sorted. The last line is the precondition biting: on unsorted data binary_search returned false for a 9 that is right there. No error, no warning — just a wrong answer. Sort first, or use find.

Counting and Transforming

count_if, transform and friends each replace a small loop with a name.

#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 2, 4, 2, 5};
    auto twos  = std::count(v.begin(), v.end(), 2);
    auto evens = std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
    std::cout << "twos " << twos << ", evens " << evens << "\n";

    std::vector<int> sq(v.size());
    std::transform(v.begin(), v.end(), sq.begin(), [](int x) { return x * x; });
    for (int x : sq) std::cout << x << " ";
    std::cout << "\n";

    std::vector<int> a{1, 2, 3}, b{10, 20, 30}, c(3);
    std::transform(a.begin(), a.end(), b.begin(), c.begin(), std::plus<>{});
    std::cout << c[0] << " " << c[1] << " " << c[2] << "\n";

    std::string s = "hello, world";
    std::transform(s.begin(), s.end(), s.begin(),                 // in place
                   [](unsigned char ch) { return std::toupper(ch); });
    std::cout << s << "\n";
    std::cout << std::boolalpha << "all positive: "
              << std::all_of(v.begin(), v.end(), [](int x) { return x > 0; }) << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o transform transform.cpp
$ ./transform
twos 3, evens 4
1 4 9 4 16 4 25 
11 22 33
HELLO, WORLD
all positive: true

transform writes into a destination that must already be big enough — sq(v.size()) preallocates it. The binary form walks two ranges in step, here with std::plus<> instead of a lambda. Source and destination can be the same range, as in the in-place uppercase. The unsigned char parameter matters: passing a negative char to std::toupper is undefined behavior.

accumulate and reduce

std::accumulate folds a range into one value, starting from an initial value — and that value’s type is the accumulator’s type.

#include <iostream>
#include <numeric>
#include <string>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5};
    std::cout << "sum " << std::accumulate(v.begin(), v.end(), 0)
              << ", product " << std::accumulate(v.begin(), v.end(), 1,
                     [](int acc, int x) { return acc * x; }) << "\n";

    std::vector<std::string> words{"one", "two", "three"};
    std::string joined = std::accumulate(std::next(words.begin()), words.end(), words[0],
        [](std::string acc, const std::string& w) { return std::move(acc) + ", " + w; });
    std::cout << joined << "\n";

    std::vector<double> prices{0.5, 1.25, 2.75};
    std::cout << "prices with init 0:   " << std::accumulate(prices.begin(), prices.end(), 0)
              << "\n";
    std::cout << "prices with init 0.0: " << std::accumulate(prices.begin(), prices.end(), 0.0)
              << "\n";
    std::cout << "reduce:               " << std::reduce(prices.begin(), prices.end()) << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o accumulate accumulate.cpp
$ ./accumulate
sum 15, product 120
one, two, three
prices with init 0:   3
prices with init 0.0: 4.5
reduce:               4.5

Summing 0.5 + 1.25 + 2.75 with an initial 0 gave 3, not 4.5: the accumulator is an int, so each partial sum was truncated (0, then 1, then 3). No compiler warning. Initialize with 0.0. std::reduce (C++17) takes its default initial value from the element type, which avoids the trap, but it may combine elements in any order, so its operation must be associative and commutative. The string join passes the accumulator by value and moves it to avoid copying the growing string each step.

The Erase-Remove Idiom

Algorithms can’t change a container’s size. std::remove compacts the kept elements to the front and returns the new logical end.

#include <algorithm>
#include <iostream>
#include <vector>

void show(const char* label, const std::vector<int>& v) {
    std::cout << label;
    for (int x : v) std::cout << x << " ";
    std::cout << "(size " << v.size() << ")\n";
}

int main() {
    std::vector<int> v{1, 2, 3, 2, 4, 2, 5};
    auto new_end = std::remove(v.begin(), v.end(), 2);
    show("after remove: ", v);                         // size unchanged!
    std::cout << "logical end at index " << (new_end - v.begin()) << "\n";
    v.erase(new_end, v.end());
    show("after erase:  ", v);

    std::vector<int> w{1, 2, 3, 2, 4, 2, 5};
    auto n = std::erase_if(w, [](int x) { return x % 2 == 0; });   // C++20, one step
    show("erase_if even: ", w);
    std::cout << "removed " << n << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o remove remove.cpp
$ ./remove
after remove: 1 3 4 5 4 2 5 (size 7)
logical end at index 4
after erase:  1 3 4 5 (size 4)
erase_if even: 1 3 5 (size 3)
removed 4

After remove, the size is still 7 and the kept elements 1 3 4 5 sit at the front; the tail (4 2 5 here) is leftover data with unspecified values. Only erase actually shrinks the vector. C++20’s std::erase_if does both steps and returns how many elements it removed.

Partitioning

partition moves elements matching a predicate to the front in O(n), without sorting.

#include <algorithm>
#include <iostream>
#include <vector>

void show(const char* label, const std::vector<int>& v, std::vector<int>::const_iterator mid) {
    std::cout << label;
    for (auto it = v.begin(); it != v.end(); ++it)
        std::cout << (it == mid ? "| " : "") << *it << " ";
    std::cout << "\n";
}

int main() {
    auto even = [](int x) { return x % 2 == 0; };
    std::vector<int> a{5, 1, 8, 2, 9, 3, 7, 4, 6};
    std::vector<int> b = a;
    auto mid_a = std::partition(a.begin(), a.end(), even);
    auto mid_b = std::stable_partition(b.begin(), b.end(), even);
    show("partition:        ", a, mid_a);
    show("stable_partition: ", b, mid_b);

    std::vector<int> c{9, 4, 7, 1, 8, 2, 6};
    std::nth_element(c.begin(), c.begin() + 3, c.end());          // median of 7
    std::cout << "median: " << c[3] << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o partition partition.cpp
$ ./partition
partition:        6 4 8 2 | 9 3 7 1 5 
stable_partition: 8 2 4 6 | 5 1 9 3 7 
median: 6

Both put the evens first (the | marks the returned boundary), but only stable_partition keeps each group’s original order — 8 2 4 6 and 5 1 9 3 7, as they appeared in the input. nth_element is the partition-based way to find a median: it puts the element that would be at index 3 after sorting there, in O(n) on average, without sorting the rest.

C++20 Ranges

Range algorithms take the container directly and accept projections — a member or function applied to each element before comparing.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Book { std::string title; int year; };

int main() {
    std::vector<int> v{5, 2, 8, 1, 9, 3};
    std::ranges::sort(v);                                         // no begin()/end()
    std::cout << "sorted: ";
    for (int x : v) std::cout << x << " ";
    std::cout << "| find 8 -> " << *std::ranges::find(v, 8) << "\n";

    std::vector<Book> books{{"Dune", 1965}, {"Neuromancer", 1984}, {"Foundation", 1951}};
    std::ranges::sort(books, {}, &Book::year);                    // projection: sort by year
    for (const auto& b : books) std::cout << b.year << " " << b.title << "\n";

    auto it = std::ranges::find(books, "Dune", &Book::title);     // search by member
    std::cout << "Dune is at index " << (it - books.begin()) << "\n";
    auto oldest = std::ranges::min(books, {}, &Book::year);
    std::cout << "oldest: " << oldest.title << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o ranges ranges.cpp
$ ./ranges
sorted: 1 2 3 5 8 9 | find 8 -> 8
1951 Foundation
1965 Dune
1984 Neuromancer
Dune is at index 1
oldest: Foundation

std::ranges::sort(books, {}, &Book::year) sorts by year with the default comparator ({}) — no lambda that compares a.year < b.year. The same projection lets find search by title and min pick the oldest book. Before ranges, each of these needed a hand-written comparator.

C++20 Views — Lazy Pipelines

Views transform or filter a range lazily. A logging filter shows exactly when work happens:

#include <iostream>
#include <ranges>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto pipeline = v
        | std::views::filter([](int x) { std::cout << "[test " << x << "] "; return x % 2 == 0; })
        | std::views::transform([](int x) { return x * x; })
        | std::views::take(3);
    std::cout << "pipeline built, nothing tested yet\n";
    for (int n : pipeline) std::cout << "-> " << n << "\n";
    std::cout << "\n";

    auto squares = std::views::iota(1)                        // 1, 2, 3, ... forever
                 | std::views::transform([](int x) { return x * x; })
                 | std::views::take(5);
    for (int s : squares) std::cout << s << " ";
    std::cout << "\n";

    for (int x : v | std::views::reverse | std::views::drop(7)) std::cout << x << " ";
    std::cout << "\n";
}

$ g++ -std=c++20 -Wall -Wextra -o views views.cpp
$ ./views
pipeline built, nothing tested yet
[test 1] [test 2] -> 4
[test 3] [test 4] -> 16
[test 5] [test 6] -> 36
[test 7] [test 8] 
1 4 9 16 25 
3 2 1 

Building pipeline tested nothing. Each loop iteration pulls one value through: the filter tests 1 and 2, transform squares 2, and so on. take(3) stopped after 36 — but notice [test 7] [test 8]: after the third element, the loop still advances the iterator once more before take reports the end, so the filter runs ahead to the next match. Lazy doesn’t mean minimal; don’t put side effects in view predicates. iota(1) is infinite, and take(5) makes it safe. reverse | drop(7) walks 10, 9, 8 … and skips seven.

Parallel Execution Policies (C++17)

Many algorithms take an execution policy as their first argument. With GCC, std::execution::par is implemented on Intel TBB, so the program links with -ltbb (package libtbb-dev on Debian/Ubuntu).

#include <algorithm>
#include <chrono>
#include <execution>
#include <iostream>
#include <random>
#include <vector>

template <typename Policy>
void timed_sort(const char* name, Policy policy, std::vector<int> data) {  // by value: fresh copy
    auto t0 = std::chrono::steady_clock::now();
    std::sort(policy, data.begin(), data.end());
    auto ms = std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t0);
    std::cout << name << ": " << ms.count() << " ms, sorted = "
              << std::boolalpha << std::is_sorted(data.begin(), data.end()) << "\n";
}

int main() {
    std::mt19937 rng(42);
    std::vector<int> data(10'000'000);
    for (int& x : data) x = static_cast<int>(rng());
    timed_sort("seq", std::execution::seq, data);
    timed_sort("par", std::execution::par, data);
}

$ g++ -std=c++20 -Wall -Wextra -O2 -o parallel parallel.cpp -ltbb
$ ./parallel
seq: 886.493 ms, sorted = true
par: 295.017 ms, sorted = true

On this 4-core machine the parallel sort of ten million ints was about three times faster than the sequential one on this run; the exact times vary from run to run, and the speedup depends on core count and data size. Leave off -ltbb and the link fails with undefined references to tbb::detail::.... If the TBB headers aren’t installed at all, libstdc++ compiles the parallel overloads as plain sequential code — no error, just no speedup. Policies are seq, par, par_unseq and unseq; with par, your callables must be safe to run concurrently.

Practice

1. Sort staff in sorting.cpp by dept ascending and name descending using a single std::sort with a lambda.

   Solution

   std::sort(staff.begin(), staff.end(), [](const Emp& a, const Emp& b) {
       if (a.dept != b.dept) return a.dept < b.dept;
       return a.name > b.name;
   });

   Output: dev:Eve dev:Bob dev:Ann ops:Zoe ops:Raj ops:Kim. A compound comparator works with any sort; the stable-sort trick is useful when the keys are applied at different times.

2. Use std::equal_range to count the 7s in searching.cpp in one call.

   Solution

   auto [first, last] = std::equal_range(v.begin(), v.end(), 7);
   std::cout << (last - first) << "\n";   // 3

   equal_range returns the lower_bound/upper_bound pair in one O(log n) call.

3. Compute the average of prices in accumulate.cpp correctly, then show what the 0 initial value would have printed.

   Solution

   double avg = std::accumulate(prices.begin(), prices.end(), 0.0) / prices.size();   // 1.5
   int wrong  = std::accumulate(prices.begin(), prices.end(), 0);                     // 3

   With the 0 version the average would be 3.0 / 3 = 1 instead of 1.5 — the truncation happened inside accumulate, before the division ever saw a double.

4. Build a view pipeline over std::views::iota(1, 50) that keeps multiples of 7, squares them, and prints the first four.

   Solution

   for (int x : std::views::iota(1, 50)
              | std::views::filter([](int n) { return n % 7 == 0; })
              | std::views::transform([](int n) { return n * n; })
              | std::views::take(4))
       std::cout << x << " ";   // 49 196 441 784

5. Replace the seq/par sort in parallel.cpp with a std::reduce of the ten million values under both policies. Why must you sum into long long?

   Solution

   long long total = std::reduce(std::execution::par, data.begin(), data.end(), 0LL);

   The initial value 0LL makes the accumulator 64-bit; with 0, ten million random ints would overflow int, which is undefined behavior. Time both policies the same way as the sort — a sum is memory-bound, so expect a smaller speedup than for sorting.