Library

since C++98

Basic

Transforming and Mutating Algorithms

Deep reference for std::transform, for_each, copy, fill, generate, remove, rotate, and C++20 ranges equivalents with pitfalls and best practices.

Transforming Algorithmssince C++98

Mutating sequence algorithms that apply a function, copy, fill, reorder, or remove elements in-place or into an output range, without changing the container's logical structure beyond the requested transformation.

Overview

The transforming and mutating algorithms in <algorithm> cover everything from pure element-mapping (std::transform) through reordering (std::rotate, std::shuffle) to selective removal (std::remove_if). The critical design distinction: most algorithms do not resize containers — they write into pre-existing ranges or require an insert iterator. Getting this wrong causes silent UB.

std::iota from <numeric> (C++11) fills a range with successive incremented values and belongs alongside std::fill and std::generate in any daily toolkit.

std::transform

std::transform (C++98) applies a callable to each element and writes results into an output range. The output range must have at least last - first elements pre-allocated, or you must use an inserter.

cpp

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

// Unary: square each element
std::vector<int> v{1, 2, 3, 4, 5};
std::vector<int> out(v.size());
std::transform(v.begin(), v.end(), out.begin(),
    [](int x) { return x * x; });
// out: {1, 4, 9, 16, 25}

// Binary overload (C++98): element-wise combine — second range has no end iterator,
// it must contain at least as many elements as the first or the behavior is undefined
std::vector<int> a{1, 2, 3}, b{10, 20, 30}, sum(3);
std::transform(a.begin(), a.end(), b.begin(), sum.begin(),
    std::plus<int>{});
// sum: {11, 22, 33}

// In-place: safe when d_first == first (ranges do not overlap adversely)
std::transform(v.begin(), v.end(), v.begin(),
    [](int x) { return x * 2; });
// v: {2, 4, 6, 8, 10}

// String to uppercase — cast to unsigned char before toupper; passing signed char is UB
std::string s = "hello world";
std::transform(s.begin(), s.end(), s.begin(),
    [](unsigned char c) { return std::toupper(c); });
// s: "HELLO WORLD"

std::for_each

std::for_each (C++98) applies a callable to each element and returns the callable. This matters for stateful functors — the returned object carries accumulated state.

cpp

#include <algorithm>
#include <execution>   // C++17
#include <vector>

std::vector<int> v{1, 2, 3, 4, 5};

// Capture the returned functor to access its accumulated state
struct Accumulator {
    long long sum = 0;
    void operator()(int x) { sum += x; }
};
auto acc = std::for_each(v.begin(), v.end(), Accumulator{});
// acc.sum == 15

// Parallel for_each (C++17): callable must be invocable concurrently without data races
std::for_each(std::execution::par_unseq, v.begin(), v.end(),
    [](int& x) { x *= 2; });   // safe: each element is independent

// for_each_n (C++17): apply to exactly n elements starting at first
std::for_each_n(v.begin(), 3, [](int& x) { x = 0; });
// v[0..2] zeroed, v[3..4] unchanged

Fill, Generate, and Iota

cpp

#include <algorithm>
#include <numeric>    // std::iota — C++11
#include <vector>
#include <random>

std::vector<int> v(5);

std::fill(v.begin(), v.end(), 42);         // {42, 42, 42, 42, 42}
std::fill_n(v.begin(), 3, 0);             // {0, 0, 0, 42, 42}

// generate: callable provides successive values; may carry state
int n = 0;
std::generate(v.begin(), v.end(), [&n] { return n++; });
// v: {0, 1, 2, 3, 4}

// generate_n with back_inserter appends to the container
std::vector<int> r;
std::mt19937 rng{42};
std::generate_n(std::back_inserter(r), 5,
    [&rng] { return static_cast<int>(rng() % 100); });

// iota (C++11): fills with value, value+1, value+2, ... — cleaner than generate + counter
std::iota(v.begin(), v.end(), 1);          // {1, 2, 3, 4, 5}

Copy Algorithms

cpp

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

std::vector<int> src{1, 2, 3, 4, 5};
std::vector<int> dst(5);

std::copy(src.begin(), src.end(), dst.begin());

// copy_if: filter into output — output must be pre-sized or use back_inserter
std::vector<int> evens;
std::copy_if(src.begin(), src.end(), std::back_inserter(evens),
    [](int x) { return x % 2 == 0; });    // {2, 4}

// copy_n: exactly n elements
std::copy_n(src.begin(), 3, dst.begin()); // dst[0..2] = {1, 2, 3}

