How std::views::filter Evaluates Lazily in C++

Introduced in C++20, std::views::filter provides a non-owning, lazy range adaptor that yields only the elements of an underlying range that satisfy a given predicate. Rather than processing the entire collection up front or allocating new storage, std::views::filter defers execution until the elements are actively requested by an iterator. This article explains the internal mechanics of std::ranges::filter_view, detailing how its custom iterator manages traversal, executes predicates on demand, and maintains performance through lazy evaluation.

The Mechanics of Lazy Views

A view in C++ is a lightweight abstraction that holds a reference to an underlying range alongside an operation (like a predicate). When std::views::filter(predicate) is applied to a container—such as via the pipe operator range | std::views::filter(pred)—no filtering occurs immediately.

Instead, it constructs a std::ranges::filter_view object. This object stores only:

  1. A view of the underlying sequence.
  2. An invocable predicate wrapped in a movable-box helper.

No memory allocation occurs, and no elements are examined at the moment of construction.

Finding the First Match: begin()

Lazy evaluation begins when traversal is initiated via .begin(). Because the first element of the underlying container might not satisfy the predicate, filter_view::begin() cannot simply return the underlying container's begin() iterator.

Instead, calling begin() triggers a forward search:

  1. It obtains the underlying iterator pointing to the start of the source range.
  2. It evaluates the predicate against the element: std::invoke(*pred_, *current_).
  3. If the predicate returns false, the iterator advances until an element satisfies the condition or the end of the range is reached.
  4. It returns a filter_view::iterator positioned at this first matching element.

To avoid repeated scans when calling begin() multiple times, std::ranges::filter_view caches the result of the initial search in implementations where the underlying range satisfies forward traversal requirements.

Advancing the Iterator: operator++

Evaluation of subsequent elements is strictly driven by the increment operations (operator++). When advancing:

[Current Match] ---> operator++() ---> Scan underlying range ---> [Next Match or End]

When pre-increment is called on a filter_view::iterator:

  1. The underlying iterator is incremented once: ++current_.
  2. A loop immediately tests each subsequent element using the stored predicate.
  3. The underlying iterator keeps advancing until std::invoke(*pred_, *current_) evaluates to true or reaches ranges::end(base_).
  4. The iterator halts at the newly found valid element.

Because the search happens inside operator++, elements are tested sequentially only when the consumer asks for the next item. If consumption stops early (for example, via break or std::views::take), remaining elements in the underlying container are never inspected.

Dereferencing: operator*

By the time operator* is called, the iterator is already resting on an element that passed the predicate check (ensured either by begin() or the previous operator++). Therefore, dereferencing performs zero computation and zero predicate calls:

constexpr decltype(auto) operator*() const {
    return *current_;
}

It simply returns a reference to the element in the underlying range.

Practical Code Walkthrough

Consider this example tracking evaluation calls:

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6};

    auto evens = numbers | std::views::filter([](int n) {
        std::cout << "[Checking " << n << "] ";
        return n % 2 == 0;
    });

    std::cout << "Filter defined.\n";

    for (int n : evens) {
        std::cout << "Yielded: " << n << "\n";
        if (n == 4) break;
    }
}

Output:

Filter defined.
[Checking 1] [Checking 2] Yielded: 2
[Checking 3] [Checking 4] Yielded: 4
  • Filter defined. prints first, confirming that no predicate executed during view creation.
  • Entering the for loop calls begin(), evaluating 1 (fails) and 2 (succeeds).
  • Advancing the loop evaluates 3 (fails) and 4 (succeeds).
  • The loop breaks at 4. Elements 5 and 6 are never checked.

Performance Characteristics

  • Time Complexity: Traversal takes \(O(N)\) total predicate evaluations over a complete range iteration, matching a standard manual loop.
  • Space Complexity: \(O(1)\) overhead because no intermediate buffers are allocated.
  • Cache Considerations: Since the view does not cache filtered elements, re-iterating over a filter_view will re-evaluate the predicate for every element from the start, trading CPU cycles for minimal memory consumption.