skip to content

Erase-Remove and Transforms

std::remove only shuffles elements to the end, so erase must follow; C++20 std::erase_if does both. Interviewers ask for the idiom and for transform, accumulate and reduce.

on this pageshow

explore

questions

5

In C++, how do std::transform and std::copy_if write into a new vector, and why is std::back_inserter needed?

level: juniorimportance: must knowfreq 60%

answer

  1. output iterator, not container
  2. algorithms assign, never push
  3. empty destination is the trap
  4. back_inserter calls push_back
  5. or size it first

basics

~20 s

Both write through an output iterator by assignment and never grow the destination. Passing out.begin() of an empty vector writes past its end, which is undefined behaviour; std::back_inserter(out) turns each assignment into out.push_back, or you size the vector first.

solid answer

~40 s

`std::transform(first, last, out, op)` assigns `op(*it)` through the output iterator `out` for each input element, and `std::copy_if(first, last, out, pred)` assigns only the elements for which `pred` is true, keeping their order. Neither knows about the destination container, so neither can add elements. With an empty `std::vector`, `out.begin()` points at nothing and every write is undefined behaviour. `std::back_inserter(dest)` returns a `std::back_insert_iterator` whose assignment calls `dest.push_back(value)`, so the vector grows as needed; `reserve` first if the size is known. For `std::transform` you may instead size the destination (`std::vector<T> dest(src.size())`) and pass `dest.begin()`. `copy_if` usually needs `back_inserter`, since the output count is unknown. `std::iota(first, last, start)` from `<numeric>` is the opposite case: it fills an existing range with `start, start + 1, ...` and needs a sized destination.

code

cpp · 31 lines
cpp
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <numeric>
#include <string>
#include <vector>

struct LogRecord {
    std::string level;
    std::int64_t epochMillis;
};

int main() {
    std::vector<LogRecord> log{{"INFO", 1'700'000'000'123}, {"ERROR", 1'700'000'004'500},
                               {"WARN", 1'700'000'009'999}, {"ERROR", 1'700'000'012'000}};

    std::vector<std::int64_t> seconds;            // empty: grow it with back_inserter
    seconds.reserve(log.size());
    std::transform(log.begin(), log.end(), std::back_inserter(seconds),
                   [](const LogRecord& r) { return r.epochMillis / 1000; });

    std::vector<LogRecord> errors;
    std::copy_if(log.begin(), log.end(), std::back_inserter(errors),
                 [](const LogRecord& r) { return r.level == "ERROR"; });

    std::vector<int> lineNo(log.size());          // sized: iota writes in place
    std::iota(lineNo.begin(), lineNo.end(), 1);

    std::cout << seconds.front() << ' ' << errors.size() << ' ' << lineNo.back() << '\n';
}

go deeper

for a junior

Know the shapes: transform and copy_if take an output iterator, and std::back_inserter(vec) makes them append; std::iota fills an already sized range.

for a middle

Explain why algorithms cannot grow containers, when to pre-size versus use back_inserter with reserve, and that transform may run in place while copy_if may not.

for a senior

Catch empty-destination writes and lambdas with side effects passed to transform, and choose inserter, front_inserter or back_inserter per container.

for a principal

Decide when algorithm calls beat a plain loop for readability in team code, and keep side-effecting work in loops or for_each.

