Why does `std::ranges::clamp` limits the number of projections so strictly?

user_11638718 0
Viewed 200

According to [alg.clamp#5], the time complexity of std::ranges::clamp requires at most 2 comparisons and 3 application of projections. The possible implementation in cppreference is given by:

struct clamp_fn {
  template<class T, class Proj = std::identity,
           std::indirect_strict_weak_order<std::projected<const T*, Proj>> Comp = ranges::less>
  constexpr const T& operator()(const T& v, const T& lo, const T& hi,
                                Comp comp = {}, Proj proj = {}) const
  {
      assert(!std::invoke(comp, std::invoke(proj, hi), std::invoke(proj, lo)));
      return  std::invoke(comp, std::invoke(proj,  v), std::invoke(proj, lo)) ? lo
            : std::invoke(comp, std::invoke(proj, hi), std::invoke(proj,  v)) ? hi : v;
  }
};
 
inline constexpr clamp_fn clamp;

which obviously does not meet the requirements, since it involves 3 comparisons and 6 projections. Even if we comment out the assert, the number of projections is still 4 because std::invoke(proj, v) was executed twice.

The only way I can think of is to temporarily store the result of std::invoke(proj, v), then pass it to the next two comp calls, just like the libstdc++ does:

auto&& __proj_val = std::__invoke(__proj, __val);
if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo)))
  return __lo;
else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val))
  return __hi;
else
  return __val;

But for safety, we seem to be unable to use std::forward<decltype(__proj_val)>(__proj_val) to perfect forward the __proj_val in the first comp call, which means that we seem to be unable to use only 3 projections to perfectly implemented the std::ranges::clamp.

Why does std::ranges::clamp limits the number of projections so strictly? Does this mean that it is necessary to temporarily store the result of projection for the complexity requirement? Or is my understanding of this complexity requirement wrong?

std-ranges c++20 time-complexity c++
2 Answers

This is very much intentional. I asked specifically about this complexity requirement during the LWG review of the paper in Prague because it outlaws the "obvious" implementation. And yes, this requires the implementation to invoke the projection on the value and "suspend the result in mid-air" with auto&& or equivalent.

It also requires perfect forwarding the projected value (which libstdc++ fails to do). This is valid because the invoke expression is required to not modify its arguments (a requirement that comes from regular_invocable), and is required because nothing in indirect_strict_weak_order requires invocability with iter_reference_t<I1>&, only iter_reference_t<I1> and iter_value_t<I1>&.

user_27567190

Forwarding is conditional move. Move means "I do not need this value any more". Recomputing a value only so we can move it more often is silly; our choice is create 2 and move both, or create 1, use it, then move it when done.

user_17746670
Related