The Comparison Functor inside the Binary Search in C++

Question

I'm working on a C++ program in which the pointer to class, an airlines class, is the object in a sorted vector. I want to determine if an airline is already a pointed-to object in the vector. First I apply the lower_bound with a lambda, it is successful. Then I implement the binary_search with same lambda, however it fails. The error message is below,

__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp&     __value_, _Compare __comp)
{
   __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
   return __first != __last && !__comp(__value_, *__first);
}
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/algorithm:4139:13: No matching function for call to object of type '(lambda at /Users/.../Desktop/Programming/C++/trial/trial/main.cpp:188:61)'

It looks the lambda doesn't work in the binary search. Could you help me figure out why it doesn't? Thanks a lot!

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class vector_test{
public:
    vector_test(string name_) : name(name_) {}
    const string get_name() const {return name;}
private:
    string name;
};

typedef vector<vector_test*> vector_container;

int main()
{
    vector_container test;
    string name = "Delta";
    vector_test *vt1 = new vector_test{"Sothwest"};
    vector_test *vt2 = new vector_test{"Delta"};
    vector_test *vt3 = new vector_test{"Hawaii"};
    vector_test *vt4 = new vector_test{"United"};
    test = {vt2, vt3, vt1, vt4};
    auto iter = lower_bound(test.begin(), test.end(), name, [](vector_test* ptr, string name) {
        return  ptr->get_name()< name;});
    if (iter != test.end() && (**iter).get_name() == name)
        cout << "It exits!\n";
    else
        cout << "It doesn't exit!\n"
    auto it = binary_search(test.begin(), test.end(), name, [](vector_test* ptr, string name) {
        return name < ptr->get_name();});
    if (it)
        cout << "It exits!\n";
    else
        cout << "It doesn't exit!\n"
 }

Answer 1

your call to lower_bound builds, but the one to binary_search doesn't. This is because the difference in the expected comparison functor.

For lower_bound, it is:

The type Type1 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type1. The type Type2 must be such that an object of type T can be implicitly converted to Type2. ​

For binary_search, it is:

The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly converted to both Type1 and Type2. ​

Your comparison functor matches the first requirement, but not the second.

---

Another thing you seem to have missed is that lower_bound returns an iterator, but binary_search returns merely a bool.

---

All things considering, you're better off using lower_bound, here. Simply use the resulting iterator to see if the element is logically in the sequence or not. You can use the accepted answer to this question for that.

Finally, as BeyelerStudios very correctly notes below in the comment, you should ensure that the content of your lambda is consistent with the ordering of your sequence.

Answer 2

Your problem is that binary_search expects a symmetric comparison function, where either LHS or RHS could be either the contents of the range or the value you are comparing it to.

This is a problem, but not a hard one. Here is a solution:

---

This is a type that takes a projection function F and a target type T.

It then implicitly takes anything that can be projected to T either implicitly or via F and wraps it up:

template<class F, class T>
struct projector_t {
  void const*ptr = nullptr;
  T(*func)( F const* f, void const* ptr) = nullptr;

  // an X that is implicitly convertible to a T:
  template<class X,
    class dX = std::decay_t<X>,
    std::enable_if_t<
      !std::is_same<dX, projector_t>{}
      && std::is_convertible<X const&, T>{}
    , int> = 0
  >
  projector_t( X const& x ):
    ptr(std::addressof(x)),
    func([](F const*, void const* ptr)->T{
      return *static_cast<X const*>(ptr);
    })
  {}

  // an X that is not implicitly convertible to a T:
  template<class X,
    class dX = std::decay_t<X>,
    std::enable_if_t<
      !std::is_same<dX, projector_t>{}
      && !std::is_convertible<X const&, T>{}
    , int> = 0
  >
  projector_t( X const& x ):
    ptr(std::addressof(x)),
    func([](F const* f, void const* ptr)->T{
      auto px = static_cast<X const*>(ptr);
      return (*f)(*px);
    })
  {}
  projector_t( projector_t&& )=default;
  projector_t( projector_t const& )=default;
  projector_t& operator=( projector_t&& )=default;
  projector_t& operator=( projector_t const& )=default;

  T get( F const* f ) const {
    return func( f, ptr );
  }
};

We can now write code that takes a projection and creates an ordering:

template<class F, class T>
struct projected_order_t {
  F f;
  bool operator()( projector_t<F, T> lhs, projector_t<F, T> rhs ) const {
    return lhs.get(std::addressof(f)) < rhs.get(std::addressof(f));
  }
};
template<class T, class F>
projected_order_t<F, T> projected_order( F fin ) {
  return {std::move(fin)};
}