// Overlapping ranges: use copy_backward when dst overlaps src and dst > src
// (shifting elements right within the same container)
std::copy_backward(src.begin(), src.end(), dst.end());

// reverse_copy: writes src reversed into dst, src is unmodified
std::vector<int> rev(src.size());
std::reverse_copy(src.begin(), src.end(), rev.begin());   // {5, 4, 3, 2, 1}

// move (C++11): like copy but leaves source in valid-but-unspecified state
std::vector<std::string> strs{"a", "b", "c"};
std::vector<std::string> moved(3);
std::move(strs.begin(), strs.end(), moved.begin());

Replace

cpp

std::vector<int> v{1, 2, 3, 2, 1};

std::replace(v.begin(), v.end(), 2, 99);
// v: {1, 99, 3, 99, 1}

std::replace_if(v.begin(), v.end(),
    [](int x) { return x > 5; }, 0);

// replace_copy: non-destructive — writes replaced result into separate output
std::vector<int> out(v.size());
std::replace_copy(v.begin(), v.end(), out.begin(), 1, 100);

Remove and the Erase-Remove Idiom

std::remove and std::remove_if shift surviving elements toward the front and return an iterator to the new logical end. The container is not resized. Elements past the returned iterator are valid but unspecified — failing to erase them is a common bug.

cpp

std::vector<int> v{1, 2, 3, 2, 4, 2, 5};

// Pre-C++20 erase-remove idiom
auto new_end = std::remove(v.begin(), v.end(), 2);
v.erase(new_end, v.end());
// v: {1, 3, 4, 5}

// C++20: std::erase / std::erase_if collapse the idiom into one call
// Available for all standard sequence and associative containers
std::erase(v, 3);
std::erase_if(v, [](int x) { return x % 2 == 0; });

Reordering: Reverse, Rotate, Shuffle

cpp

#include <algorithm>
#include <random>
#include <vector>

std::vector<int> v{1, 2, 3, 4, 5};

std::reverse(v.begin(), v.end());          // {5, 4, 3, 2, 1}

// rotate: [middle, end) becomes the new front
// Returns iterator to the element that was originally at v.begin() (C++11)
auto it = std::rotate(v.begin(), v.begin() + 2, v.end());
// v: {3, 2, 1, 5, 4};  *it == 5 (was v[0])

// shuffle (C++11): std::random_shuffle removed in C++17
std::mt19937 rng{std::random_device{}()};
std::shuffle(v.begin(), v.end(), rng);

// Permutations: visit all n! orderings in lexicographic order
std::vector<int> p{1, 2, 3};
do {
    // process each permutation
} while (std::next_permutation(p.begin(), p.end()));

Unique

std::unique removes consecutive duplicates only. Sort first for global deduplication.

cpp

std::vector<int> v{3, 1, 1, 2, 3, 3, 4, 1};

std::sort(v.begin(), v.end());
auto new_end = std::unique(v.begin(), v.end());
v.erase(new_end, v.end());
// v: {1, 2, 3, 4}

// C++20: ranges::unique returns a subrange [new_end, old_end)
#include <ranges>
std::ranges::sort(v);
auto [rm, end] = std::ranges::unique(v);
v.erase(rm, end);

C++20 Ranges

Ranges versions accept range arguments directly, support projections, and compose with lazy views. They live in std::ranges:: and return rich result types instead of bare iterators.

cpp

#include <algorithm>
#include <ranges>
#include <vector>
#include <string>

struct Employee { std::string name; int salary; };
std::vector<Employee> staff{{"Alice", 90000}, {"Bob", 75000}, {"Carol", 95000}};

// transform with projection: extract salary into separate vector
std::vector<int> salaries;
std::ranges::transform(staff, std::back_inserter(salaries),
    &Employee::salary);

// copy_if with projection: predicate receives the projected value
std::vector<Employee> senior;
std::ranges::copy_if(staff, std::back_inserter(senior),
    [](int s) { return s >= 90000; },
    &Employee::salary);

// Lazy pipeline: no intermediate containers allocated
auto top_names = staff
    | std::views::filter([](const Employee& e) { return e.salary > 80000; })
    | std::views::transform(&Employee::name);

for (const auto& name : top_names)
    std::println("{}", name);   // std::println: C++23

Best Practices

