5

我正在开发一个 C++ 程序，其中指向类（航空公司类）的指针是排序向量中的对象。我想确定航空公司是否已经是向量中的指向对象。首先，我将 lower_bound 与 lambda 一起应用，它是成功的。然后我用相同的 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"
 }
4

3 回答 3

3

您对lower_bound构建的调用，但对构建的调用binary_search没有。这是因为预期的比较函子不同。

对于lower_bound，它是：

Type1 类型必须使得 ForwardIt 类型的对象可以被取消引用，然后隐式转换为 Type1。类型 Type2 必须使得类型 T 的对象可以隐式转换为 Type2。​​​

对于binary_search，它是：

类型 Type1 和 Type2 必须使得 T 类型的对象可以隐式转换为 Type1 和 Type2，并且 ForwardIt 类型的对象可以取消引用，然后隐式转换为 Type1 和 Type2。​​​

您的比较函子符合第一个要求，但不符合第二个要求。

您似乎错过的另一件事是lower_bound返回一个迭代器，但binary_search只返回一个bool.

考虑到所有事情，你最好在lower_bound这里使用 , 。只需使用生成的迭代器来查看元素是否在逻辑上在序列中。您可以为此问题使用已接受的答案。

最后，正如 BeyelerStudios 在下面的评论中非常正确地指出的那样，您应该确保 lambda 的内容与序列的顺序一致。

于 2016-09-09T06:28:20.763 回答
2

您的问题是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存储在成员变量中，它所操作的非数据存储在成员变量中。为了退出，成员函数接受 an并将其传递给to 。funcprojector_tFvoid const* ptrTgetF const*ptrfunc

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

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

这种技术的一个好处是我们只需要提供投影，而不是比较，并且比较是从投影中合理巧妙地得出的。

活生生的例子。

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

于 2016-09-09T14:11:50.740 回答
1

当我在我的 IDE VS2015 中对此进行测试并阅读编译器错误时，我注意到 Ami Tavory 在回答问题时击败了我。因此，也许这可以为正在发生的事情提供一些洞察力或清晰度。

在您使用它的第一次搜索中lower_bound()，它确实按照 Ami 所述进行编译，并且从搜索中返回了一个指向您容器的迭代器。

在您使用它的第二次搜索中binary_search()，它不会编译，并且正如 Ami 所说，它只返回一个布尔值，就好像它是否被发现一样。至于它没有在这里编译是来自 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 ==========

它说它不能将参数 1 从转换const std::string为vector_test*

那么这里发生了什么？让我们暂时抽象一下，让我们暂时将 lambda 写在搜索函数调用谓词参数列表之外。所以这部分代码看起来像这样：

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";

现在让我们检查一下编译器错误：

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 ==========

我们得到一个非常相似的错误信息。因此，让我们注释掉调用二进制搜索的代码行并检查编译器错误消息...

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";
*/

现在我们没有得到任何编译器错误。所以 lambda 本身很好，但是binary_search()函数中发生的事情是这样的：

您正在向它传递 2 个前向迭代器begin和end一个搜索词或值name，即std::string. 您的前向迭代器是 的向量vector_test pointers。这并不是说您的 lambda 是错误的，只是该函数无法从std::string您的搜索查询数据类型转换为包含指向vector_test对象的指针的向量，从而使该类型成为错误的 lambda 使用，或错误的搜索参数。您的vector_test对象类不提供任何构造函数或转换因子，或重载运算符以转换为 std::string。另外，在使用binary_search容器时应预先分类。

于 2016-09-09T07:13:45.520 回答