projected_order<T>(lambda) takes a lambda. It returns an comparison function object. This object takes two parameters. Each of those parameters, if passed an object that can be converted to T, simply stores that conversion. If not, it tries to call the lambda on it to convert it to T. Then < is called on the result of this operation.

The "action" to get the T is stored in the member variable func during construction of projector_t, and the non-F data it operates on is stored in a void const* ptr member variable. To get the T out, the member function get takes an F const* and passes it and the ptr to func.

func either applies the F to the x, or it implicitly converts.

projetec_order_t provides an operator() that takes two projector_ts, and then calls their get passing in the F it stores. This extracts the T representing each argument. These T are then compared.

A nice thing about this technique is that we only have to provide the projection, not the comparison, and the comparision is derived reasonably smartly from the projection.

live example.

A simple improvement would be to permit it to chain to a different comparsion function, defaulting to std::less<T>, instead of calling <.

Answer 3

As I was doing testing with this in my IDE VS2015 and reading the compiler errors I noticed that Ami Tavory beat me to answering the question. So maybe this can provide some insight or clarity as to what is going on.

In your first search using lower_bound() it does compile as Ami stated and an iterator to your container is being returned from the search.

In your second search using binary_search() it does not compile, and as Ami stated it only returns a bool as if it was found or not. As for it not compiling here is the compiler error from Visual Studio 2015 CE

1>------ Build started: Project: LambdaTemplates, Configuration: Debug Win32 ------
1>  LambdaTemplates.cpp
1>c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): error C2664: 'bool main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>::operator ()(vector_test *,std::string) const': cannot convert argument 1 from 'const std::string' to 'vector_test *'
1>  c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): note: No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
1>  c:\users\skilz80\documents\visual studio 2015\projects\stackoverflowsolutions\lambdatemplates\lambdatemplates.cpp(46): note: see reference to function template instantiation 'bool std::binary_search<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,std::string,main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>>(_FwdIt,_FwdIt,const _Ty &,_Pr)' being compiled
1>          with
1>          [
1>              _FwdIt=std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,
1>              _Ty=std::string,
1>              _Pr=main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>
1>          ]
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

It says that it can not convert parameter 1 from const std::string to vector_test*

So what is happening here? Let's abstract away for a moment and lets temporarily write the lambda outside the search function call predicate parameter list. So this section of code would look like this:

auto myLambda = []( vector_test* ptr, std::string name ) {
    return name < ptr->get_name();
};

auto it = std::binary_search( test.begin(), test.end(), name, myLambda );

if (it)
    std::cout << "It is here\n";
else
    std::cout << "It is NOT here\n";

Now lets check out the compiler error:

1>------ Build started: Project: LambdaTemplates, Configuration: Debug Win32 ------
1>  stdafx.cpp
1>  LambdaTemplates.cpp
1>c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): error C2664: 'bool main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>::operator ()(vector_test *,std::string) const': cannot convert argument 1 from 'const std::string' to 'vector_test *'
1>  c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): note: No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
1>  c:\users\skilz80\documents\visual studio 2015\projects\stackoverflowsolutions\lambdatemplates\lambdatemplates.cpp(45): note: see reference to function template instantiation 'bool std::binary_search<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,std::string,main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>>(_FwdIt,_FwdIt,const _Ty &,_Pr)' being compiled
1>          with
1>          [
1>              _FwdIt=std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,
1>              _Ty=std::string,
1>              _Pr=main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>
1>          ]
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

We get a very similar error message. So lets comment out the line of code for calling the binary search and check the compiler error messages...

auto myLambda = []( vector_test* ptr, std::string name ) {
        return name < ptr->get_name();
    };

/*auto it = std::binary_search( test.begin(), test.end(), name, myLambda );

if (it)
    std::cout << "It is here\n";
else
    std::cout << "It is NOT here\n";
*/

And now we don't get any compiler errors. So the lambda itself is fine, however what is happening within the binary_search() function is this:

You are passing it 2 forward iterators begin and end a search term or value name which is a std::string. Your forward iterators are vectors of vector_test pointers. It isn't that your lambda is wrong so-to-speak, it is just that the function can not convert from an std::string being your search query data type into a vector that contains pointers to vector_test objects thus making this the wrong type of lambda to use, or the wrong search parameter. Your class of vector_test objects does not supply any constructors or conversion factors, or overloaded operators to convert to an std::string. Also as a side note when using the binary_search your container should be pre-sorted.