C++中二进制搜索中的比较函数

Question

我正在研究一个C++程序,其中指向class(航空类)的指针是排序向量中的对象.我想确定航空公司是否已经是向量中的指向对象.首先我使用lambda应用lower_bound,它是成功的.然后我用相同的lambda实现binary_search,但它失败了.错误信息如下,

__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)'

它看起来lambda在二进制搜索中不起作用.你能帮我搞清楚它为什么没有？非常感谢!

#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

您的问题是binary_search需要一个对称比较函数，其中 LHS 或 RHS 可以是范围的内容，也可以是您要与之比较的值。

这是一个问题，但并不难。这是一个解决方案：

这是一种采用投影函数F和目标类型的类型T。

然后，它隐式地获取任何可以T隐式或通过方式投影的内容F并将其包装起来：

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 );
  }
};

我们现在可以编写接受投影并创建排序的代码：

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)需要一个 lambda。它返回一个比较函数对象。该对象有两个参数。这些参数中的每一个，如果传递一个可以转换为 的对象T，则仅存储该转换。如果不是，它会尝试调用lambda它以将其转换为T. 然后<调用该操作的结果。

构造 时，获取 的“动作”存储T在成员变量中，而其操作的非数据则存储在成员变量中。为了得到out，成员函数接受 an并将其传递给to 。funcprojector_tFvoid const* ptrTgetF const*ptrfunc

func要么将 应用于F，x要么隐式转换。

projetec_order_t提供一个operator()需要两个projector_ts 的 an ，然后get在 it 存储中调用它们的传递F。这会提取T代表每个参数的参数。然后对这些T进行比较。

这种技术的一个好处是，我们只需要提供投影，而不是比较，并且比较是从投影中相当智能地导出的。

活生生的例子。

一个简单的改进是允许它链接到不同的比较函数，默认为std::less<T>，而不是调用<。