Prefer std::iota over std::generate with an external counter — intent is explicit and the implementation is typically optimized.
Pre-allocate output with resize when size is known; use std::back_inserter when it isn't. Never write into an empty-default-constructed container.
Capture the return value of std::for_each when using stateful functors — the standard guarantees the returned object reflects all applications.
Prefer std::erase/std::erase_if (C++20) over the erase-remove idiom. They're single-call, container-aware, and eliminate the erroneous-truncation footgun.
Restrict std::execution::par_unseq to callable objects that are genuinely thread-safe and operate on disjoint data. Shared mutable state without synchronization is UB.

Common Pitfalls

Unsized output range. std::transform, std::copy, and related algorithms write into an existing range — they never grow it. Writing past the end is UB.

cpp

std::vector<int> src{1, 2, 3};
std::vector<int> dst;                                        // empty!
// UB: std::copy(src.begin(), src.end(), dst.begin());
std::copy(src.begin(), src.end(), std::back_inserter(dst)); // correct

Forgetting to erase after std::remove. std::remove reorganizes elements but leaves the container at its original size with unspecified values past the logical end. Always pair with erase, or use std::erase (C++20).

std::toupper on signed char. Passing a char with a negative value to std::toupper is undefined behavior. Cast to unsigned char before the call.

Binary std::transform overrun. The second input range has no end iterator. If it's shorter than the first range, the algorithm reads past its end — UB with no compile-time diagnostic.

Overlapping copies shifted right. std::copy requires d_first to not lie in (first, last). When shifting elements right within the same container (e.g., making room at the front), use std::copy_backward instead.

std::random_shuffle was removed in C++17. Code using it will not compile in C++17 or later. Replace with std::shuffle and an explicit std::mt19937.

std::transform with Binary Operation (Two Input Ranges)

The binary overload of std::transform merges two ranges element-wise using a callable. The second range begins at first2 and has no explicit end iterator — the algorithm advances it in lockstep with the first range, reading exactly last1 - first1 elements. If the second range is shorter, you get undefined behavior with no compile-time warning.

Use the binary overload any time you need to zip two same-length sequences: vector arithmetic, pairwise string comparison, combining parallel data columns, or computing residuals between two arrays.

cpp

// C++11
#include <algorithm>
#include <vector>
#include <functional>
#include <cmath>

std::vector<double> predicted{1.0, 2.0, 3.0, 4.0};
std::vector<double> actual   {1.1, 1.9, 3.2, 3.8};
std::vector<double> residuals(predicted.size());

// Element-wise subtraction into residuals
std::transform(predicted.begin(), predicted.end(),
               actual.begin(),
               residuals.begin(),
               [](double p, double a) { return a - p; });
// residuals: {0.1, -0.1, 0.2, -0.2}

// In-place: overwrite one of the input ranges
std::vector<int> weights{2, 3, 1, 4};
std::vector<int> values {5, 6, 7, 8};
// multiply each value by its weight, store back into values
std::transform(values.begin(), values.end(),
               weights.begin(),
               values.begin(),            // d_first == first1: safe
               std::multiplies<int>{});
// values: {10, 18, 7, 32}

The unary and binary overloads are entirely distinct — the binary overload is selected when four iterators (plus a callable) are passed. There is no three-iterator-range overload in the standard; the second range always needs only a begin iterator.

cpp

// C++17
#include <algorithm>
#include <execution>
#include <vector>

// Parallel binary transform: independent element pairs make this safe for par
std::vector<float> xs(1'000'000, 1.5f);
std::vector<float> ys(1'000'000, 2.5f);
std::vector<float> zs(1'000'000);

std::transform(std::execution::par_unseq,
               xs.begin(), xs.end(),
               ys.begin(),
               zs.begin(),
               [](float x, float y) { return x * x + y * y; });

std::ranges::transform with Projections (C++20)

Projections let you describe what to map before how to combine, separating element access from the transformation logic. Both the unary and binary std::ranges::transform overloads accept projection callables applied to each element before the main transform callable receives them. This eliminates boilerplate lambdas that exist only to reach a member field.

cpp

// C++20
#include <algorithm>
#include <ranges>
#include <vector>
#include <string>
#include <cmath>

struct Vec2 { double x, y; };

std::vector<Vec2> points{{3.0, 4.0}, {5.0, 12.0}, {8.0, 6.0}};
std::vector<double> lengths(points.size());

// Unary transform with projection: callable receives the projected value
std::ranges::transform(points, lengths.begin(),
    [](double h) { return h; },        // identity on the projected value
    [](const Vec2& v) { return std::hypot(v.x, v.y); });
