The <algorithm> header has a second large family beyond searching: algorithms that produce a modified version of a range. They cover the transformations that would otherwise need loops: copying, mapping values, replacing matches, filling, reversing, and removing. This chapter walks through each operation, the output iterator concept that makes them composable, and the erase-remove idiom that is a common source of confusion.

A modifying algorithm writes into a range. Some write into the same range they read from (in-place); others write into a separate destination range. The names follow a convention: anything called xxx_copy writes to a destination range and leaves the source untouched; the unsuffixed xxx modifies the source in place.

std::replace rewrites the source; std::replace_copy writes the result to a separate output range and leaves the source as it was. Use the in-place version when the original isn't needed; use the copy version when it is.

Most modifying algorithms return an iterator one past the last position they wrote. That return value matters more than it first appears. It lets algorithms chain, and it's the only honest way to know "how many elements were produced?" when the answer might be less than the input.

One concept needs a clear introduction: the output iterator. A modifying algorithm that writes to a destination range needs the destination to already have enough room. If the destination is a std::vector with size zero, writing through vec.begin() is undefined behaviour, because there's nowhere to write.

The fix is one of two patterns. Pre-size the destination so it has the right capacity:

Or use an insert iterator that calls push_back on each write instead of overwriting an existing slot. std::back_inserter is the standard one.

std::back_inserter(dest) produces an output iterator that translates *it = value into dest.push_back(value). The destination grows as the algorithm runs. This is the idiomatic way to fill a vector with the output of a modifying algorithm when the size isn't known ahead of time.

back_inserter is convenient, but every push_back may cause a reallocation. When the output size is known in advance, dest.reserve(n) before the algorithm avoids the geometric-growth allocations. For very large outputs, this matters.

There are also std::front_inserter (uses push_front, requires the container to support it like std::deque) and std::inserter (inserts at an arbitrary position, useful for std::set and std::map), but back_inserter covers most cases.

std::copy(first, last, dest) copies every element from [first, last) to the range starting at dest. It returns an iterator one past the last element written to the destination.

This is the explicit form of "copy these items into another container." For a flat copy of one container into another of the same type, the constructor or assignment operator is usually simpler:

std::copy is useful when copying into a different container type, into an existing container at a specific position, or into a stream via std::ostream_iterator.

std::ostream_iterator<int>(std::cout, " ") is an output iterator that translates each write into std::cout << value << " ". The same algorithm now sends elements to an output stream instead of another container. This composability is the reason output iterator is its own concept.

std::copy_if for Filtered Copies

std::copy_if(first, last, dest, pred) copies only elements for which pred(element) is true. The destination size is at most the source size; use back_inserter when the count isn't known in advance.

copy_if is the closest STL has to a "filter" operation in the functional sense. The C++20 ranges library makes this even cleaner, but copy_if is the C++17 baseline.

std::copy_n and std::copy_backward

std::copy_n(first, count, dest) copies exactly count elements starting at first. It's useful when the count comes from somewhere other than an end iterator.

std::copy_backward(first, last, dest_last) is the rare one. It copies the range starting from the end and walking backward, writing into the destination ending at dest_last. The use case is in-place copies where the destination range overlaps the source, with the destination shifted forward. std::copy would step on its own tail; std::copy_backward doesn't.

The forward std::copy would have produced wrong output because it would have overwritten 3 before reading it. copy_backward reads 5 first, writes it into the last slot, then 4, then 3, and so on.

std::move: The Algorithm, Not the Cast

There's a function in <algorithm> called std::move that is distinct from the std::move cast in <utility>. The algorithm std::move(first, last, dest) moves every element from the source range into the destination range, leaving the source elements in their moved-from state.

The post-move state of the source elements is "valid but unspecified." For std::string, most implementations leave them empty, but the standard only guarantees they're in a state where destruction and assignment are safe. Don't read meaningful values from a moved-from object.

std::move (the algorithm) is the same number of element operations as std::copy, but each element's move is usually cheaper than its copy for types with expensive copies like std::string or std::vector<T>. For trivially copyable types (int, double), move is identical to copy.

std::transform is the closest STL has to a functional map. It applies a function to each element of a range and writes the result to a destination. There are two forms: unary (one input range) and binary (two input ranges combined element-wise).

Unary transform

Each price is mapped through p * 0.9 and the result is appended to the destination. The transform function can produce a different type than the input. The destination iterator's value type determines what gets written.

An in-place transform passes the same iterator as source and destination.

The original prices are gone; this is the in-place form. Use it when the original values aren't needed.

Binary transform

The binary form takes two input ranges and combines them element-by-element. The second range must be at least as long as the first.

This is the "zip-and-combine" pattern: pair up two parallel ranges and produce a third. For a shopping cart, this turns parallel prices and quantities vectors into a vector of line totals in one call.

