为什么 std::ranges::clamp 如此严格地限制投影的数量?
Why does `std::ranges::clamp` limits the number of projections so strictly?
根据[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给出:
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;
但是为了安全起见,我们似乎无法在第一个comp
调用中使用std::forward<decltype(__proj_val)>(__proj_val)
来完美转发__proj_val
,也就是说我们似乎无法使用只有 3 个投影 完美地 实现了 std::ranges::clamp
。
为什么std::ranges::clamp
如此严格地限制投影数量?这是否意味着为了复杂度的要求,需要将投影的结果暂存起来呢?还是我对这个复杂性要求的理解有误?
这是非常有意的。在 LWG 审查布拉格的论文期间,我特别询问了这种复杂性要求,因为它禁止“显而易见”的实施。是的,这需要实现调用值的投影并使用 auto&&
或等价物“将结果暂停在半空中”。
它还需要完美转发投影值(libstdc++ 做不到)。这是有效的,因为要求 invoke
表达式不修改其参数(来自 regular_invocable
的要求),并且是必需的,因为 indirect_strict_weak_order
中的任何内容都不需要使用 iter_reference_t<I1>&
调用, 只有 iter_reference_t<I1>
和 iter_value_t<I1>&
.
转发是有条件的。移动意味着“我不再需要这个值”。仅仅重新计算一个值以便我们可以更频繁地移动它是愚蠢的;我们的选择是创建 2 并移动两者,或者创建 1,使用它,然后在完成后移动它。
根据[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给出:
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;
但是为了安全起见,我们似乎无法在第一个comp
调用中使用std::forward<decltype(__proj_val)>(__proj_val)
来完美转发__proj_val
,也就是说我们似乎无法使用只有 3 个投影 完美地 实现了 std::ranges::clamp
。
为什么std::ranges::clamp
如此严格地限制投影数量?这是否意味着为了复杂度的要求,需要将投影的结果暂存起来呢?还是我对这个复杂性要求的理解有误?
这是非常有意的。在 LWG 审查布拉格的论文期间,我特别询问了这种复杂性要求,因为它禁止“显而易见”的实施。是的,这需要实现调用值的投影并使用 auto&&
或等价物“将结果暂停在半空中”。
它还需要完美转发投影值(libstdc++ 做不到)。这是有效的,因为要求 invoke
表达式不修改其参数(来自 regular_invocable
的要求),并且是必需的,因为 indirect_strict_weak_order
中的任何内容都不需要使用 iter_reference_t<I1>&
调用, 只有 iter_reference_t<I1>
和 iter_value_t<I1>&
.
转发是有条件的。移动意味着“我不再需要这个值”。仅仅重新计算一个值以便我们可以更频繁地移动它是愚蠢的;我们的选择是创建 2 并移动两者,或者创建 1,使用它,然后在完成后移动它。