时间戳

首页 > 解决方案 > 缺少 std::maximum 的设计考虑是什么？

c++ - 缺少 std::maximum 的设计考虑是什么？

问题描述

C++ 标准库支持各种函数对象，包括关联二进制函子std::plus和std::multiplies，它们是各种通用折叠算法的有用参数，例如std::accumulate、std::reduce或tbb::parallel_reduce。

我正在实现一个Fenwick 树以将关联二元运算符作为模板参数（默认为std::plus<void>）。一种可能的参数选择是最大（和最小）运算符

template<typename T=void>
struct maximum
{
    constexpr T operator() (T const&x, T const&y) const
    { return x>y? x:y; }
};

template<>
struct maximum<void>
{
    template<typename T>
    constexpr T operator() (T const&x, T const&y) const
    { return x>y? x:y; }
};

当芬威克树可以在任何元素的前缀中找到最大值时，或者在一个元素范围内，以对数时间计算。

然而，令我惊讶的是，标准库中不存在这样的二进制最大仿函数。当然，我可以使用我自己的，但这使得将代码专门用于一般用途是不可能的。例如，更新 Fenwick 树以更改一个元素可以在最大值的情况下进行优化：如果树节点表示的范围中的先前最大值超过新值，则可以终止树传递。

那么，是否有任何严重的理由没有std::maximum和std::minimum（除了没有人提出它）？

请注意，这里std::max没有选项：

std::accumulate(v.begin(), v.end(), 0, std::max<T>);

不起作用（在 C++11 中，但它以前做过），而不是（使用上面maximum）

std::accumulate(v.begin(), v.end(), 0, std::plus<void>{});
std::accumulate(v.begin(), v.end(), 0, maximum<void>{});

另一个选项是通用选择函子，将比较函子作为参数，例如

template<typename T, typename Compare = std::greater<T> >
struct select
{
    constexpr T operator()(T const&x, T const&y) const
    { return comp(x,y)? x:y; }
  private:
    Compare comp;        
};

并select<void>以类似的方式。

标签： c++c++11functorfold

解决方案

Accumulate 是一个模板函数，它只是试图调用累加器函数，不管是Callable普通函数还是普通函数（嗯，普通函数本身就是 Callable），所以使用 this 是完全有效的

cout << std::accumulate(v.begin(), v.end(), 0, std::max<YOUR_TYPE_HERE>);

如果您的类型很复杂（例如任何不适用于 max 的类型），您可以传入自定义 lambda 表达式（仅限 C++ 11 之后的版本）：

cout << std::accumulate(v.begin(), v.end(), 0, [](int a, int b){return a > b ? a : b;});

（替换int为您的类型，并替换return a > b ? a : b;为您想要的逻辑）

如果您的编译器拒绝编译第一个并且您使用的是 C++11 之前的内容，您可以尝试这一行（不安全）

cout << std::accumulate(v.begin(), v.end(), 0, std::ptr_fun(std::max<int>));

std::ptr_fun将 ANY FUNCTION 转换为函数对象，因此可以使用它，请参阅此参考http://www.cplusplus.com/reference/functional/ptr_fun/

还有一个类std::pointer_to_binary_function可以帮助你更多。这是它的参考http://www.cplusplus.com/reference/functional/pointer_to_binary_function/

推荐阅读