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

See Also