-6

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.

Walter
  • 44,150
  • 20
  • 113
  • 196
  • 4
    What about [`std::min()` and `std::max()`](https://en.cppreference.com/w/cpp/algorithm/min)? – πάντα ῥεῖ Jul 20 '18 at 16:29
  • 1
    A specific specialization of `std::min` and `std::max` would constitute a function object for comparing the types it is specialized for. All function pointers are already functors. – StoryTeller - Unslander Monica Jul 20 '18 at 16:30
  • Possible dupe of: https://stackoverflow.com/questions/1632145/use-of-min-and-max-functions-in-c – πάντα ῥεῖ Jul 20 '18 at 16:31
  • `std::max` and `std::min` are functions, not functors. They cannot be passed (as types) to a template that expects a functor like `std::accumulate`, can they? – Walter Jul 20 '18 at 16:31
  • 1
    @πάνταῥεῖ You're very quick at judging w/o reading the post. The question you suggested as dupe has nothing to do with this one and the suggestion of `std::max` reveals that you have not understood this post either (presumably because you didn't read it). – Walter Jul 20 '18 at 16:44
  • @StoryTeller Okay, then what is the syntax for computing the maximum over a range using `std::accumulate` and `std::max` (w/o using a auxiliary lambda)? – Walter Jul 20 '18 at 16:47
  • @Walter. Well as you clarified your particular concern what about using [`std::greater()`](https://en.cppreference.com/w/cpp/utility/functional/greater) then? Or simply [`std::max_element()`](https://en.cppreference.com/w/cpp/algorithm/max_element)? – πάντα ῥεῖ Jul 20 '18 at 16:47
  • @πάνταῥεῖ `std::greater` is not an associative binary operator. – Walter Jul 20 '18 at 16:49
  • 1
    `std::accumulate(v.begin(), v.end(), 0, std::max);` doesn't work, but `std::accumulate(v.begin(), v.end(), 0, std::max);` sure does. And if having to name `T` doesn't seem sensible to you, then you need to use a lambda. Perhaps that will change when a proposal to automatically lift overload sets into functors comes through, but there it is today. – StoryTeller - Unslander Monica Jul 20 '18 at 16:58
  • @StoryTeller Have you tried it? I did. It doesn't work. Perhaps you should stop telling stories ... sorry couldn't resist ;-). Well indeed it works for C++03. – Walter Jul 20 '18 at 17:02
  • 1
    Sigh... it did work prior to C++11. Yeah, that would have been a breaking change. – StoryTeller - Unslander Monica Jul 20 '18 at 17:04
  • 3
    And I suggest you act a bit more mature. Taking a jab at my user handle, really? – StoryTeller - Unslander Monica Jul 20 '18 at 17:05
  • 1
    Seconding πάντα ῥεῖ, what's wrong with `std::max_element`? Since you seem to want `std::maximum` to use it with `accumulate` and `reduce`, `std::max_element` should be enough. – HolyBlackCat Jul 20 '18 at 17:09
  • 1
    @HolyBlackCat As I have elaborated in the post, I want to use it in my Fenwick tree (binary index tree) to compute prefix. Also, you may want to use it in `tbb::parallel_reduce` and other templated algorithms. – Walter Jul 20 '18 at 17:11
  • Most likely it was never asked for or felt it wasn't needed. `[](auto&& lhs, auto&& rhs){return std::max(lhs, rhs);}` will do what you need so there isn't a big need to add it to the standard. – NathanOliver Jul 20 '18 at 18:00
  • @NathanOliver *was never asked for* is not a design consideration. A lambda or custom functor can always be used, but that is not the same as a widely available functor that can be used to specialize a template. – Walter Jul 20 '18 at 23:57
  • "_Note that std::max is no option here_" Could you explain why? – curiousguy Jul 22 '18 at 04:18

1 Answers1

-1

Accumulate is a template function, which just tries to invoke the accumulator function, whether it is a Callable or a regular function (well, a regular function itself is Callable), so using this is completely valid

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

If your type was complicated (like anything that is not applicable to max), you can pass in a custom lambda expression (only C++ later than 11):

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

(replace int with your type, and replace return a > b ? a : b; with your wanted logic)

If your compiler refused to compile the first one and you are on something prior to C++11, you could try this line (unsafe)

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

std::ptr_fun converts ANY FUNCTION to a function object, so it could be used, see this reference http://www.cplusplus.com/reference/functional/ptr_fun/

Also there is a class called std::pointer_to_binary_function that could help you more. Here is its reference http://www.cplusplus.com/reference/functional/pointer_to_binary_function/

user9335240
  • 1,739
  • 1
  • 7
  • 14
  • It did compile in pre 2011 C++. – Walter Jul 20 '18 at 17:09
  • It did compile in pre and post 2011, while the lambda (second line) one doesn't compile on pre 2011, if you want something that compiles more sure on C++ pre 2011, try this line `cout << std::accumulate(v.begin(), v.end(), 0, std::ptr_fun(std::max));` – user9335240 Jul 20 '18 at 17:26
  • 2
    FWWI `ptr_fun` is deprecated in C++11 as removed in C++17 – NathanOliver Jul 20 '18 at 17:52
  • @NathanOliver I know, but it seems that the question poster wants something prior to C++11 – user9335240 Jul 20 '18 at 18:05
  • @user9335240 no, they don't. What makes you think that? The code in the post is clearly C++11 (`constexpr` for example) – Walter Jul 20 '18 at 23:51