c++ - 为什么 `std::ranges::clamp`会如此严格地限制投影数量？

Question

根据 [alg.clamp#5] , 时间复杂度为 std::ranges::clamp 最多需要 2 次比较和 3 预测应用。 cppreference 中的可能实现由:

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;

这显然不符合要求，因为它涉及3次比较和6投影。即使我们注释掉 assert , 投影的数量仍然是 4 因为 std::invoke(proj, v)被执行了两次。

我能想到的唯一办法就是把std::invoke(proj, v)的结果暂存起来, 然后传递给接下来的两个 comp调用，就像 libstdc++做:

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;

但是为了安全，我们好像不能用std::forward<decltype(__proj_val)>(__proj_val)完美转发__proj_val在第一个comp调用，这意味着我们似乎无法使用仅 3 投影来完美实现std::ranges::clamp .

为什么 std::ranges::clamp如此严格地限制投影数量？这是否意味着为了复杂度的要求，需要将投影的结果暂存起来呢？还是我对这种复杂性要求的理解有误？

Answer 1

这是非常有意的。在 LWG 审查布拉格的论文期间，我特别询问了这种复杂性要求，因为它禁止“显而易见”的实现。是的，这需要实现调用值的投影并使用 auto&&“将结果悬停在半空中”或等效的。

它还需要完美转发投影值(libstdc++ 做不到)。这是有效的，因为 invoke要求表达式不修改其参数(来自 regular_invocable 的要求)，并且是必需的，因为 indirect_strict_weak_order 中没有任何内容需要调用 iter_reference_t<I1>& , 只有 iter_reference_t<I1>和 iter_value_t<I1>& .