Funkcja porównawcza wewnątrz wyszukiwania binarnego w C++

Question

Pracuję nad programem C++, w którym wskaźnik do klasy, klasa linii lotniczych, jest obiektem w posortowanym wektorze. Chcę ustalić, czy linia lotnicza jest już obiektem wskazanym w wektorze. Najpierw stosuję lower_bound z lambda, to się udaje. Następnie zaimplementuję metodę binary_search z tą samą wartością lambda, ale nie działa. Komunikat o błędzie jest poniżej:

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

Wygląda na to, że lambda nie działa w wyszukiwaniu binarnym. Czy możesz mi pomóc dowiedzieć się, dlaczego tak nie jest? Wielkie dzięki!

#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

Twój problem polega na tym, że binary_search oczekuje symetrycznej funkcji porównywania, w której LHS lub RHS może być zawartością zakresu lub wartością, z którą porównujesz.

To jest problem, ale nie trudny. O to rozwiązanie:

---

to jest typem, który wykonuje funkcje projekcyjne F i typu docelowej T.

Następnie pośrednio bierze wszystko, co może być rzutowany na T albo pośrednio lub poprzez F i owija go:

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

Możemy teraz napisać kod, który zaczyna występ i tworzy Kolejność:

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) ma lambdę. Zwraca obiekt funkcji porównania. Ten obiekt przyjmuje dwa parametry. Każdy z tych parametrów, jeśli został przekazany obiektowi, który można przekonwertować na T, po prostu przechowuje tę konwersję. Jeśli nie, próbuje wywołać na nim lambda, aby przekonwertować go na T. Następnie wywoływana jest nazwa < w wyniku tej operacji.

„akcji”, aby uzyskać T jest przechowywany w zmiennej składowej func podczas budowy projector_t, a nie- F danych działa na przechowywany jest w zmiennej void const* ptr członkowskim. Aby uzyskać T, funkcja składowa get pobiera F const* i przekazuje ją oraz ptr do func.

func stosuje F do x lub domyślnie konwertuje.

projetec_order_t dostarcza operator() że trwa dwa projector_t s, a następnie wywołuje swoje get przechodząc w F sklepach niej. To wyodrębnia z każdego argumentu T. Te T są następnie porównywane.

Przyjemną rzeczą w tej technice jest to, że musimy tylko dostarczyć projekcję, a nie porównanie, a porównanie uzyskuje się rozsądnie elegancko z projekcji.

live example.

Prostą poprawką byłoby zezwolenie jej na połączenie z inną funkcją porównywania, domyślnie na std::less<T>, zamiast na wywołanie <.

Answer 2

wezwanie do lower_bound buduje, ale jeden do binary_search nie. Jest tak, ponieważ różnica w oczekiwanym funcie porównawczym.

Dla lower_bound, to 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. ​

Dla binary_search, to 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. ​

Twoje porównanie funktor mecze pierwszego wymogu, ale nie drugi.

---

Inną rzeczą, którą wydaje się, że jest to, że brakowało lower_bound zwraca iterator, ale binary_search powraca jedynie bool.

---

Biorąc wszystko pod uwagę, lepiej skorzystać z lower_bound, tutaj. Po prostu użyj wynikowego iteratora, aby zobaczyć, czy element jest logiczny w sekwencji, czy nie. Możesz użyć do tego zaakceptowanej odpowiedzi pod numerem this question.

Wreszcie, jak BeyelerStudios bardzo poprawnie zauważa w komentarzu poniżej, należy upewnić się, że treść zawartości Twojej lambda jest zgodna z kolejnością sekwencji.

Answer 3

W trakcie testowania tego w moim IDE VS2015 i odczytywaniu błędów kompilatora zauważyłem, że Ami Tavory pobił mnie, odpowiadając na pytanie. Być może może to zapewnić pewien wgląd lub jasność co do tego, co się dzieje.

Podczas pierwszego wyszukiwania przy użyciu lower_bound() kompiluje się zgodnie z informacją Ami, a wynik wyszukiwania jest zwracany do kontenera.

W twoim drugim wyszukiwaniu przy użyciu binary_search() nie kompiluje się, a ponieważ Ami stwierdziła, że ​​zwraca tylko bool, jak gdyby został znaleziony lub nie. Jak na to nie kompilacji tu jest błąd kompilator z 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 ========== 

on mówi, że nie można konwertować parametru 1 z const std::string do vector_test*

więc to, co się tu dzieje? Oddalmy się na chwilę i tymczasowo zapiszmy lambdę poza listą parametrów predykatu funkcji wyszukiwania.Tak więc ta część kodu wyglądałby następująco:

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

Teraz pozwala sprawdzić błąd kompilatora:

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

Dostajemy bardzo podobny komunikat o błędzie. Więc pozwala wypowiedzieć się wiersz kodu do wywoływania przeszukiwanie binarne i sprawdź komunikaty o błędach kompilatora ...

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

A teraz nie mamy żadnych błędów kompilatora. Więc sama lambda jest w porządku, jednak to, co dzieje się wewnątrz funkcji binary_search() to:

Jesteś przepuszczenie 2 naprzód iteratory begin i end szukaną frazę lub wartość name który jest std::string. Twoje forwardujące iteratory są wektorami vector_test pointers. To nie jest tak, że twoja lambda jest niewłaściwa w rozmowie, po prostu ta funkcja nie może przekształcić się z std::string będącego typem twoich zapytań w wektor zawierający wskaźniki do obiektów vector_test, czyniąc to nieprawidłowym typem lambda. do użycia lub nieprawidłowy parametr wyszukiwania. Twoja klasa obiektów vector_test nie dostarcza żadnych konstruktorów ani współczynników konwersji, ani przeciążonych operatorów do konwersji na std :: string. Również jako notatka przy korzystaniu z binary_search Twój pojemnik powinien zostać wstępnie posortowany.