सी ++

Question

में बाइनरी खोज के अंदर तुलनात्मक फ़ंक्शन मैं एक सी ++ प्रोग्राम पर काम कर रहा हूं जिसमें कक्षा के सूचक, एक एयरलाइन वर्ग, सॉर्ट किए गए वेक्टर में ऑब्जेक्ट है। मैं यह निर्धारित करना चाहता हूं कि क्या एक एयरलाइन पहले से ही वेक्टर में एक ऑब्जेक्ट-ऑब्जेक्ट है। सबसे पहले मैं लम्बाडा के साथ निचला_बाउंड लागू करता हूं, यह सफल होता है। फिर मैं उसी लैम्ब्डा के साथ 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 एक सममित तुलना फ़ंक्शन की अपेक्षा करता है, जहां या तो एलएचएस या आरएचएस या तो उस सीमा या उस मूल्य की सामग्री हो सकती है, जिसका आप इसकी तुलना कर रहे हैं।

यह एक समस्या है, लेकिन मुश्किल नहीं है।

---

यह एक प्रकार है कि एक प्रक्षेपण समारोह F और एक लक्ष्य प्रकार T लेता है: यहाँ एक समाधान है।

यह तो परोक्ष अनुमान से या F के माध्यम से कुछ भी है कि T का अनुमान किया जा सकता है लेता है और यह ऊपर लपेटता:

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

:

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

अब हम कोड है कि एक प्रक्षेपण लेता है और एक आदेश बनाता है लिख सकते हैं

projected_order<T>(lambda) एक लैम्ब्डा लेता है। यह एक तुलना समारोह वस्तु देता है। यह वस्तु दो पैरामीटर लेती है। उन पैरामीटर में से प्रत्येक, यदि किसी ऑब्जेक्ट को पास किया गया है जिसे T में परिवर्तित किया जा सकता है, तो बस उस रूपांतरण को संग्रहीत करता है। यदि नहीं, तो इसे T में बदलने के लिए lambda पर कॉल करने का प्रयास किया जाता है। फिर < इस ऑपरेशन के परिणामस्वरूप बुलाया जाता है।

"कार्रवाई" T पाने के लिए projector_t के निर्माण के दौरान सदस्य चर func में संग्रहीत है, और गैर F डेटा उस पर संचालित एक void const* ptr सदस्य चर में संग्रहित है। T प्राप्त करने के लिए, सदस्य फ़ंक्शन getF const* लेता है और इसे ptr से func पर भेजता है।

func या तो पर x पर लागू होता है, या यह स्पष्ट रूप से परिवर्तित हो जाता है।

projetec_order_t एक operator() कि दो projector_t रों लेता है प्रदान करता है, और फिर F यह दुकानों में गुजर उनके get कहता है। यह 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. ​

आपका तुलना functor पहली आवश्यकता है, लेकिन नहीं दूसरे से मेल खाता है।

---

एक और बात आप चूक गए लगते हैं कि lower_bound पुनरावर्तक देता है, लेकिन binary_search रिटर्न महज एक bool।

---

सभी चीजों पर विचार करते हुए, आप यहां lower_bound का उपयोग कर बेहतर हैं। यह देखने के लिए कि तत्व अनुक्रम में तर्कसंगत है या नहीं, परिणामी इटरेटर का उपयोग करें। आप स्वीकृत उत्तर का उपयोग this question पर कर सकते हैं।

अंत में, जैसा कि बेलेर स्टुडियो ने टिप्पणी में नीचे बहुत सही तरीके से नोट किया है, आपको यह सुनिश्चित करना चाहिए कि सामग्री आपके लैम्ब्डा के क्रम में आपके अनुक्रम के क्रम के अनुरूप है।

Answer 3

जैसा कि मैं अपने आईडीई वीएस2015 में इसके साथ परीक्षण कर रहा था और संकलक त्रुटियों को पढ़ रहा था, मैंने देखा कि अमी टैवरी ने मुझे इस सवाल का जवाब देने के लिए हराया। तो हो सकता है कि यह कुछ अंतर्दृष्टि या स्पष्टता प्रदान कर सके कि क्या हो रहा है।

lower_bound() का उपयोग करके अपनी पहली खोज में यह एमी के रूप में संकलित करता है और आपके कंटेनर को एक इटरेटर खोज से वापस किया जा रहा है।

binary_search() का उपयोग करके आपकी दूसरी खोज में यह संकलित नहीं होता है, और जैसा कि अमी ने कहा है कि यह केवल एक बूल देता है जैसे कि यह पाया गया था या नहीं। इसे यहाँ संकलन नहीं के रूप में दृश्य स्टूडियो 2015 सीई से संकलक त्रुटि है

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

इसमें कहा गया है कि यह vector_test*

तो करने के लिए const std::string से पैरामीटर 1 परिवर्तित नहीं कर सकते कि यहाँ क्या हो रहा है? आइए एक पल के लिए अमूर्त हो जाएं और खोज फ़ंक्शन कॉल पूर्वानुमान पैरामीटर सूची के बाहर अस्थायी रूप से लैम्ब्डा लिखने दें।तो कोड के इस खंड इस प्रकार दिखाई देगा:

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 आगे Iterators begin और end कोई खोज शब्द या मूल्य name जो एक std::string है। आपके आगे इटरेटर vector_test pointers के वेक्टर हैं। ऐसा नहीं है कि आपका लैम्ब्डा इतना बोलने में गलत है, यह सिर्फ यह है कि फ़ंक्शन std::string से आपके वेक्टर क्वेरी डेटा प्रकार को वेक्टर में परिवर्तित नहीं कर सकता है जिसमें पॉइंटर्स vector_test ऑब्जेक्ट्स हैं, इस प्रकार यह गलत प्रकार का लैम्ब्डा बनाते हैं उपयोग करने के लिए, या गलत खोज पैरामीटर। vector_test ऑब्जेक्ट्स की आपकी कक्षा किसी भी कन्स्ट्रक्टर या रूपांतरण कारकों, या अधिभारित ऑपरेटरों को एक std :: स्ट्रिंग में कनवर्ट करने की आपूर्ति नहीं करती है। binary_search का उपयोग करते समय एक साइड नोट के रूप में भी आपका कंटेनर पूर्व-क्रमबद्ध होना चाहिए।