C++
Library
Basic

Modifying Sequence Algorithms

STL algorithms from <algorithm> that mutate a target range by copying, filling, generating, transforming, replacing, or rearranging elements.

Modifying Sequence Algorithmssince C++98

Algorithms from <algorithm> that write to or rearrange a target range, in contrast to non-modifying algorithms that only inspect elements without changing them.

Overview

Modifying sequence algorithms operate on iterator-defined ranges and fall into logical groups:

  • Copy / Move — transfer elements to a separate destination
  • Fill / Generate — overwrite a range with a constant or computed value
  • Transform — apply a function element-by-element to produce a new range
  • Replace — overwrite elements that match a value or predicate
  • Remove — compact a range by logically deleting matched elements
  • Reverse / Rotate — rearrange elements in place
  • Shuffle — randomize order using an explicit URNG

Most algorithms come in _if, _copy, and _copy_if variants. The _if suffix substitutes a unary predicate for a value comparison; _copy writes to a separate destination, leaving the source intact.

Since C++17, most of these accept an execution policy as their first argument (std::execution::par, std::execution::par_unseq) to opt into parallelism. Since C++20, std::ranges:: overloads accept range objects or sentinel pairs and add projection support, eliminating boilerplate begin/end calls.

Copy and Move

cpp
#include <algorithm>
#include <vector>
#include <iterator>

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

// Forward copy: writes [first, last) to d_first, returns iterator past last written
std::copy(src.begin(), src.end(), dst.begin());

// Conditional copy — back_inserter avoids pre-sizing when output size is unknown
std::vector<int> evens;
evens.reserve(src.size());
std::copy_if(src.begin(), src.end(), std::back_inserter(evens),
             [](int x) { return x % 2 == 0; });
// evens == {2, 4}

// Copy exactly n elements
std::copy_n(src.begin(), 3, dst.begin());

// Safe for right-overlapping ranges (dst overlaps src with dst > src)
std::copy_backward(src.begin(), src.end(), dst.end());

// Move each element using move semantics — source elements are valid but unspecified
std::vector<std::string> words{"alpha", "beta", "gamma"};
std::vector<std::string> moved(words.size());
std::move(words.begin(), words.end(), moved.begin());    // C++11
// std::move_backward for right-overlapping variant

std::copy requires that [first, last) and the destination range do not overlap such that the destination falls within the source range ahead of the read position. When source and destination overlap and dst > src, std::copy_backward is correct; std::copy would silently corrupt data.

std::move (the algorithm) is distinct from std::move (the cast to rvalue reference). Both live in namespace std — keep the distinction explicit in code review.

Fill and Generate

std::fill assigns a single constant to every element. std::generate calls a generator for each position, enabling stateful or computed sequences without a manual loop.

cpp
#include <algorithm>
#include <numeric>

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

std::fill(v.begin(), v.end(), 0);
// v == {0, 0, 0, 0, 0, 0, 0, 0}

// fill_n returns an iterator one past the last element written
auto it = std::fill_n(v.begin(), 4, 42);
// v == {42, 42, 42, 42, 0, 0, 0, 0}

// generate with stateful lambda
int counter = 0;
std::generate(v.begin(), v.end(), [&counter] { return counter++ * 2; });
// v == {0, 2, 4, 6, 8, 10, 12, 14}

// generate_n with back_inserter — appends to container rather than overwriting
std::vector<int> out;
out.reserve(5);
std::generate_n(std::back_inserter(out), 5, [n = 1]() mutable { return n++; });
// out == {1, 2, 3, 4, 5}

// std::iota (<numeric>, C++11): consecutive values starting from an initial
std::iota(v.begin(), v.end(), 1);
// v == {1, 2, 3, 4, 5, 6, 7, 8}

std::fill_n with a back_inserter appends rather than overwrites — a meaningful distinction when the container is empty. Output iterators are write-only; do not read back through a back_insert_iterator.

Transform

std::transform applies a unary or binary callable to each element and writes the result to a destination. Source and destination may be the same range (in-place).

cpp
#include <algorithm>
#include <cctype>
#include <functional>

std::string s{"Hello, World!"};

// In-place lowercase — pass same iterator as source and destination
std::transform(s.begin(), s.end(), s.begin(),
               [](unsigned char c) { return std::tolower(c); });

