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