5

クラスへのポインタである航空会社クラスがソートされたベクトルのオブジェクトである C++ プログラムに取り組んでいます。航空会社が既にベクトル内のポイント先オブジェクトであるかどうかを判断したいと考えています。まず、ラムダで lower_bound を適用すると、成功します。次に、同じラムダで 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)'

二分探索でラムダが機能しないようです。なぜそれができないのかを理解するのを手伝ってもらえますか? どうもありがとう！

#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 の両方に暗黙的に変換できるようなものでなければなりません。』

比較ファンクターは最初の要件に一致しますが、2 番目の要件には一致しません。

あなたが見逃しているように見えるもう1つのことlower_boundは、イテレータを返しますがbinary_search、bool.

すべてを考慮するとlower_bound、ここでは , を使用する方がよいでしょう。結果の反復子を使用して、要素が論理的にシーケンス内にあるかどうかを確認します。そのために、この質問に対する受け入れられた回答を使用できます。

最後に、BeyelerStudios が以下のコメントで非常に正確に指摘しているように、ラムダの内容がシーケンスの順序と一致していることを確認する必要があります。

于 2016-09-09T06:28:20.763 に答える
2

あなたの問題は、binary_searchLHSまたは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)ラムダを取ります。比較関数オブジェクトを返します。このオブジェクトは 2 つのパラメータを取ります。これらの各パラメーターは、に変換できるオブジェクトを渡された場合、Tその変換を単純に格納します。そうでない場合は、 を呼び出してlambdaに変換しようとしますT。次に<、この操作の結果に対して呼び出されます。

を取得するための「アクション」は、の構築中にTメンバー変数に格納され、操作対象の非データはメンバー変数に格納されます。outを取得するために、メンバー関数は を受け取り、それとto を渡します。funcprojector_tFvoid const* ptrTgetF const*ptrfunc

funcを に適用するかF、x暗黙的に変換します。

projetec_order_tは、operator()2 つの を取り、 it ストアでそれらの受け渡しをprojector_t呼び出すan を提供します。これにより、各引数を表す が抽出されます。次に、これらが比較されます。getFTT

この手法の良い点は、比較ではなく投影を提供するだけでよく、比較は投影から合理的にスマートに導出されることです。

実例。

std::less<T>簡単な改善は、 を呼び出す代わりに、デフォルトで を別の比較関数にチェーンできるようにすること<です。

于 2016-09-09T14:11:50.740 に答える
1

IDE VS2015 でこれを使用してテストを行っていて、コンパイラ エラーを読んでいると、Ami Tavory が私を打ち負かして質問に答えていることに気付きました。したがって、これにより、何が起こっているかについての洞察や明確さが得られる可能性があります。

それを使用した最初の検索lower_bound()では、Amiが述べたようにコンパイルされ、コンテナへのイテレータが検索から返されます。

それを使用した2回目の検索binary_search()ではコンパイルされず、Amiが述べたように、見つかったかどうかのようにboolのみを返します。ここでコンパイルしないのは、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 ==========

const std::stringパラメータ1をからに変換できないと言っていますvector_test*

では、ここで何が起こっているのでしょうか? ちょっと抽象化して、ラムダを検索関数呼び出しの述語パラメーター リストの外に一時的に書きましょう。したがって、コードのこのセクションは次のようになります。

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

これで、コンパイラ エラーは発生しなくなりました。binary_search()したがって、ラムダ自体は問題ありませんが、関数内で起こっていることは次のとおりです。

2 つの前方反復子beginとend、検索語または値nameであるstd::string. 前方反復子は のベクトルですvector_test pointers。いわばラムダが間違っているわけではありません。関数が検索クエリのデータ型からオブジェクトstd::stringへのポインターを含むベクターに変換できないため、使用するラムダの型が間違っているだけです。 vector_test、または間違った検索パラメータです。オブジェクトのクラスはvector_test、std::string に変換するためのコンストラクターや変換係数、またはオーバーロードされた演算子を提供しません。また、コンテナを使用する際の補足として、binary_search事前に分類する必要があります。

于 2016-09-09T07:13:45.520 に答える