// Binary form: zips two ranges, element-wise
std::vector<int> a{1, 2, 3};
std::vector<int> b{10, 20, 30};
std::vector<int> result(a.size());
std::transform(a.begin(), a.end(), b.begin(), result.begin(),
               std::plus<int>{});
// result == {11, 22, 33}

// C++20 ranges overload with projection — avoids explicit begin/end
// std::ranges::transform(a, result.begin(), [](int x) { return x * x; });

Replace

The replace family overwrites matching elements without changing container size or invalidating iterators.

cpp
#include <algorithm>

std::vector<int> data{1, 5, 3, 5, 7, 5};

std::replace(data.begin(), data.end(), 5, 0);
// data == {1, 0, 3, 0, 7, 0}

std::replace_if(data.begin(), data.end(),
                [](int x) { return x > 4; }, -1);

// _copy variants leave the source untouched
std::vector<int> src{1, 5, 3, 5};
std::vector<int> dst(src.size());
std::replace_copy(src.begin(), src.end(), dst.begin(), 5, 99);
// dst == {1, 99, 3, 99},  src unchanged

std::replace_copy_if(src.begin(), src.end(), dst.begin(),
                     [](int x) { return x > 3; }, 0);

Remove

std::remove and std::remove_if do not erase elements from the container. They compact the retained elements to the front and return a "new end" iterator; elements in [new_end, old_end) are left in a valid but unspecified state. Container erasure is a separate step.

cpp
#include <algorithm>
#include <vector>

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

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

// Since C++20: std::erase and std::erase_if are non-member functions
// defined per container — cleaner and avoids the two-step:
// std::erase(v, 2);
// std::erase_if(v, [](int x) { return x % 2 == 0; });

Failing to call erase after remove is one of the most common defects in STL-using code. The container's size() is unchanged by std::remove alone.

Reverse and Rotate

cpp
#include <algorithm>

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

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

// rotate: new_first becomes the element at position 0 after rotation
// returns an iterator pointing to the element that was at first before rotation
std::vector<int> r{1, 2, 3, 4, 5};
auto ret = std::rotate(r.begin(), r.begin() + 2, r.end());
// r == {3, 4, 5, 1, 2},  *ret == 1

// Left-rotate by one:
std::rotate(r.begin(), r.begin() + 1, r.end());

// _copy variants write to destination, preserve source
std::vector<int> out(v.size());
std::reverse_copy(v.begin(), v.end(), out.begin());
std::rotate_copy(r.begin(), r.begin() + 2, r.end(), out.begin());

std::rotate is more general than it looks: the returned iterator pins the original first element in its new location, enabling multi-step permutations without extra allocation.

Shuffle

std::random_shuffle was deprecated in C++14 and removed in C++17. Its replacement, std::shuffle, mandates an explicit Uniform Random Bit Generator, which avoids the rand()-based portability problems of its predecessor.

cpp
#include <algorithm>
#include <random>

std::vector<int> deck(52);
std::iota(deck.begin(), deck.end(), 1);          // C++11

std::mt19937 rng{std::random_device{}()};         // C++11
std::shuffle(deck.begin(), deck.end(), rng);      // C++11

Always seed from std::random_device in production. A fixed seed produces a reproducible shuffle — acceptable in testing, a vulnerability in any security or fairness context.

Best Practices

  • Reserve the destination container to src.size() before using back_inserter to avoid repeated reallocations during copy_if or transform.
  • Use std::copy_backward (not std::copy) whenever source and destination overlap and the write target is to the right of the read source.
  • Prefer std::erase/std::erase_if (C++20) over the two-step erase-remove idiom when targeting C++20 or later.
  • Benchmark before applying std::execution::par_unseq — parallel dispatch overhead dominates on ranges shorter than a few thousand elements.
  • For std::transform in-place, the single-range overload writing back to begin is well-defined; iterators do not need to differ.

Common Pitfalls

Overlapping copy direction: std::copy assumes no right-overlap; undefined behaviour results if dst falls within src ahead of the read position. Use std::copy_backward for that case.

Treating std::remove as deletion: Elements beyond the returned iterator are neither erased nor destroyed. Containers still report the original size(). Always pair with .erase().

std::move (algorithm) vs std::move (cast): They share a name. std::move(it1, it2, dst) is the range algorithm; std::move(x) casts x to an rvalue reference. The overload resolution differs by argument count but confusion in code review is common.

