binary_search, find_if and <functional>

Question

std::find_if takes a predicate in one of it's overloaded function. Binders make it possible to write EqualityComparators for user-defined types and use them either for dynamic comparison or static comparison.

In contrast the binary search functions of the standard library take a comparator and a const T& to the value that should be used for comparison. This feels inconsistent to me and could possibly more inefficient as the comparator has to be called with both arguments every time instead of having the constant argument bound to it. While it could be possible to implement std::binary_search in a way to use std::bind this would require all comparators to inherit from std::binary_function. Most code I've seen doesn't do that.

Is there a possible benefit from letting comparators inherit from std::binary_function when using it with algorithms that take a const T& as a value instead of letting me use the binders? Is there a reason for not providing predicate overloads in those functions?

Answer 1

A single-argument predicate version of std::binary_search wouldn't be able to complete in O(log n) time.

Consider the old game "guess the letter I'm thinking of". You could ask: "Is it A?" "Is it B?".. and so on until you reached the letter. That's a linear, or O(n), algorithm. But smarter would be to ask "Is it before M?" "Is it before G?" "Is it before I?" and so on until you get to the letter in question. That's a logarithmic, or O(log n), algorithm.

This is what std::binary_search does, and to do this in needs to be able to distinguish three conditions:

• Candidate C is the searched-for item X
• Candidate C is greater than X
• Candidate C is less than X

A one-argument predicate P(x) says only "x has property P" or "x doesn't have property P". You can't get three results from this boolean function.

A comparator (say, <) lets you get three results by calculating C < X and also X < C. Then you have three possibilities:

• !(C < X) && !(X < C) C is equal to X
• C < X && !(X < C) C is less than X
• !(C < X) && X < C C is greater than X

Note that both X and C get bound to both parameters of < at different times, which is why you can't just bind X to one argument of < and use that.

Edit: thanks to jpalecek for reminding me binary_search uses <, not <=. Edit edit: thanks to Rob Kennedy for clarification.

Answer 2

This is a misunderstanding of the Functor concept in C++.

It has nothing to do with inheritance. The property that makes an object a functor (eligible for passing to any of the algorithms) is validity of the expression object(x) or object(x, y), respectively, regardless whether it is a function pointer or an object with overloaded function call operator. Definitely not inheritance from anything. The same applies for std::bind.

The use of binary functors as comparators comes from the fact that comparators (eg. std::less) are binary functors and it's good to be able to use them directly.

IMHO there would be no gain in providing or using the predicate version you propose (after all, it takes just passing one reference). There would be no (performance) gain in using binders, because it does the same thing as the algorithm (bind would pass the extra argument in lieu of the algorithm).

Answer 3

They are completely different algorithms: find_if looks linearly for the first item for which the predicate is true, binary_search takes advantage that the range is sorted to test in logarithmic time if a given value is in it.

The predicate for binary_search specifies the function according to which the range is ordered (you'd most likely want to use the same predicate you used for sorting it).

You can't take advantage of the sortedness to search for a value satisfying some completely unrelated predicate (you'd have to use find_if anyway). Note however, that with a sorted range you can do more than just test for existence with lower_bound, upper_bound and equal_range.

---

The question, what is the purpose of std::binary_function is an interesting one.

All it does is provide typedefs for result_type, first_argument_type and second_argument_type. These would allow the users, given a functor as a template argument, to find out and use these types, e.g

template <class T, class BinaryFunction>
void foo(const T& a, const T& b, BinaryFunction f)
{
     //declare a variable to store the result of the function call
     typename BinaryFunction::result_type result = f(a, b);
     //...
 }

However, I think the only place where they are used in the standard library is creating other functor wrappers like bind1st, bind2nd, not1, not2. (If they were used for other purposes, people would yell at you any time you used a function as a functor since it would be an unportable thing to do.)

For example, binary_negate might be implemented as (GCC):

template<typename _Predicate>
class binary_negate
: public binary_function<typename _Predicate::first_argument_type,
             typename _Predicate::second_argument_type, bool>
{
protected:
  _Predicate _M_pred;

public:
  explicit
  binary_negate(const _Predicate& __x) : _M_pred(__x) { }

  bool
  operator()(const typename _Predicate::first_argument_type& __x,
     const typename _Predicate::second_argument_type& __y) const
  { return !_M_pred(__x, __y); }
};

Of course, operator() could perhaps just be a template, in which case those typedefs would be unnecessary (any downsides?). There are probably also metaprogramming techniques to find out what the argument types are without requiring the user to typedef them explicitly. I suppose it would somewhat get into the way with the power that C++0x gives - e.g when I'd like to implement a negator for a function of any arity with variadic templates...

(IMO the C++98 functors are a bit too inflexible and primitive compared for example to std::tr1::bind and std::tr1::mem_fn, but probably at the time compiler support for metaprogramming techniques required to make those work was not that good, and perhaps the techniques were still being discovered.)