skip to content

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%

answer

  1. filter tests, then the loop reads
  2. transform runs on every read
  3. begin() is cached
  4. caching means non-const begin
  5. order the stages deliberately

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.

solid answer

~50 s

A view applies its work on each dereference. In `raw | views::transform(convert) | views::filter(isSpike)`, the filter's iterator calls `isSpike(*base)` to decide whether to stop, which runs `convert`; when the loop then reads the element, `*it` dereferences the transform again and runs `convert` a second time. With four readings and two spikes that is six calls, not four. Put cheap stages first, filter on the raw value when possible, or materialise an expensive transform. Second, the standard requires `filter_view::begin()` to cache the iterator to the first match (for forward ranges) so repeated `begin()` calls stay amortised constant time. Caching mutates the view, so `begin()` is non-const, and a function taking `const auto&` cannot iterate a filter view: Apple clang 21 reports that `begin` "is not marked const". Pass views by value or forwarding reference, and never change an element through the filter so that it stops satisfying the predicate.

code

cpp · 15 lines
cpp
#include <iostream>
#include <ranges>
#include <vector>

int main() {
    std::vector<double> rawMillivolts{120.0, 980.0, 450.0, 990.0};
    int conversions = 0;

    auto spikes = rawMillivolts
                | std::views::transform([&](double mv) { ++conversions; return mv / 10.0; })
                | std::views::filter([](double celsius) { return celsius > 90.0; });

    for (double c : spikes) std::cout << c << '\n';
    std::cout << "conversions: " << conversions << '\n';   // 4 elements, 6 calls
}

go deeper

for a junior

Remember that views compute on demand, so a transform runs whenever an element is read, not once up front.

for a middle

Trace a transform-then-filter pipeline and count the calls, and explain why filter_view::begin() is not const.

for a senior

Reorder stages to avoid duplicate work, pass views by value or forwarding reference, and avoid writes through a filter that break its predicate.

for a principal

Set guidance on side effects in view callables and on generic function signatures so filter views work across the codebase.

## Views do their work on dereference `std::views::transform(g)` does not store transformed values: its iterator's `operator*` calls `g` on the underlying element **every time** it is dereferenced. `std::views::filter(p)` stores no list of matches either: its iterator's `operator++` advances the underlying iterator and evaluates `p(*underlying)` until it finds a match. Combining them exposes how many times each callable really runs. ## Why the transform runs twice Take millivolt readings, convert them to degrees, and keep the spikes: ```cpp auto spikes = raw | std::views::transform(convert) | std::views::filter(isSpike); for (double c : spikes) use(c); ``` For each element: 1. The filter evaluates `isSpike(*t)`, where `t` is the transform iterator; that dereference calls `convert`. 2. If the element passes, the loop's `*it` dereferences the filter iterator, which dereferences `t` again and calls `convert` again. Rejected elements cost one `convert`; kept elements cost two. With four readings and two spikes the example counts six conversions. Remedies, cheapest first: - **Filter first** when the predicate can work on raw data: `raw | views::filter(rawIsSpike) | views::transform(convert)` calls `convert` once per kept element. - **Make the transform cheap** and pure; then duplication only costs time. - **Materialise** the converted values once (a container, or C++23's `std::ranges::to`) when `convert` is expensive, and filter that. - C++26 adds `views::cache_latest`, which caches the last dereferenced value between two adaptors; check your standard library before relying on it. A transform with **side effects** - logging, counting, sending - is the case where the duplication is a bug rather than a cost. ## Why begin() is cached, and what that costs The `range` concept requires `begin()` to be amortised constant time. For `filter_view`, finding the first match may scan many elements, so the standard says `begin()` **caches** its result inside the view when the base is a forward range. libc++ implements it with a `__non_propagating_cache` member filled on the first call. Three consequences: | Consequence | Why | |---|---| | `begin()` is not `const` | it writes the cache | | `const auto&` parameters cannot iterate a filter view | only the const overload would be callable, and for forward ranges it does not exist | | changes to the base before the first `begin()` are seen, later ones may not be | the cached iterator is reused, so a newly matching earlier element is skipped | The same caching applies to `drop_view` and `drop_while_view`. C++26 adds a const `begin()` to `filter_view` only for input-only base ranges, which cannot be re-scanned anyway; a filter over a `std::vector` is still non-const-iterable. ## Modifying elements through a filter Writing through a filter iterator is allowed, but the standard warns that it has undefined behaviour if the element no longer satisfies the predicate when the filter evaluates it again. Clamping every spike to a normal value inside a loop over `spikes` is exactly that pattern. Collect the positions first, or modify through the underlying container after the loop. ## Passing views around - Take views **by value** (`std::ranges::view auto v`) or by forwarding reference (`auto&& r`); views are cheap to copy or move, and both forms keep `begin()` callable. - Do not write generic utilities as `void report(const auto& range)` if callers might pass a filter view; the error appears at the `for` loop inside the utility. - Avoid storing a filter view and iterating it from several threads: the first `begin()` writes the cache, which is a data race if two threads call it concurrently. ## Ordering stages in a telemetry pipeline A realistic pipeline converts, filters, labels and limits: 1. **Cheap, selective filters first**, on raw data where possible, so expensive stages see fewer elements. 2. **Expensive transforms after the last filter**, so each kept element is transformed once, at the loop's read. 3. **`take` last**, remembering that the increment after the final element still runs the filters below it. 4. **No stage with side effects**; if a stage must log or count, move that into the loop body where it runs exactly once per consumed element. Applied to the spike detector: filter raw millivolts above the raw threshold, convert to degrees, attach the sensor label, take the first ten. The conversion runs at most ten times, and the filter's predicate is the only per-element cost on rejected readings. ## Diagnosing in practice A counter in a transform's lambda, or a breakpoint in it, shows the duplicate calls immediately. For the const problem, the compiler error names `begin` and the const `filter_view` type; the fix is in the parameter type, not in the pipeline.

  • How would you restructure the spike pipeline so the conversion runs once per kept reading?
    Filter on the raw value first when the threshold can be expressed in raw units: `raw | views::filter([](double mv) { return mv > 900.0; }) | views::transform(convert)`. Now the filter never dereferences the transform, and the loop's single read calls `convert` once per kept element. When the predicate genuinely needs converted values, materialise the converted readings once and filter the container.
  • Why is iterating one filter view from two threads at once a data race even if neither modifies the data?
    The first call to `filter_view::begin()` writes the cached first-match iterator into the view object. Two threads calling `begin()` on the same view concurrently both try to write that member without synchronisation, which is a data race and undefined behaviour. Give each thread its own copy of the view, or call `begin()` once before sharing.

  • Saying transform_view stores the transformed values
  • Believing each callable in a pipeline runs exactly once per element
  • Writing generic helpers that take const auto& ranges
  • Clamping elements through a filter so they stop matching
  • Assuming filter_view::begin() rescans on every call

Assumes C++23; filter_view and transform_view are C++20, C++26 adds views::cache_latest and a const begin() for input-only filter bases.