std::replace(first, last, old_value, new_value) rewrites the range, replacing every occurrence of old_value with new_value. The comparison is by operator==.

std::replace_if(first, last, pred, new_value) is the predicate-based version. It rewrites every element for which pred(element) returns true.

replace_copy and replace_copy_if are the non-mutating versions. They write to a destination range and leave the source untouched.

Use the _copy variants when the original is needed. The in-place forms are slightly faster (no extra allocation), but they destroy the original data.

std::fill(first, last, value) writes the same value to every element in the range. std::fill_n(first, n, value) writes n copies starting at first.

std::generate(first, last, generator) calls generator() for each element and stores the result. Use it for a different value at each slot, computed by some rule.

The lambda captures next by reference and increments it on each call. The capture-and-mutate pattern is what makes generate useful as a sequence builder. std::generate_n(first, n, generator) is the count-bounded version, useful when paired with back_inserter.

std::generate is O(n) calls to the generator. The generator runs once per slot, so a slow generator dominates the runtime. For trivial generators like a counter, the loop is as cheap as a plain for.

std::reverse(first, last) reverses the range in place. std::reverse_copy writes the reversed range to a destination and leaves the source alone.

std::rotate(first, middle, last) rotates the range so that the element at middle becomes the new first element. Everything before middle is shifted to the end, in order. It returns an iterator to where the original first element ended up.

A common application is moving an element to the front: find the iterator, then rotate [begin, that_iter, that_iter + 1) (or [begin, that_iter + 1, end) to move it to the back).

std::shuffle(first, last, urbg) randomly permutes the range using a uniform random bit generator. The <random> library provides std::mt19937 for this.

std::shuffle replaced the older std::random_shuffle in C++14 (deprecated in C++14, removed in C++17) because the older one used std::rand, which has poor statistical properties. Always pass an explicit URBG like std::mt19937.

The seed matters. A fixed seed like 42 gives the same shuffle every run, which is useful for tests. For randomness, seed from std::random_device:

The name std::remove suggests it removes elements from the container. It doesn't. It can't: it only sees iterators, not the container, and there's no way to shrink the container through an iterator.

What std::remove(first, last, value) does: walk the range, and for each element that doesn't compare equal to value, move it forward into the next "kept" slot. It returns the iterator one past the last kept element. Everything from that iterator to last is in an unspecified state, but the container's size() is unchanged.

A common buggy first attempt:

The first four slots are the "kept" elements, but the last two are leftover garbage from the move. The vector's size is still 6. The "removed" 999s are still counted in cart.size().

The fix is the erase-remove idiom: feed the iterator returned by std::remove into cart.erase(...) to actually shrink the container.

std::remove shuffled the kept elements forward and returned the iterator to where the kept range ends. cart.erase(thatIter, cart.end()) then truncates the vector to discard the leftover slots. The size and the contents are now consistent.

That diagram is the erase-remove idiom in one picture. remove rearranges, returns a new logical end, and erase does the actual shrinking.

std::remove_if(first, last, pred) is the predicate version: every element for which pred returns true is removed. The erase-remove pattern is identical.

Two out-of-stock entries are gone, and the catalog is now two items shorter. Without the surrounding erase(..., end()), the vector would still hold all five entries, and the last two would contain unspecified data.

std::unique(first, last) collapses runs of consecutive equal elements into a single element. Like std::remove, it doesn't change the container's size; it returns the new logical end and leaves the tail in an unspecified state. Pair it with erase to actually shrink.

unique only collapses consecutive duplicates. To deduplicate a sequence regardless of order, sort it first and then call unique:

The sort makes equal elements adjacent; unique then collapses them. To preserve the original order, a different approach is needed (a std::unordered_set to track seen ids while iterating).

std::unique also accepts an optional binary predicate that decides when two adjacent elements should be treated as equal. That's useful for "fuzzy" dedup, like treating readings within 0.01 of each other as the same:

The predicate decides whether two adjacent values are close enough to be considered duplicates. Three runs collapse to one representative each.

C++20 added free functions std::erase and std::erase_if that bundle the erase-remove idiom into a single call. They live in the container header (e.g., <vector>, <string>), not in <algorithm>.

std::erase_if is the predicate version. It's the shortest spelling and the one to prefer in new C++20 code:

On C++17 or earlier, the erase-remove idiom is the only option. On C++20 or newer, std::erase_if is shorter, safer, and equally efficient.

A small program that uses several modifying algorithms together to clean up a shopping cart, apply a discount, and produce a final receipt.

Each step in that pipeline is a single algorithm call. The same logic written as nested loops would be three or four times as long and harder to verify by reading. That readability advantage is the main reason to learn the modifying algorithms; they make intent visible at the call site.