Ch8.5: Projections

Overview

A projection is a function applied to each element before an algorithm uses it. Instead of operating on the element directly, the algorithm operates on the projected value. This allows algorithms to work with derived fields or computed values without modifying the underlying data structure.

Projections are conceptually simple: the algorithm sees proj(x) instead of x. But understanding how projections interact with iterators, references, and algorithm semantics is essential for writing correct and efficient code.

1. What is a projection?

A projection is a unary function applied to each element before the algorithm processes it. For example, if we have a struct with two numeric fields, we can sort by one of them using a projection.

struct Record {
    ::std::size_t index;
    ::std::ptrdiff_t offset;
};

::fast_io::vector<Record> v = {
    {3, -10},
    {1,  25},
    {2,   5}
};

// Sort by the offset field
::std::ranges::sort(v, {}, &Record::offset);
      

The algorithm never compares Record objects directly. It compares the projected values returned by &Record::offset.

2. Why projections exist

Without projections, customizing algorithms often required:

• writing custom comparison lambdas
• repeating field names everywhere
• rewriting algorithms manually

Projections eliminate this boilerplate. They let you specify what part of the element the algorithm should use, without changing how the algorithm works.

3. Projections vs comparators

A comparator defines how two projected values are compared. A projection defines what part of the element is compared.

// Comparator only:
::std::ranges::sort(v, [](auto const& a, auto const& b) {
    return a.offset < b.offset;
});

// Comparator + projection:
::std::ranges::sort(v, {}, &Record::offset);
      

The projection version is shorter, avoids captures, and avoids duplicating field names. It also reduces binary size compared to lambdas.

4. Projections must be pure and cheap

Projections are called many times. They must be:

• pure (no side effects)
• cheap (ideally trivial)
• safe (no references to temporaries)

A projection should behave like a field access. Anything more expensive risks destroying algorithmic performance.

// Bad: expensive projection
::std::ranges::sort(v, {}, [](auto const& r) {
    return r.offset * r.offset * r.offset; // expensive
});
      

This turns O(n log n) sorting into something much worse.

5. Projections and references

A projection may return a reference, but only if the reference remains valid for the duration of the algorithm. Returning references to temporaries is undefined behavior.

// Bad: returns reference to a temporary
::std::ranges::sort(v, ::std::ranges::greater{}, [](auto const& r) -> ::std::ptrdiff_t const& {
    return r.offset + 1; // temporary
});
      

Safe projections return:

• a field reference
• a pointer
• a small value (copied cheaply)

6. Projections and stability

Projections do not change whether an algorithm is stable. They only change what the algorithm sees. If two elements have equal projected values, a stable algorithm preserves their original order.

Key takeaways

• A projection transforms each element before the algorithm sees it.
• Projections simplify code and reduce boilerplate.
• They must be pure, cheap, and safe.
• Returning references to temporaries is undefined behavior.
• Projections do not change algorithm stability.
• Using simple POD‑like types keeps projections efficient.