क्या मैं अंतर्निहित कंटेनर के बिना std :: upper_bound का उपयोग कर सकता हूं?

Question

मेरे पास पूर्णांक [start, end] और गैर-घटते मोनोटोनिक फ़ंक्शन f(i) की एक श्रृंखला है। तो अवधारणात्मक रूप से, मेरे पास एक गैर-घटती अनुक्रम [f(start), f(start + 1), .. , f(end)] है। क्या मैं रखता है उस श्रेणी में पहला तत्व i खोजने के लिए उस अनुक्रम पर std::upper_bound का उपयोग कर सकता हूं?

वैचारिक रूप से, मैं कुछ इस तरह करना चाहते हैं:

std::upper_bound(start, end + 1, some_value, [&](int lhs, int rhs) { 
    return f(lhs) < f(rhs); 
}); 

लेकिन इस संकलन नहीं है क्योंकि start और end + 1forward iterators की आवश्यकताओं को पूरा नहीं करते।

Answer 1

संक्षिप्त उत्तर हाँ है, क्योंकि std::upper_bound कंटेनर पर नहीं, इटरेटर पर काम करता है। लेकिन इटेटर स्वयं संबंधित वर्ग के उदाहरण हैं (उदाहरण के लिए, std::vector<int>::iterator या व्हाट्नॉट)।

यदि आप कुछ विशिष्ट वर्ग का निर्माण करते हैं जो ForwardIterator की आवश्यकताओं को पूरा करेगा, वास्तव में कुछ प्रकार के कंटेनर से बंधे नहीं हैं, जबकि अभी भी कुछ अर्थ है (उदाहरण के लिए, यदि आप अपने अनुक्रम को प्रक्रियात्मक रूप से उत्पन्न करना चाहते हैं), तो यह ठीक काम करना चाहिए ।

ध्यान दें कि सरल पूर्णांक चाल नहीं करेगा। दूसरी तरफ, एक वर्ग, जिसका ऑब्जेक्ट किसी विशेष तर्क मान (कुछ अतिरिक्त बैटरी के साथ) के लिए आपके फ़ंक्शन का मान रखता है, होगा।

Answer 2

मूल रूप से दो उत्तर हैं:
क्या यह मानक द्वारा काम करेगा या यह एसटीएल के सभी व्यावहारिक कार्यान्वयन के साथ काम करेगा?

मानक से, के रूप में पहले से ही T.C. pointed out, वहाँ iterators पर कुछ सख्त आवश्यकताओं, *it (इटरेटर के एक सदस्य के संदर्भ में वापस लौट कर जो हम संतुष्ट हैं) value_type करने के लिए एक (संभवतः स्थिरांक) संदर्भ वापस जाने के लिए है विशेष रूप से कर रहे हैं , लेकिन हमें it1 == it2, *it1 और *it2 के लिए भी एक ही ऑब्जेक्ट के संदर्भ में संदर्भ हैं, जो केवल तभी संभव है जब हमारे पास सीमा में प्रत्येक संख्या के लिए एक विशिष्ट वस्तु हो।

यदि आप अभ्यास में इस विचार का उपयोग करना चाहते हैं, तो मुझे std::upper_bound के किसी भी कार्यान्वयन पर विश्वास नहीं है या इसी तरह के तरीके वास्तव में इस संदर्भ समानता पर निर्भर करते हैं, तो आप केवल एक वर्ग का उपयोग कर सकते हैं जो एक इटरेटर के रूप में पूर्णांक को समाहित करता है necessary methods ओवरलोडिंग। जहां तक ​​मैं देख सकता हूं, boost::irange इन आवश्यकताओं को पूरा करता है

जैसा कि आप देख सकते हैं, यह सख्ती से मानक-अनुपालन नहीं है, लेकिन मुझे कोई कारण नहीं है कि बाइनरी खोज के किसी भी कार्यान्वयन को इटरेटर के लिए ऐसी मजबूत आवश्यकताओं पर भरोसा क्यों करना चाहिए, अगर अंतर्निहित 'भंडारण' वैसे भी है।

Answer 3

नहीं, व्यावहारिक रूप से नहीं, लेकिन अभ्यास में हाँ, लेकिन यदि आप व्यावहारिक होना चाहते हैं।

नहीं

upper_boundForwardIterator की आवश्यकता है। फॉरवर्डइटरेटर को * एक वास्तविक संदर्भ देता है, और कि यदि दो पुनरावर्तक बराबर हैं तो वे एक ही ऑब्जेक्ट को संदर्भित करते हैं।

नहीं व्यावहारिक रूप से

एक कंटेनर-कम इटरेटर लिए, यह एक पागलपन की हद तक जटिल इटरेटर है कि मूल्यों यह किसी तरह का एक साझा वैश्विक मानचित्र में देता कैश की आवश्यकता है। इसे आधा व्यावहारिक बनाने के लिए, ध्यान दें कि पुनरावर्तक आवश्यकताएं संदर्भ के जीवनकाल के बारे में बहुत कम कहती हैं; इसलिए आप गिनती का संदर्भ देना चाहते हैं और मूल्यों को नष्ट करना चाहते हैं क्योंकि प्रश्न में इटरेटर मौजूद हैं।

इस तरह के एक समाधान तुल्यकालन, वैश्विक राज्य की आवश्यकता है, और काफी अधिक महंगे और boost::integer_range की तरह कुछ की तुलना में जटिल है। कोई साधु व्यक्ति यह नहीं दिखाएगा कि एक अभ्यास के रूप में मानक को तय करने की आवश्यकता क्यों है।

लेकिन हाँ व्यवहार में

upper_boundका कोई समझदार कार्यान्वयन वास्तव में है कि प्रश्न में iterators पूर्ण पैमाने पर आगे iterators हैं की आवश्यकता है, एक है कि पूर्ण अवधारणा-जांच करता है मानक के खिलाफ मान्य करने के लिए करता है (और के खिलाफ नहीं को छोड़कर वास्तविक एल्गोरिदम की क्या ज़रूरत है)। मूल्यों पर स्थिरता के साथ इनपुट इटरेटर लगभग निश्चित रूप से यह करता है। सी ++ मानक में ऐसी कोई अवधारणा नहीं है, और आगे इटरेटर मानक में सबसे कमजोर इटरेटर श्रेणी है जो इसे प्रमाणित करता है।

यह समस्या, प्रभावी रूप से मांग की iterators कंटेनरों द्वारा समर्थित किया की, मेरी राय में मानक में एक दोष है। कंटेनर-फ्री इटरेटर्स शक्तिशाली और उपयोगी हैं, सिवाय इसके कि वे मानक कंटेनर में शायद ही कभी तकनीकी रूप से काम करते हैं।

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

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

लेकिन कोई अगर तुम व्यावहारिक

यह करता है, तथापि, एक बीमार का गठन कार्यक्रम में परिणाम होना चाहता हूँ, कोई निदान की आवश्यकता है। तो विचार करें कि यह इसके लायक है; यह वास्तव में एक कार्यक्रम जिसका हर excution अपरिभाषित व्यवहार है बनाए रखने की तुलना में upper_bound reimplement करना आसान हो सकता है, और हर एक संकलक उन्नयन की दया पर संकलित करें।