In C++, how do std::transform and std::copy_if write into a new vector, and why is std::back_inserter needed?
answer
- output iterator, not container
- algorithms assign, never push
- empty destination is the trap
- back_inserter calls push_back
- or size it first
basics
~20 sBoth 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#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
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.
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.
Catch empty-destination writes and lambdas with side effects passed to transform, and choose inserter, front_inserter or back_inserter per container.
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