3

根据[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)中完美转发，这意味着我们似乎无法仅使用 3 个投影来完美实现.__proj_valcompstd::ranges::clamp

为什么要std::ranges::clamp如此严格地限制投影数量？这是否意味着需要临时存储投影结果以满足复杂性要求？还是我对这种复杂性要求的理解是错误的？

4

2 回答 2

4

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

它还需要完美转发预计值（libstdc++ 无法做到）。这是有效的，因为invoke表达式需要不修改其参数（来自 的要求regular_invocable），并且是必需的，因为 inindirect_strict_weak_order不需要使用iter_reference_t<I1>&，仅iter_reference_t<I1>和的可调用性iter_value_t<I1>&。

于 2021-05-01T16:05:07.247 回答
1

转发是有条件的移动。移动的意思是“我不再需要这个值了”。仅重新计算一个值以便我们可以更频繁地移动它是愚蠢的；我们的选择是创建 2 并移动两者，或者创建 1，使用它，然后在完成后移动它。

于 2021-05-01T16:06:14.883 回答