// lengths: {5.0, 13.0, 10.0}

// More typical: projection isolates a member, transform does the math
struct Record { std::string id; int raw_score; };
std::vector<Record> records{{"A", 85}, {"B", 92}, {"C", 78}};
std::vector<double> scaled(records.size());

std::ranges::transform(records, scaled.begin(),
    [](int s) { return s / 100.0; },
    &Record::raw_score);               // projection: extract raw_score first
// scaled: {0.85, 0.92, 0.78}

The binary ranges overload takes two input ranges and two projections — one per range — before the combining callable.

cpp

// C++20
#include <algorithm>
#include <ranges>
#include <vector>
#include <string>

struct Student { std::string name; int score; };
struct Baseline { std::string name; int expected; };

std::vector<Student>  students {{"Alice", 91}, {"Bob", 74}, {"Carol", 88}};
std::vector<Baseline> baselines{{"Alice", 85}, {"Bob", 80}, {"Carol", 90}};
std::vector<int> deltas(students.size());

// Binary transform with per-range projections
std::ranges::transform(students, baselines, deltas.begin(),
    [](int actual, int expected) { return actual - expected; },
    &Student::score,      // project first range
    &Baseline::expected); // project second range
// deltas: {6, -6, -2}

Projections compose naturally with std::views pipelines: apply a projection in a views::transform stage and feed the result into a further ranges::transform call, keeping each step focused on a single concern.

In-Place Transforms vs Output-to-Separate-Range Patterns

Choosing between in-place and out-of-place transform is a correctness and performance trade-off, not just a style preference. In-place transforms overwrite the source, which eliminates the extra allocation and can improve cache utilization for large contiguous arrays. Out-of-place transforms preserve the original, permit the output type to differ from the input type, and enable the original data to remain visible for diagnostics or rollback.

The standard permits d_first == first for unary std::transform — the output iterator can alias the input iterator when writing back into the same range. The binary overload additionally allows d_first == first1. What is never allowed is a partially-overlapping range that would cause d_first to be read before it is written.

cpp

// C++11
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

// In-place: normalize a vector of floats in-place
std::vector<float> signal{0.5f, 1.0f, 0.25f, 0.75f};
float peak = *std::max_element(signal.begin(), signal.end());
std::transform(signal.begin(), signal.end(), signal.begin(),
    [peak](float v) { return v / peak; });
// signal: {0.5, 1.0, 0.25, 0.75} → {0.5, 1.0, 0.25, 0.75} (already normalized)

// Out-of-place: int → double requires a different output container type
std::vector<int> counts{1, 4, 9, 16, 25};
std::vector<double> roots(counts.size());
std::transform(counts.begin(), counts.end(), roots.begin(),
    [](int n) { return std::sqrt(static_cast<double>(n)); });
// roots: {1.0, 2.0, 3.0, 4.0, 5.0}
// counts is still intact

// Out-of-place with back_inserter: output container grows as needed
std::vector<std::string> words{"hello", "world", "cpp"};
std::vector<int> lengths;
std::transform(words.begin(), words.end(), std::back_inserter(lengths),
    [](const std::string& s) { return static_cast<int>(s.size()); });
// lengths: {5, 5, 3}

When the output type is the same as the input and you only need to mutate (not produce a value), std::for_each is a cleaner fit than in-place std::transform — it avoids the dummy d_first argument and signals intent more clearly.

std::shift_left and std::shift_right (C++20)

std::shift_left and std::shift_right efficiently slide the contents of a range toward either end without allocating any extra storage. Both were added in C++20 alongside the parallel algorithm expansion. They return an iterator to the new logical end (for shift_left) or the new logical beginning (for shift_right), analogous to the iterator returned by std::remove.

cpp

// C++20
#include <algorithm>
#include <vector>
#include <iostream>

std::vector<int> v{1, 2, 3, 4, 5, 6, 7};

// shift_left by 2: surviving elements are [3,4,5,6,7] at positions [0..4]
// Returns iterator to the new end (v.begin() + 5 here)
auto new_end = std::shift_left(v.begin(), v.end(), 2);
v.erase(new_end, v.end());
// v: {3, 4, 5, 6, 7}

// Reset
v = {1, 2, 3, 4, 5, 6, 7};

