तुलनात्मक फ़ंक्शन

Question

std :: cd+ प्रकार का libcxx (C++ मानक लाइब्रेरी का llvm संस्करण) समान तत्व के साथ तुलना अनुमानित करता है यानी तुलनात्मक विक्टर के तर्क दोनों को संदर्भित करते हैं अनुक्रमित करने के क्रम में स्थिति। बिंदु को चित्रित करने के लिए एक संक्षिप्त उदाहरण।

$ cat a.cc 
#include <algorithm> 
#include <vector> 
#include <cassert> 

int main(int argc, char** argv) { 
    int size = 100; 
    std::vector<int> v(size); 

    // Elements in v are unique. 
    for (int i = 0; i < size; ++i) 
    v[i] = i; 

    std::sort(v.begin(), v.end(), 
      [&](int x, int y) { assert(x != y); return x < y; }); 

    return 0; 
} 

$ clang++ -std=c++11 -stdlib=libc++ a.cc -o a.out 
$ ./a.out 
a.out: a.cc:14: auto main(int, char **)::(anonymous class)::operator()(int, int) const: Assertion `x != y' failed. 
./go.sh: line 5: 19447 Aborted     (core dumped) ./a.out 

libstdC++ के साथ ठीक काम करता है।

$ clang++ -std=c++11 -stdlib=libstdc++ a.cc -o a.out 
$ ./a.out 

क्या यह समान तत्व के साथ तुलना फ़ंक्शन को कॉल करना ठीक है। यह अनावश्यक नहीं है।

Answer 1

मैं इस प्रश्न पर कुछ अधिकारियों के साथ बात कर सकता हूं क्योंकि मैं यह कोड लिखता हूं।

https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm#L3994-L3995

के रूप में लिंक (गलत लाइन के लिए बिंदु) जाने के लिए बासी के रूप में समय पर चला जाता है की संभावना है, मैं भी बोली होगी:

यहाँ तुलना जो अपने उदाहरण में जोर देते हुए किया जाता है यहाँ कोड:

  // __m still guards upward moving __i 
      while (__comp(*__i, *__m)) 
       ++__i; 

यह इटरेटर __i अनुक्रम के अंत बंद चल रहा है के रूप में यह वृद्धि की जाती है के लिए कोई चेक न होने के कारण एक "असुरक्षित" लूप के रूप में जाना जाता है। इस कारण का कारण यह है क्योंकि इस एल्गोरिदम का एक आविष्कार यह है कि इस बिंदु पर यह ज्ञात है कि __i <= __m (जो इस उद्धरण के ऊपर एक टिप्पणी में 3 पंक्तियों में भी है)।

आप इस बोली से ऊपर कोड को देखें, तो आप इन टिप्पणियों देखेंगे:

// The search going up is known to be guarded but the search coming down isn't. 
    // Prime the downward search with a guard. 

तो इससे पहले कि हम इस बात पर आते हैं, अनुक्रम नीचे एक सुरक्षित खोज किया जाता है। यही कारण है कि, इस परीक्षण है:

if (__i == --__j) 

इस परीक्षण के बाद कम गार्ड पाता है, एल्गोरिथ्म तो, निगरानी रहित छोरों जो यात्रा में केवल एक परीक्षण के लिए कूदता है जबकि अन्यथा यात्रा प्रति दो टेस्ट (पर एक परीक्षण किया जाएगा इटरेटर और इटरेटर के मानदंडित मूल्य पर एक परीक्षण)।

"अनगिनत लूप" का उपयोग एक तत्व का तुलना स्वयं के साथ किया जा रहा है। विकास के दौरान मैंने मापा कि लूप में एक अतिरिक्त तुलना की लागत लूप में प्रति पुनरावृत्ति के दो तुलनाओं की तुलना में एक बेहतर सौदा था।

बेशक यह एक इंजीनियरिंग ट्रेडऑफ है। यदि तुलनात्मक कार्यकर्ता स्वयं की तुलना करने की लागत की तुलना में तुलनात्मक रूप से महंगा हो गया है, तो कोई भी एक अलग निष्कर्ष पर आ सकता है।

यह उत्तर rici's answer के साथ पूरी तरह से संगत है जो भी सही है (और मैंने इसे ऊपर उठाया है)।मैंने अपनी आवाज़ को जोड़ा क्योंकि मैं "संभावित रूप से" छोड़ सकता हूं और एल्गोरिदम में कोड की विशिष्ट पंक्तियों को इंगित करता हूं।

Answer 2

संभावित रूप से, मानक-लाइब्रेरी लेखकों की राय में, यह एक ऐसा परीक्षण करना तेज़ है जो लगातार बराबर सूचकांक के साथ-साथ तत्वों की तुलना करने के लिए झूठी वापसी की गारंटी देता है। यह इस बारे में आ सकता है क्योंकि पिवट तत्व को लूप सेंटीनेल के रूप में उपयोग किया जाता है।

इस तरह से तुलनात्मक फ़ंक्शन को इस तरह से कॉल करने की अनुमति है, और आपके कोड में assert की अनुमति नहीं है।