1

The C++ standard library function std::min_element() accepts a function object as is last argument, and that object's return type is bool. Why is it not int?

With true or false, we have only two options: < or >, but what if two entries are the same i.e. ==?

In C, this situation is handled by choosing the return type as int. But this is not done for std::min_element() in C++.

What is the reason for this?

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Rushikesh
  • 163
  • 8

2 Answers2

7

What would you gain from that information? The function is supposed to return the smallest element (hence the name min_element). It doesn't need to care about equality, what would you gain from it in the end result? A boolean value is sufficient to tell whether one element is smaller than another. How you handle equality is up to your implementation of that callable.

In the words of cppreference:

bool cmp(const Type1 &a, const Type2 &b);

comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if a is less than b.

Timo
  • 9,269
  • 2
  • 28
  • 58
3

I'll point out that this is consistent with other parts of std, such as sort and map, which all order things based on a functor which satisfies Compare. The same question can be extended to all these things.

What is the reason?

The original author, and the standards committee, thought that it was a more natural way of expressing ordering.

There are some problems with using three way compare via int.

  • int has more than three values. You therefore have to do further arithmetic on the return value.
  • It's easier to fall into undefined behaviour
struct three_way_compare
{
     int operator()(int lhs, int rhs) { return lhs - rhs; }
     // Undefined behaviour when rhs is a large positive value and lhs is a large negative value
}

You can synthesize three way comparison by calling your functor twice. The reference defines the requirements using

equiv(a, b), an expression equivalent to !comp(a, b) && !comp(b, a)

Note that for C++20, three way comparison is being added to the language with operator <=>. I'm not sure if existing algorithms are being changed to utilise it, when available.

Caleth
  • 52,200
  • 2
  • 44
  • 75
  • Unless you have `NAN` floating point values in your container, in which case **all** comparisons return `false`. – Khouri Giordano May 30 '19 at 13:28
  • @KhouriGiordano Yes, it's undefined to try to sort NAN. – Caleth May 30 '19 at 13:36
  • Thanks for explaining it is detail. I think I am more interested in knowing how the algorithm implementation determines whether two entries are of equal values based on true/false output from the compare function. Suppose I decide to write implementation of compare function as follows: bool compare(int & val1, int & val2) { return (val1 < val2) } With such compare function, can the algorithm know whether two entries are having same value by using !comp(a, b) && !comp(b, a) ? It evaluates to false with above compare function. – Rushikesh May 31 '19 at 11:20
  • 1
    @Rushikesh `comp` is whatever comparison you provide. For the case of `<`, it treats as equivalent any `a` and `b` such that `!(a < b) && !(b < a)` is true. That need not the same as `a == b` – Caleth May 31 '19 at 11:33