Сравнительный функтор внутри двоичного поиска в C++

Question

Я работаю над программой на 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" 
} 

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) принимает лямбда. Он возвращает объект функции сравнения. Этот объект принимает два параметра. Каждый из этих параметров, если передан объект, который может быть преобразован в T, просто сохраняет это преобразование. Если нет, он пытается вызвать lambda, чтобы преобразовать его в T. Затем на результат этой операции вызывается <.

«действие», чтобы получить T хранится в переменной-члене func при строительстве projector_t и не- F данных он работает на хранится в переменной в void const* ptr члена. Чтобы получить T, функция-член get принимает F const* и передает ее, а ptr - func.

func либо применяется F к x, либо неявно преобразуется.

projetec_order_t обеспечивает operator(), которая принимает два projector_t с, а затем называет их get прохождения в F он хранит. Это извлекает T, представляющий каждый аргумент. Эти T затем сравнивают.

Приятная вещь в этом методе заключается в том, что нам нужно предоставить только проецирование, а не сравнение, и сравнение получается достаточно разумно из проекции.

live example.

Простым улучшением было бы привести его в цепочку к другой функции сортировки, по умолчанию std::less<T>, вместо того, чтобы звонить <.

Answer 2

ваш призыв к lower_bound строит, но один в binary_search нет. Это связано с тем, что разница в ожидаемом функторе сравнения.

Для lower_bound, это 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. ​

Для binary_search, это 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. ​

Ваш функтор сравнения соответствует первому требованию, но не второй.

---

Еще одна вещь, вы, кажется, пропустил, что lower_bound возвращает итератор, но binary_search возвращает лишь bool.

---

Все вещи, учитывая, что вы лучше использовать lower_bound, здесь. Просто используйте полученный итератор, чтобы увидеть, является ли элемент логически в последовательности или нет. Вы можете использовать принятый ответ на this question.

Наконец, как BeyelerStudios очень правильно отмечает ниже в комментарии, вы должны убедиться, что контент вашей лямбды соответствует порядку вашей последовательности.

Answer 3

Как я уже тестировал это в своей IDE VS2015 и читая ошибки компилятора, я заметил, что Ами Тавори избил меня, отвечая на вопрос. Поэтому, возможно, это может дать некоторую информацию или ясность относительно того, что происходит.

В вашем первом поиске, используя lower_bound(), он компилируется, как указано Ами, и итератор в ваш контейнер возвращается из поиска.

В вашем втором поиске с использованием binary_search() он не компилируется, и, как заявила Ами, он возвращает только 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 ========== 

Он говорит, что он не может преобразовать параметр 1 из const std::string в 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 ваш контейнер должен быть предварительно отсортирован.