skip to content

Algorithms and Ranges

The <algorithm> header and C++20 ranges replace hand-written loops with named, composable operations. Interviewers ask about erase-remove, sort guarantees and lazy views.

on this pageshow

explore

questions

17

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

In C++, how do you sort a std::vector of structs by one member using std::sort and a lambda comparator?

level: juniorimportance: must knowfreq 75%

basics

~20 s

Call std::sort(v.begin(), v.end(), comp) where comp is a lambda taking two const references and returning true when the first must come before the second, such as a.score > b.score for highest-first. Equal elements end up in no particular 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

What do C++20 std::ranges algorithms such as std::ranges::sort(readings, {}, &Reading::timestampMs) offer over the classic std::sort?

level: middleimportance: must knowfreq 50%

basics

~20 s

std::ranges algorithms take a whole range instead of an iterator pair, accept a projection that selects the key to compare (a member pointer works), are constrained by concepts so misuse fails early, and return useful iterators, such as the end of the processed range.

open as a page

On a sorted C++ vector, how do std::binary_search, std::lower_bound, std::upper_bound and std::equal_range differ?

level: middleimportance: must knowfreq 60%

basics

~20 s

std::binary_search only answers whether a value is present. std::lower_bound returns the first position not less than the value, std::upper_bound the first position greater than it, and std::equal_range returns both, bracketing every equivalent element. All need data ordered by the same comparator.

open as a page

In C++, how does std::stable_sort differ from std::sort, and what does that difference cost?

level: middleimportance: must knowfreq 65%

basics

~20 s

std::stable_sort keeps elements that compare equivalent in their original relative order; std::sort may reorder them. Stability usually costs a temporary buffer and, if that memory is unavailable, up to N log squared N comparisons instead of N log N.

open as a page

In C++20, what does readings | std::views::filter(f) | std::views::transform(g) | std::views::take(2) build, and when does f run?

level: juniorimportance: should knowfreq 50%

basics

~20 s

It builds a lazy view that refers to readings and stores f, g and the count; nothing is examined yet. f and g run only while something iterates the view, one element at a time, until take has yielded two.

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

In C++23, how do you turn a views pipeline such as std::views::iota or std::views::split into a std::vector, and why must you?

level: middleimportance: should knowfreq 40%

basics

~20 s

A view only describes elements, so to store, index or return the results you materialise them. C++23's std::ranges::to does it: v | std::ranges::tostd::vector(). In C++20 you construct the container from the view's iterators or loop with push_back.

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

Why does C++20 std::ranges::find(loadReadings(), 7, &Reading::sensorId) return std::ranges::dangling instead of an iterator, and when does it not?

level: seniorimportance: should knowfreq 35%

basics

~20 s

The temporary vector from loadReadings() dies at the end of the statement, so an iterator into it would dangle. For an rvalue range that is not borrowed, ranges algorithms return std::ranges::dangling, which cannot be dereferenced.

open as a page

In a C++20 views::transform then views::filter pipeline, why does the transform run twice for kept elements, and why can a const reference to it not be iterated?

level: seniorimportance: should knowfreq 35%

basics

~20 s

views::filter dereferences its base to test each element, and the loop dereferences again to read it, so a transform below the filter runs twice per kept element. filter_view caches its first match in begin(), which therefore is not const for forward ranges.

open as a page

What does passing std::execution::par to std::sort require of your C++ code, and what does it not guarantee?

level: seniorimportance: should knowfreq 30%

basics

~20 s

std::execution::par lets std::sort run comparisons on several threads, so the comparator must be free of data races and must not modify its arguments; an exception escaping it calls std::terminate. It permits parallelism but does not promise it or any speedup.

open as a page

A C++ std::sort call using the comparator [](int a, int b) { return a <= b; } hangs or crashes on many equal scores; why?

level: seniorimportance: should knowfreq 50%

basics

~20 s

std::sort requires the comparator to be a strict weak ordering. a <= b returns true for equal values, so it is not irreflexive, and the program has undefined behaviour: optimised partition loops that trust the comparator can run past the range or never terminate.

open as a page

To keep the top 100 of a million C++ scores, when do you choose std::partial_sort, std::nth_element or a full std::sort?

level: seniorimportance: should knowfreq 45%

basics

~20 s

std::nth_element finds the top 100 as an unordered set, or the 100th score, in linear time on average. std::partial_sort also ranks them, at about N log K comparisons. A full std::sort is for when every rank is needed.

open as a page

Your team builds one C++20 codebase with GCC, Clang and MSVC; how do you decide how far to adopt std::ranges and views?

level: principalimportance: nice to knowfreq 25%

basics

~20 s

Adopt in tiers: ranges algorithms with projections broadly, as they stay eager; views for local one-pass pipelines under lifetime rules; C++23 pieces like ranges::to behind feature tests. The oldest shipped standard library and measured build and debug costs gate each tier.

open as a page