// shift_right by 2: surviving elements are [1,2,3,4,5] at positions [2..6]
// Returns iterator to the new beginning (v.begin() + 2 here)
auto new_begin = std::shift_right(v.begin(), v.end(), 2);
// Elements before new_begin are valid-but-unspecified
// v: [?, ?, 1, 2, 3, 4, 5]  (first 2 elements unspecified)

A shift amount of zero or greater than or equal to the range length leaves the range unchanged and returns first (for shift_left) or last (for shift_right). Unlike std::rotate, shifts do not wrap — elements that fall off the edge are simply discarded.

cpp

// C++20
#include <algorithm>
#include <deque>

// shift_left works with any bidirectional or forward iterator
// (shift_right requires bidirectional or random-access for efficiency)
std::deque<int> dq{10, 20, 30, 40, 50};
auto end2 = std::shift_left(dq.begin(), dq.end(), 1);
dq.erase(end2, dq.end());
// dq: {20, 30, 40, 50}

// Parallel shift (C++20): execution policy overloads exist
#include <execution>
std::vector<double> big(1'000'000);
std::iota(big.begin(), big.end(), 0.0);
auto pe = std::shift_left(std::execution::par, big.begin(), big.end(), 100);
big.erase(pe, big.end());

std::shift_left is essentially the operation that std::rotate performs when you rotate to first + n, but shift_left is explicit about discarding elements rather than wrapping them, and compilers can generate tighter code for it as a result.

Performance: transform vs Manual Loop, SIMD Vectorization

std::transform is not slower than a hand-written loop — on any modern optimizing compiler with -O2 or higher, they emit identical machine code for trivially-typed elements. The real performance question is whether the compiler can auto-vectorize the loop body. Lambdas that operate element-wise on contiguous ranges of arithmetic types are prime SIMD candidates.

The following patterns consistently enable auto-vectorization in GCC, Clang, and MSVC:

Output range does not alias input (or the compiler can prove it doesn't).
No early-exit, exception throws, or function calls the compiler cannot inline.
Element type is a scalar arithmetic type (int, float, double) or a trivially-laid-out struct.
Loop body fits in a single SIMD instruction or a short sequence of them.

cpp

// C++17
#include <algorithm>
#include <vector>
#include <cmath>

// Vectorizable: simple arithmetic on contiguous float data
std::vector<float> input(1'024'000, 1.5f);
std::vector<float> output(input.size());

// Compiler emits AVX2/AVX-512 on x86 with -O2 -march=native
std::transform(input.begin(), input.end(), output.begin(),
    [](float x) { return x * x - 1.0f; });

// Non-vectorizable: std::sin calls the libm function, which the compiler
// typically cannot vectorize unless you enable -ffast-math or use
// a SIMD math library (e.g., Intel SVML, Sleef)
std::transform(input.begin(), input.end(), output.begin(),
    [](float x) { return std::sin(x); });

When you need guaranteed SIMD throughput (e.g., DSP, image processing), three approaches work well with std::transform style code:

cpp

// C++17  — parallel execution policy offloads scheduling to the STL backend
// (Intel TBB, Microsoft PPL, or libstdc++ OpenMP), which may use SIMD internally
#include <execution>
#include <algorithm>
#include <vector>

std::vector<float> v(4'000'000, 2.0f);
std::vector<float> out(v.size());

// par_unseq: the standard's hint for both thread-parallelism AND SIMD
std::transform(std::execution::par_unseq,
               v.begin(), v.end(), out.begin(),
               [](float x) { return x * 0.5f + 1.0f; });

In microbenchmarks, std::transform with a trivial lambda is within 1–2% of a hand-written for loop on the same data — the difference vanishes in any real workload dominated by memory bandwidth. The practical performance hierarchy is: memory layout (sequential vs strided) > SIMD width > scalar vs std::transform vs loop.

cpp

// C++11
// Anti-pattern: strided access defeats SIMD — structure of arrays beats array of structures
// for transform-heavy workloads
struct Particle { float x, y, z, w; };  // AoS: accesses to x are strided by 16 bytes

// Prefer SoA for batch transforms:
struct ParticlesSoA {
    std::vector<float> x, y, z, w;
};
// std::transform on ParticlesSoA.x is contiguous; SIMD width fully utilized

See Also

Sorting Algorithms — pair with std::unique for deduplication, or std::partial_sort before slicing
Searching Algorithms — locate elements before transforming them
Ranges and Views — lazy composition with std::views::transform and std::views::filter
<numeric> Algorithms — std::iota, std::accumulate, std::transform_reduce (C++17)
Execution Policies — parallel and vectorized variants (C++17)