Leaking through remove on owning raw pointers: std::remove rearranges; it does not call destructors. Raw pointer elements in the tail [new_end, old_end) become unreachable, leaking their objects. Use std::unique_ptr or delete explicitly before erasing.

Fixed-seed shuffle in randomization-sensitive code: std::shuffle with a constant seed is deterministic. Seed from std::random_device unless reproducibility is explicitly required.

std::transform with Two Input Ranges

Claim. The binary overload of std::transform zips two input ranges element-by-element, making explicit loops for vector arithmetic unnecessary. The source and destination may overlap, enabling in-place updates.

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

std::vector<int> a{1, 2, 3, 4};
std::vector<int> b{10, 20, 30, 40};
std::vector<int> out(a.size());

// Element-wise addition: out[i] = a[i] + b[i]
std::transform(a.begin(), a.end(), b.begin(), out.begin(),
               std::plus<int>{});
// out == {11, 22, 33, 44}

// In-place transformation: square every element of a
std::transform(a.begin(), a.end(), a.begin(),
               [](int x) { return x * x; });
// a == {1, 4, 9, 16}

The C++20 ranges overload accepts range objects directly and adds optional projections, removing the paired begin/end calls. Unlike the iterator overload, std::ranges::transform with two input ranges returns a struct holding all three output iterators.

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

std::vector<int> x{1, 2, 3};
std::vector<int> y{4, 5, 6};
std::vector<int> result(x.size());

// Ranges overload: takes two range arguments
std::ranges::transform(x, y, result.begin(), std::plus<int>{});
// result == {5, 7, 9}

std::replace and std::replace_if

Claim. The replace family overwrites elements in-place based on value equality or a predicate, making data normalization passes concise and branch-free. No iterators are invalidated and container size is unchanged.

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

std::vector<double> data{1.0, std::numeric_limits<double>::quiet_NaN(),
                          3.0, std::numeric_limits<double>::quiet_NaN()};

// Replace every NaN with 0.0 — use replace_if because NaN != NaN
std::replace_if(data.begin(), data.end(),
                [](double x) { return std::isnan(x); }, 0.0);
// data == {1.0, 0.0, 3.0, 0.0}

std::vector<int> ids{0, 5, 3, 0, 7};

// Replace by value — equality comparison, no predicate needed
std::replace(ids.begin(), ids.end(), 0, -1);
// ids == {-1, 5, 3, -1, 7}

// _copy variants: write to a new range, leaving the source intact
std::vector<int> src{1, 5, 3, 5};
std::vector<int> dst(src.size());

std::replace_copy(src.begin(), src.end(), dst.begin(), 5, 99);
// dst == {1, 99, 3, 99},  src unchanged

std::replace_copy_if(src.begin(), src.end(), dst.begin(),
                     [](int x) { return x > 3; }, 0);
// dst == {1, 0, 3, 0},  src unchanged

Use std::replace_copy when the original data must be preserved for audit or rollback, and std::replace when an in-place rewrite is acceptable. Sanitizing string or numeric input before storage is a typical production use case.

std::rotate and std::rotate_copy

Claim. std::rotate performs a left rotation so that the element pointed to by new_first becomes index zero, returning an iterator to the element that was originally at first. It is O(n) and makes exactly n move-assignments.

cpp
// C++11
#include <algorithm>
#include <vector>

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

// Rotate left by 2: element at index 2 becomes the new front
auto it = std::rotate(v.begin(), v.begin() + 2, v.end());
// v == {3, 4, 5, 1, 2}
// *it == 1  (original first element relocated to index 3)

// Left-rotate by one — efficient circular-buffer drain step
std::rotate(v.begin(), v.begin() + 1, v.end());
// v == {4, 5, 1, 2, 3}

// _copy variant: writes rotated sequence to a destination, source unchanged
std::vector<int> src{10, 20, 30, 40, 50};
std::vector<int> dst(src.size());
std::rotate_copy(src.begin(), src.begin() + 3, src.end(), dst.begin());
// dst == {40, 50, 10, 20, 30},  src unchanged

The returned iterator from std::rotate is useful for chaining rotations: it marks where the old [first, new_first) block was placed, enabling a sliding-window algorithm to track the logical start without an extra offset variable.

std::unique and the Erase-Remove Idiom