## Output iterators Many algorithms produce values rather than rearranging existing ones. They take an **output iterator**, `result`, and write each value with `*result = value; ++result;`. That is all they do: an output iterator is a write position, not a container, and an algorithm cannot ask it for more room. Each such algorithm returns the iterator one past the last element it wrote, which tells you how much of the destination it used. `std::transform` and `std::copy_if` are the everyday examples: - `std::transform(first, last, result, op)` writes `op(*i)` for every input element; the binary form combines two input ranges element by element. - `std::copy_if(first, last, result, pred)` writes only the elements for which `pred` is true, in their original order (it is stable), and requires the input and output ranges not to overlap. ## The empty-destination bug ```cpp std::vector<int> in{1, 2, 3}, out; // out is empty std::transform(in.begin(), in.end(), out.begin(), [](int x) { return x * 2; }); ``` This compiles, and it is **undefined behaviour**: `out.begin()` of an empty vector is also its `end()`, and the algorithm assigns through it three times. Built with AddressSanitizer on Apple clang 21, the program stopped with a SEGV on a WRITE access; without a sanitizer it may corrupt the heap silently. The size of `out` is still zero afterwards either way, because nothing called `push_back`. ## Two correct shapes | Approach | Code | When | |---|---|---| | Insert iterator | `std::back_inserter(out)` | output count unknown (`copy_if`), or you prefer not to pre-size | | Pre-sized destination | `std::vector<T> out(in.size());` then `out.begin()` | output count known (`transform`), and `T` is cheap to default-construct | `std::back_inserter(c)` returns `std::back_insert_iterator<C>`; assigning to it calls `c.push_back(value)`. Its siblings are `std::front_inserter` (calls `push_front`, for `deque` and `list`) and `std::inserter(c, pos)` (calls `c.insert(pos, value)`, for sets and maps). With `back_inserter`, call `out.reserve(in.size())` first when you can, so the vector does not reallocate repeatedly. ## Cleaning log records A log pipeline transforms timestamps and extracts errors: 1. `std::transform(log.begin(), log.end(), std::back_inserter(seconds), [](const LogRecord& r) { return r.epochMillis / 1000; });` builds a parallel vector of whole seconds. 2. `std::copy_if(log.begin(), log.end(), std::back_inserter(errors), [](const LogRecord& r) { return r.level == "ERROR"; });` copies the errors, oldest first. 3. `std::iota(lineNo.begin(), lineNo.end(), 1);` numbers the lines 1, 2, 3 in a vector already sized to `log.size()`. `std::transform` may also write **in place**: the standard allows `result` to equal `first`, so `std::transform(v.begin(), v.end(), v.begin(), op)` updates every element. `copy_if` may not overlap its output with its input; for in-place filtering use `remove_if` and `erase`. ## Why not just write a loop? A range-for that calls `push_back` does the same work, and for a one-off it is perfectly readable. The algorithm form earns its place in three ways: - **The name states the intent.** `copy_if` says "filtered copy" before the reader parses the lambda; a loop has to be read to the end. - **The shape is fixed.** There is no index to get wrong and no early `break` hiding in the body. - **It composes with other output iterators.** The same call can write into a `std::set` through `std::inserter`, into a stream through `std::ostream_iterator`, or into a pre-sized buffer, without changing the algorithm. The cost is the output-iterator contract itself: the algorithm will happily write wherever the iterator points, and the empty-destination bug above is the price of forgetting that. ## Details worth knowing - **Order of calls.** `std::transform` promises the result of each position, not the order in which `op` is called, and `op` must not modify the ranges; for side effects in sequence use `std::for_each` or a loop, which are specified to proceed from `first` to `last`. - **Return values.** `copy_if` returns the end of the written range, so with a pre-sized destination you shrink it afterwards: `out.erase(std::copy_if(...), out.end());`. - **`std::iota` lives in `<numeric>`**, not `<algorithm>`, assigns `value` and then increments it with `++value`, and works for any incrementable type: integers, iterators, even `char`.

  • When would you pre-size the destination instead of using std::back_inserter with std::transform?
    When the output count equals the input count and the element type is cheap to default-construct, `std::vector<T> out(in.size())` plus `out.begin()` avoids a `push_back` call per element. When construction is expensive or impossible without arguments, `reserve` plus `std::back_inserter` builds each element once. For `copy_if` the output count is unknown, so `back_inserter` is the natural choice.
  • Why may std::transform write back into its own input range while std::copy_if may not?
    `std::transform` explicitly allows `result` to equal `first1`, because each output position depends only on the input at the same position. `std::copy_if` requires its input and output ranges not to overlap, because it writes fewer elements than it reads and could overwrite input it has not examined yet. In-place filtering is the job of `remove_if` followed by `erase`.

  • Passing begin() of an empty vector as the output of std::transform
  • Believing std::copy_if grows the destination vector by itself
  • Saying std::back_inserter calls insert at the front
  • Calling std::iota on an empty vector to create elements
  • Assuming std::transform calls the lambda strictly in order
open as a page

Why does std::accumulate(v.begin(), v.end(), 0) return a wrong total for a C++ vector of doubles or 64-bit byte counts?

level: middleimportance: must knowfreq 55%

basics

~20 s

std::accumulate's accumulator has the type of the init argument, not the element type. With 0 it is int, so each partial sum of doubles is truncated and 64-bit sums wrap. Pass 0.0, std::int64_t{0} or a value of the element type.

open as a page

In C++, why does std::remove_if not shrink a std::vector, and how do you actually delete the matching elements?

level: middleimportance: must knowfreq 75%

basics

~20 s

std::remove_if works on iterators, so it cannot change the container's size: it moves the kept elements to the front and returns the new logical end. Calling erase(newEnd, end()) deletes the leftovers; C++20's std::erase_if(v, pred) does both steps and returns the count.

open as a page

Why does std::unique on a C++ vector of log messages leave duplicates behind, and what must you do before calling it?

level: middleimportance: should knowfreq 50%

basics

~20 s

std::unique collapses only consecutive equal elements, keeping the first of each run, so duplicates separated by other values survive. Sort the range first so equal values are adjacent, then erase from the returned iterator to end().

open as a page

When can C++17 std::reduce replace std::accumulate, and why can it give a different total for the same data?

level: seniorimportance: should knowfreq 40%

basics

~20 s

std::reduce may combine elements in any grouping and order, so it gives the same result as std::accumulate only for an associative and commutative operation. Floating-point addition is neither exactly, so totals can differ; non-commutative operations like string concatenation give nondeterministic results.

open as a page