Skip to content
Tutorials Center
My learning

Topics

Lesson 108 of 171 ยท The Standard Library (STL)

Algorithms: Transforming and Modifying

Learn C++ modifying algorithms - copy and copy_if, transform, fill and generate, replace, the remove-erase idiom, unique, reverse, rotate, shuffle and sample.

The previous lesson covered algorithms that look at data and answer questions. This one covers the algorithms that produce or change data: copying all or some elements (copy, copy_if, copy_n), computing new values (transform), filling ranges (fill, generate), replacing values (replace, replace_if), removing elements (remove, remove_if and the C++20 shortcuts std::erase and std::erase_if), deduplicating (unique), and rearranging (reverse, rotate, shuffle, sample).

All of them live in <algorithm> and come in the classic iterator-pair form and the C++20 std::ranges:: form. One rule ties this whole lesson together: algorithms write through iterators and never change a container's size. They can overwrite existing elements, or write through an insert iterator that calls push_back for them, but they can't make room by themselves. Most bugs with modifying algorithms come from forgetting that rule.

Copying: copy, copy_if and copy_n

std::copy(first, last, out) writes every element of [first, last) to the positions starting at out. The destination must already have enough elements, or out must be an insert iterator such as std::back_inserter(v) (see Iterators). copy_if copies only the elements that satisfy a predicate, and copy_n copies exactly n elements.

The ranges versions return a small struct with the input and output positions where they stopped ({in, out}), which tells you how far the output got.

C++ copy, copy_if, copy_n and back_inserter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

If you only want the whole container copied, a plain copy is simpler: auto copy = source; or std::vector<int> copy(source.begin(), source.end());. The copy algorithms earn their keep when the destination already exists, when you copy only part of a range, or when the destination is a different kind of container or a stream.

Overlapping ranges: std::copy is safe when the destination starts before the source (shifting elements left). To shift right within the same container, use std::copy_backward, or better, std::shift_right (C++20), which also handles the bookkeeping for you.

transform: computing new values

std::transform applies a function to each element and writes the results. The unary form takes one input range; the binary form takes two input ranges and combines elements pairwise. The output can be the input itself, which transforms a range in place.

C++ Unary and binary transform

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Three details to note. The std::toupper call goes through a lambda that takes unsigned char, because passing a negative char (possible for non-ASCII bytes) to std::toupper is undefined behavior. &std::string::size works as the operation because the ranges algorithms call it through std::invoke. And {::.3f} formats each element of a range with .3f: the first : starts the range's format spec, the second applies to its elements.

With the binary form, the second range must be at least as long as the first. The classic iterator version only takes a begin iterator for the second range and trusts you; the ranges version stops at the shorter of the two.

For transforming lazily, without creating a new container at all, use std::views::transform from the ranges lesson.

fill and generate

  • fill(r, value) and fill_n(out, n, value) set elements to one value.
  • generate(r, f) and generate_n(out, n, f) call f() once per element and store each result, which is useful with stateful lambdas and random numbers.
  • std::iota (in <numeric>) fills with consecutive values; it's covered in Numeric Algorithms.
C++ fill, fill_n, generate and generate_n

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

generate takes its function object by value, so the Fibonacci lambda's state lives in the algorithm's copy. That's fine here because we only need the output. The random engine, on the other hand, is captured by reference so the algorithm draws from your engine and leaves it advanced; Random Numbers explains engines and distributions.

replace and replace_if

replace(r, old_value, new_value) overwrites every element equal to old_value; replace_if(r, pred, new_value) overwrites every element where the predicate holds. The _copy variants (replace_copy, replace_copy_if) leave the input alone and write the modified sequence elsewhere.

C++ replace, replace_if and replace_copy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

replace swaps single elements for single elements. To replace a substring inside a std::string, use the string's own replace member (see String Methods).

Removing elements: remove, erase and erase_if

std::remove and std::remove_if can't shrink a container, because they only have iterators. They move the elements to keep to the front and return the new logical end; the leftover tail holds unspecified values. You finish the job with the container's erase. That two-step pattern is the erase-remove idiom, explained in depth in std::vector in Depth.

Since C++20, std::erase(c, value) and std::erase_if(c, pred) do both steps in one call for every standard container and return how many elements were removed. Prefer them. The ranges form std::ranges::remove returns the subrange of leftovers, which is exactly what you pass to erase.