Claim. std::unique compacts consecutive duplicate elements to the front of a range and returns a "new end" iterator; elements in the tail are valid but unspecified, so the erase step is always required to shrink the container.

cpp
// C++11
#include <algorithm>
#include <vector>

std::vector<int> v{1, 1, 2, 3, 3, 3, 4};
// Input must be sorted for globally unique results (duplicates must be adjacent)

// Classic erase-unique idiom
v.erase(std::unique(v.begin(), v.end()), v.end());
// v == {1, 2, 3, 4}

// With a custom equivalence predicate
std::vector<std::string> words{"foo", "FOO", "bar", "BAR", "bar"};
std::sort(words.begin(), words.end());
auto new_end = std::unique(words.begin(), words.end(),
    [](const std::string& a, const std::string& b) {
        return a == b; // case-sensitive here; adapt as needed
    });
words.erase(new_end, words.end());

C++20 provides two improvements: std::ranges::unique returns a subrange (not a bare iterator), making the erased range explicit; and the free-function std::erase collapses the two-step idiom into one call for equality-based removal.

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

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

// ranges::unique returns a subrange denoting the tail to erase
auto [new_end, old_end] = std::ranges::unique(v);
v.erase(new_end, old_end);
// v == {1, 2, 3, 4}

std::generate and std::generate_n

Claim. std::generate decouples the production of values from their storage: any zero-argument callable — a lambda capturing mutable state, a distribution object, or a hardware source — can serve as the generator. std::iota is the special-case shorthand for arithmetic sequences.

cpp
// C++11
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>

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

// Arithmetic sequence: 1, 2, 3, ..., 8
std::iota(v.begin(), v.end(), 1);

// Fibonacci sequence via stateful lambda
int a = 0, b = 1;
std::generate(v.begin(), v.end(), [&a, &b]() mutable {
    int val = a;
    std::tie(a, b) = std::make_pair(b, a + b);
    return val;
});
// v == {0, 1, 1, 2, 3, 5, 8, 13}

// generate_n with back_inserter — appends n elements to an empty container
std::vector<int> out;
out.reserve(5);
std::generate_n(std::back_inserter(out), 5,
                [n = 0]() mutable { return n++ * n; });
// out == {0, 1, 4, 9, 16}

// Fill from a random source — useful for test data generation
std::mt19937 rng{42};
std::uniform_int_distribution<int> dist(1, 100);
std::generate(v.begin(), v.end(), [&] { return dist(rng); });

Prefer std::generate over std::fill whenever the values are not constant — even for a trivial counter, a generator communicates intent and avoids a separate mutable variable in the surrounding scope.

Parallel Modifying Algorithms (C++17)

Claim. Passing an execution policy as the first argument opts a modifying algorithm into parallel or vectorised execution; the only constraint is that the callable must be thread-safe and must not depend on the processing order of elements.

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

std::vector<float> pixels(1920 * 1080);

// Parallel element-wise transform — each pixel scaled independently
std::transform(std::execution::par_unseq,
               pixels.begin(), pixels.end(), pixels.begin(),
               [](float v) { return std::clamp(v * 1.2f, 0.0f, 1.0f); });

// Parallel conditional replace — zero out negative sensor readings
std::replace_if(std::execution::par,
                pixels.begin(), pixels.end(),
                [](float v) { return v < 0.0f; },
                0.0f);

// Parallel copy_if — extract hot pixels to a pre-sized output buffer
std::vector<float> hot(pixels.size());
auto new_end = std::copy_if(std::execution::par_unseq,
                            pixels.begin(), pixels.end(),
                            hot.begin(),
                            [](float v) { return v > 0.9f; });
hot.erase(new_end, hot.end());

std::execution::par_unseq permits both inter-thread parallelism and SIMD vectorisation; any callable used with it must not acquire locks, call non-reentrant functions, or access shared mutable state without synchronisation. Benchmarking is essential — parallel dispatch overhead typically dominates below a few thousand elements, and memory-bandwidth-bound kernels often see diminishing returns beyond available hardware threads.

See Also

  • std::iota and std::transform_reduce — in <numeric> alongside std::accumulate and scan algorithms
  • std::ranges:: overloads — C++20 projections and sentinel support clean up every algorithm in this family
  • std::merge / std::inplace_merge — for combining sorted ranges without element-wise replacement