vendredi 20 juillet 2018

What are the design considerations for the lack of std::maximum?

The C++ standard library supports various function objects, including the associative binary functors std::plus and std::multiplies, which are useful arguments for various general fold algorithms, such as std::accumulate, std::reduce, or tbb::parallel_reduce.

I was implementing a Fenwick tree to take the associative binary operator as template argument (defaulting to std::plus<void>). One possible choice of argument is the maximum (and minimum) operator

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; }
};

when the Fenwick tree can find the maximum value in the prefix of any element, or in a range of elements, in logarithmic time.

However, to my surprise, such a binary maximum functor does not exist in the standard library. I can, of course, use my own, but that makes it impossible to specialise the code for general use. For example, updating a Fenwick tree for a change of one element can be optimized in case of maximum: the tree pass can be terminated if the previous maximum in the range represented by a tree node exceeds the new value.

So, are there any serious reasons for not having std::maximum and std::minimum (other than nobody has proposed it yet)?

Note that std::max is no option here:

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

does not work (in C++11 but it did before), as opposed to (using above maximum)

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

Another option would have been a general select functor taking a compare functor as argument, for example

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;        
};

and select<void> in a similar fashion.

Aucun commentaire:

Enregistrer un commentaire