`<algorithm>`: `ranges::min`, `ranges::max` and `ranges::minmax` evaluate each element twice

Describe the bug

std::ranges::min/max/minmax over a views::transform range invoke the transform roughly twice per element. libstdc++ invokes it once, and libc++'s count depends on the data. Since these overloads return range_value_t<R> by value and are constrained on indirectly_copyable_storable, one evaluation per element appears to be permitted.

Command-line test case

// cl /EHsc /std:c++latest /O2 repro.cpp
#include <algorithm>
#include <cstdio>
#include <ranges>
#include <vector>

int calls = 0;
struct Entry { double v; double get() const { ++calls; return v; } };

int main() {
    std::vector<Entry> data;
    for (int i = 1; i <= 8; ++i) data.push_back(Entry{static_cast<double>(i)});

    calls = 0;
    (void) std::ranges::min(data | std::views::transform(&Entry::get));
    std::printf("ranges::min    : %d\n", calls);   // 15

    calls = 0;
    double m = 1e300;
    for (const auto& e : data) m = (std::min)(m, e.get());
    std::printf("hand loop      : %d\n", calls);   // 8
}

Godbolt link

Observed (N = 8, so 8 is one call per element and 15 is 2N−1):

	MS STL 19.51	libstdc++	libc++
ranges::min over transform_view	15	8	<=15
ranges::max over transform_view	15	8	<=15
ranges::minmax over transform_view	22	8	22
ranges::fold_left over transform_view	8	8	8
hand-written loop	8	8	8

Expected behavior

One evaluation per element, as libstdc++ achieves.

STL version

Microsoft Visual Studio 18 (Insiders), toolset 14.51.36231, compiler 19.51.36252, x64.

Additional context

[alg.min.max]/7 constrains comparisons and applications of the projection:

Complexity: Exactly ranges::distance(r) - 1 comparisons and twice as many applications of the projection, if any.

Here the projection is identity, and I could not find any wording in [alg.min.max] or [algorithms.requirements] that constrains how many times *i may be evaluated. An implementation that stores range_value_t<R> rather than tracking an iterator would satisfy the stated complexity exactly while halving the dereferences. minmax seems to be even more permissive with its "at most" wording.

Note that [alg.min.max]/27 has similar wording on the min_element variant, except that "if any" is suspiciously missing:

Complexity: Exactly max(last - first - 1,0) comparisons and twice as many projections.

I guess the pedantic reading of this gives the reason why min_element cannot have a similar optimisation (along with minor performance and design quirks on caching reference alongside of the iterator). This is deliberately not part of this report.

Measured impact

I was trying to write a blog post advocating for C++20 ranges, and ran into unexpected performance issues when using costly transform.

With a non-trivial transform (std::cos(angle) * length), MSVC 19.51 /O2: 2.09× a hand-written loop at N = 131072, and 4.77× at N = 2048. MSVC is not able to optimise out the redundancy at /O2 /Ob3 /GL /arch:AVX2 /LTCG or with /fp:fast.

If the maintainers consider this a worthwhile change, I would be happy to prepare a pull request for std::max/min/minmax with identity projection.

Start by locating the ranges::min, ranges::max, and ranges::minmax implementations and their tests, then run the supplied repro.cpp command-line case to measure transform calls. Done means each transform element is evaluated once for these overloads while their stated comparison and projection complexity remains satisfied.