समकक्ष श्रेणियों के लिए एसटीएल एल्गोरिदम

Question

परिभाषा के अनुसार, std :: बराबर एल्गोरिदम केवल एक 'अंतिम' इटेटरेटर लेता है। स्टैकओवरफ्लो पर कई पोस्ट इंगित करती हैं कि दो श्रेणियों के बीच समानता करने के लिए, सबसे पहले यह जांचना चाहिए कि श्रेणियों के पास std :: बराबर कॉल करने के अलावा समान आकार है। यदि यादृच्छिक अभिगम इटरेटर उपलब्ध हैं, तो यह कोई भी सामग्री ओवरहेड नहीं जोड़ता है। हालांकि, ऐसा लगता है कि यादृच्छिक अभिगम इटरेटर्स के बिना, पहले कोड खंड, केवल मौजूदा एसटीएल एल्गोरिदम के साथ लागू किया गया है, दूसरे कोड खंड से धीमा होगा, जो एक कस्टम "समकक्ष" एल्गोरिदम (एसटीएल का हिस्सा नहीं) का प्रतिनिधित्व करता है। मेरा सवाल यह है कि मौजूदा एसटीएल एल्गोरिदम का उपयोग करके कोडित किसी भी एल्गोरिदम की तुलना में 2 अधिक कुशल है? यदि हां, तो यह एल्गोरिदम एसटीएल का हिस्सा क्यों नहीं है?

टुकड़ा 1:

template <typename IITR1, typename IITR2> 
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2) 
{ 
    return distance(first1, last1) == distance(first2, last2) && 
     equal(first1, last1, first2); 
} 

टुकड़ा 2:

template <typename IITR1, typename IITR2> 
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2) 
{ 
    while (first1 != last1 && first2 != last2) { 
     if (!(*first1 == *first2)) return false; 
     ++first1; ++first2; 
    } 
    return first1 == last1 && first2 == last2; 
} 

नोट: मैं इसे की जाँच नहीं की है, लेकिन मैं बहुत संदिग्ध है कि संकलक टुकड़ा अनुकूलित करेंगे 1 ऐसी है कि वह पैदा करता होगा खंड 2 द्वारा उत्पादित एक ही प्रदर्शन के साथ कोड।

पूरा होने के लिए, निम्नलिखित कोड खंड बेकार के बगल में है, क्योंकि यह सीमा असफल होने पर असफल हो जाएगी:

template <typename IITR1, typename IITR2> 
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2) 
{ 
    return equal(first1, last1, first2) && equal(first2, last2, first1); 
} 

Answer 1

पहला केवल आगे इटरेटर के लिए काम करेगा, सामान्य रूप से इनपुट इटरेटर्स नहीं।

प्रदर्शन इटेटरेटर प्रकार पर निर्भर करेगा। सबसे पहले यादृच्छिक-पहुंच इटरेटर्स के लिए तेज़ होने की संभावना है क्योंकि equal का मुख्य पाश आपके दूसरे कार्यान्वयन के मुख्य पाश से सरल है; लेकिन अगर distance को पूरी श्रृंखला में फिर से चालू करना है तो धीमा होने की संभावना है।

इनपुट इटरेटर्स का समर्थन करने के लिए, और सभी परिस्थितियों में सर्वश्रेष्ठ प्रदर्शन प्राप्त करने के लिए, आपको शायद विभिन्न इटरेटर श्रेणियों के लिए अलग-अलग विशेषज्ञता की आवश्यकता होगी। मैं दूसरे के साथ शुरू करूंगा, और केवल तभी विशेषज्ञ हूं जब आपको लगता है कि यह पर्याप्त नहीं है।

मुझे नहीं पता कि यह मानक पुस्तकालय में क्यों नहीं है, लेकिन आप किसी भी लाइब्रेरी में प्रत्येक संभावित एल्गोरिदम को शामिल करने की उम्मीद नहीं कर सकते हैं।

Answer 2

यह संभावना है कि जब एसटीएल को उस स्थिति को मानकीकृत किया जा रहा था जहां दो श्रेणियां गैर-यादृच्छिक-पहुंच हैं लेकिन अलग-अलग लंबाई पर विचार नहीं किया गया था; और दोष रिपोर्ट देख रहे हैं क्योंकि ऐसा लगता है कि यह बहुत अधिक मांग नहीं किया गया है। जैसा कि आपने देखा है, अपने स्वयं के संस्करण को लिखना काफी आसान है जो इसे सही बनाता है।

एक फ़िक्स को पुन: स्थापित करने में कोई समस्या यह तय करेगी कि चार-पैरामीटर कॉल दो-श्रेणी कॉल (it1, it1_end, it2, it2_end) या (it1, it1_end, it2, predicate) संस्करण है या नहीं। अंतर करने की तकनीक (SFINAE, enable_if) केवल हाल ही में उपलब्ध है।

ध्यान दें कि बूस्ट.रेंज में एक कार्यान्वयन है जो इसे सही बनाता है; कार्यान्वयन के लिए http://www.boost.org/doc/libs/1_51_0/boost/range/algorithm/equal.hpp देखें। यह भी पता लगाता है कि जब दो इटरेटर प्रकार यादृच्छिक-पहुंच होते हैं और distance को शॉर्ट सर्किट में कॉल करते हैं, जहां लंबाई अलग होती है।

#include <boost/range/algorithm.hpp> 

boost::equal(boost::make_iterator_range(first1, last1), 
    boost::make_iterator_range(first2, last2));