C++ remove_if versus std::erase_if

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

unique: removing adjacent duplicates

std::unique collapses runs of adjacent equal elements into one, again by shifting the survivors forward and returning the new end. It doesn't find duplicates that are far apart, so the usual recipe for "remove all duplicates" is sort, then unique, then erase. If you need the original order preserved, or the data is large, a std::unordered_set filter or a std::set may be the clearer choice (see std::set).

C++ unique after sort, and with a custom rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The first line of output, [3, 1, 3, 2, 1, 2], shows that unique only merges neighbors. After sorting, equal values are neighbors, so the second line becomes [1, 2, 3].

Rearranging: reverse, rotate, shuffle and sample

  • reverse(r) reverses in place; reverse_copy writes a reversed copy.
  • rotate(first, middle, last) moves [middle, last) to the front and [first, middle) after it. It returns where the old first element ended up. It's the right tool for "move this block to there".
  • shift_left / shift_right (C++20) slide elements by n positions, leaving moved-from values at the vacated end.
  • shuffle(r, engine) randomly permutes; it needs a random engine such as std::mt19937. (The old std::random_shuffle was removed in C++17.)
  • sample(r, out, n, engine) picks n distinct elements at random, keeping their relative order.
C++ reverse, rotate, shuffle and sample

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The playlist line is a reusable recipe: to move the element at from to the earlier position to, rotate [to, from + 1) so that from becomes its first element. Moving an element later works the same way with the roles swapped: std::rotate(from, from + 1, to + 1).

Shuffle results depend on the library's implementation as well as the seed, so the same seed may give a different order with another compiler. For real randomness, seed the engine from std::random_device.

Common mistakes

  • Writing into an empty container. std::ranges::copy(src, dst.begin()) with an empty dst is undefined behavior. Size the destination first or use std::back_inserter(dst).
  • Forgetting erase after remove or unique. The size doesn't change until you erase the tail. Prefer std::erase_if.
  • Expecting unique to remove all duplicates. It only merges adjacent runs; sort first.
  • Shifting right with copy inside one container. Overlapping to the right needs copy_backward or shift_right.
  • Holding iterators across modifications. erase (and insertion via back_inserter into the same vector) invalidates iterators; see Iterators.
  • Passing plain char to std::toupper/std::tolower. Convert to unsigned char first.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. std::vector<int> v{1, 2, 2, 3, 2}; After std::erase(v, 2);, what is v?

    std::erase removes every element equal to the value and shrinks the container, so only 1 and 3 remain.
  2. 2. What is wrong with std::vector<int> out; std::ranges::transform(in, out.begin(), f);?

    Algorithms never grow containers. The destination needs room, or an insert iterator.
  3. 3. std::vector<int> v{4, 4, 1, 4}; After auto r = std::ranges::unique(v); v.erase(r.begin(), r.end());, what is v?

    unique merges only adjacent equal elements. The two leading 4s become one, but the last 4 is not next to them.
  4. 4. std::vector<int> v{1, 2, 3, 4, 5}; std::ranges::rotate(v, v.begin() + 1); What is v?

    The element at the middle iterator (2) becomes the first element, and the elements before it move to the end. That is a left rotation by one.
  5. 5. Which call keeps names unchanged and writes only the names longer than 3 characters into long_names?

    copy_if reads the input without modifying it and writes matching elements through the back_inserter.

Summary

  • Modifying algorithms write through iterators and never resize containers: give them room, or an insert iterator such as std::back_inserter.
  • copy, copy_if and copy_n copy all, some or the first n elements; copy_backward and shift_right handle overlapping moves to the right.
  • transform maps one range, or two ranges pairwise, into an output, which may be the input itself.
  • fill/fill_n set a value, generate/generate_n call a function per element, and replace/replace_if overwrite matching values; _copy variants leave the input untouched.
  • remove/remove_if/unique only move survivors forward; finish with erase, or use C++20's std::erase and std::erase_if. unique merges adjacent duplicates only, so sort first.
  • reverse, rotate, shuffle (with an engine like std::mt19937) and sample rearrange or pick elements; rotate moves blocks to new positions.

Next: Numeric Algorithms, where accumulate, reduce, partial_sum, iota and transform_reduce turn ranges into sums, products and running totals.