एसटीएल एल्गोरिदम

लोअर_बाउंड और अपर_बाउंड बिल्ट-इन बाइनरी सर्च फंक्शन हैं।

निचला_बाउंड - एक फ़ंक्शन जो लघुगणकीय समय में, क्रमबद्ध सरणी में सबसे छोटा तत्व पाता है जो दिए गए मान k से अधिक या उसके बराबर होता है।
यह सरणी की सीमा और k के मान को तर्क के रूप में लेता है।
यदि ऐसा कोई तत्व मौजूद नहीं है, तो पाया गया तत्व या सरणी के अंत (शामिल नहीं) के लिए एक पुनरावर्तक लौटाता है।
आप दस्तावेज़ीकरण में अधिक पढ़ सकते हैं।

अपर_बाउंड - एक फ़ंक्शन जो लघुगणकीय समय में एक क्रमबद्ध सरणी में सबसे छोटा तत्व पाता है जो दिए गए मान k से सख्ती से अधिक है।
यह सरणी की सीमा और k के मान को तर्क के रूप में लेता है।
यदि ऐसा कोई तत्व मौजूद नहीं है, तो पाया गया तत्व या सरणी के अंत (शामिल नहीं) के लिए एक पुनरावर्तक लौटाता है।
आप दस्तावेज़ीकरण में अधिक पढ़ सकते हैं।

यह स्पष्ट करने योग्य है कि उपरोक्त रैंडम एक्सेस संग्रह में पुनरावृत्तियों की कमी के कारण सेट या मल्टीसेट पर इन कार्यों का उपयोग लघुगणकीय समय में काम नहीं करता है।
हालाँकि, इन संग्रहों में संबंधित अंतर्निहित विधियाँ हैं (अर्थात, आपको उन्हें "डॉट के माध्यम से" उपयोग करने की आवश्यकता है)।

उदाहरण:
  वेक्टर ए = {0, 1, 3, 5, 7}; वेक्टर::इटरेटर इट; यह = निचला_बाउंड (a.begin (), a.end (), 4); // * यह == 5 यह = निचला_बाउंड (a.begin (), a.end (), 5); // * यह == 5 यह = निचला_बाउंड (a.begin (), a.end (), 8); // यह == a.end () यह = ऊपरी_बाउंड (a.begin (), a.end (), 4); // * यह == 5 यह = ऊपरी_बाउंड (a.begin (), a.end (), 5); // * यह == 7 यह = ऊपरी_बाउंड (a.begin (), a.end (), -1); // * यह == 0 // पुनरावृत्तियों को घटाकर, आप पाए गए तत्व का सूचकांक प्राप्त कर सकते हैं int ind = निचला_बाउंड (a.begin (), a.end (), 4) - a.begin (); // इंडस्ट्रीज़ == 3 // सेट और समान संग्रह के कार्यों के बजाय विधियों का उपयोग करने की आवश्यकता है सेट एस {1, 3, 5}; सेट :: इटरेटर बैठो; बैठो = s.lower_bound (3); // *बैठो == 3 बैठो = s.upper_bound (3); // *बैठो == 5  

अद्वितीय - एक ऐसा फ़ंक्शन जो रैखिक समय में समान लगातार तत्वों के सभी अनुक्रमों को एक में संपीड़ित करता है।
एक तर्क के रूप में, यह सरणी की सीमाओं को पार कर गया है, जिसके भीतर संपीड़न लागू करना आवश्यक है।
एक पुनरावर्तक सरणी के नए अंत (शामिल नहीं) पर वापस आ गया है। आपको नए अंत के बाद लेकिन पुराने वाले से पहले तत्वों से सावधान रहना चाहिए, क्योंकि उनका एक अपरिभाषित मान होगा।
आप दस्तावेज़ीकरण में अधिक पढ़ सकते हैं।

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

उदाहरण:
  वेक्टर a = {3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5}; अद्वितीय (a.begin (), a.end ()); // ए = [3, 2, 3, 1, 4, 5,?,?,?,?,?] // अद्वितीय फ़ंक्शन का उपयोग करना सुविधाजनक है // समन्वय संपीड़न के लिए सहायक सरणी ए = {235, 10, 41, 10, 41, 41, 235, 500, 500}; सॉर्ट (a.begin (), a.end ()); // ए = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize (अद्वितीय (a.begin (), a.end ()) - a.begin ()); // ए = [10, 41, 235, 500]  

मर्ज - एक फ़ंक्शन जो दो क्रमबद्ध सरणियों को मर्ज करता है, अर्थात्, रैखिक समय में यह एक क्रमबद्ध सरणी प्राप्त करता है, जिसमें पहली और दूसरी सरणी के तत्व होते हैं।
इसमें 5 तर्क होते हैं: प्रत्येक सरणी के लिए दो सीमाएँ और गंतव्य की बाईं सीमा (जहाँ परिणामी सरणी के तत्व रखे जाएंगे)।
अधिक विवरण दस्तावेज़ीकरण में पाया जा सकता है।

उदाहरण: // स्रोत सरणियों को क्रमबद्ध किया जाना चाहिए वेक्टर ए = {1, 3, 5, 7}; वेक्टर <इंट> बी = {2, 4, 6}; // गंतव्य काफ़ी बड़ा होना चाहिए वेक्टर <इंट> सी (7); विलय (a.begin (), a.end (), b.begin (), b.end (), c.begin ()); // सी = [1, 2, 3, 4, 5, 6, 7] // तत्वों को दोहराया जा सकता है ए = {1, 2, 4, 4}; बी = {2, 3, 3, 3, 4, 4}; सी. आकार बदलें (10); विलय (a.begin (), a.end (), b.begin (), b.end (), c.begin ()); // सी = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  मर्ज सॉर्ट के संदर्भ में यह फ़ंक्शन बहुत उपयोगी है।

nth_element एक ऐसा फ़ंक्शन है जो आपको रैखिक समय में क्रमबद्ध क्रम में सरणी में nवें तत्व को खोजने की अनुमति देता है।
फ़ंक्शन सरणी के बाएं सिरे को लेता है, एक पुनरावर्तक को उस स्थिति में ले जाता है जिसका मान क्रमबद्ध क्रम में पाया जाना है, और सरणी का दाहिना छोर।
फ़ंक्शन को लागू करने के बाद, आवश्यक मान पुनरावर्तक द्वारा इंगित स्थान पर स्थित होगा, जबकि शेष मान एक अराजक क्रम प्राप्त करेंगे, लेकिन nth के बाईं ओर इससे अधिक मूल्य नहीं होंगे, और दाईं ओर कम नहीं। अर्थात्, यह समझा जाना चाहिए कि यह फ़ंक्शन तत्वों के मूल क्रम को नष्ट कर देता है।
आप दस्तावेज़ में अधिक पढ़ सकते हैं (https://www.cplusplus.com/reference/algorithm/nth_element/)।

उदाहरण: वेक्टर ए = {4, 0, 3, 9, 2, 1, 8, 5, 6, 7}; // इंडेक्स 4 पर तत्व की तलाश करें // तर्कों के क्रम पर ध्यान दें nth_element (a.begin (), a.begin () + 4, a.end ()); // ए = [#, #, #, #, 4, $, $, $, $, $] // जहां # <= 4 और 4 <= $  

लंबाई n का क्रमचय संख्या 1, 2, ..., n की पुनरावृत्ति के बिना एक क्रमबद्ध संग्रह है। उदाहरण के लिए, [3, 1, 2] और [5, 4, 3, 2, 1] क्रमपरिवर्तन हैं, लेकिन [1, 2, 1, 3] और [1, 2, 4] नहीं हैं।

यदि कार्य को इस तथ्य तक सीमित कर दिया जाता है कि लंबाई n के सभी क्रमपरिवर्तनों पर पुनरावृति करना आवश्यक है, तो आप C ++ में एक सुविधाजनक तंत्र का उपयोग कर सकते हैं, जिसे "next_permutation" कहा जाता है।

आप इसके बारे में documentation में अधिक पढ़ सकते हैं, लेकिन मुद्दा यह है कि यह फ़ंक्शन पारित सरणी को बदलता है लेक्सिकोग्राफिक क्रम में बाद के क्रमपरिवर्तन के लिए (जो आम तौर पर स्पष्ट और उसका नाम है)।

next_permutation का उपयोग करने के लिए, आपको एल्गोरिथम लाइब्रेरी शामिल करने की आवश्यकता है (यानी प्रोग्राम की शुरुआत में #include <algorithm> लिखें)

उदाहरण: वेक्टर गिरफ्तार; आगमन = {1, 2, 3}; // सरणी है [1, 2, 3] अगला_क्रमपरिवर्तन (arr.begin (), arr.end ()); // पूरे सरणी को फ़ंक्शन में पास करें // सरणी अब [1, 3, 2] है आगमन = {2, 3, 1}; // सरणी [2, 3, 1] है अगला_क्रमपरिवर्तन (arr.begin (), arr.end ()); // पूरे सरणी को फ़ंक्शन में पास करें // सरणी अब [3, 1, 2] है अगला_क्रमपरिवर्तन (arr.begin () + 1, arr.begin () + 3); // किसी फ़ंक्शन को सरणी के एक भाग पर लागू करना संभव है, लेकिन व्यवहार में इसकी शायद ही कभी आवश्यकता होती है // सरणी अब [3, 2, 1] है
इस स्थिति में, फ़ंक्शन का एक बूलियन रिटर्न मान होता है जो कि अगला क्रमचय उत्पन्न होने पर सत्य होता है और यदि अगला क्रमपरिवर्तन नहीं होता है तो असत्य होता है (ऐसा मामला जब लेक्सिकोग्राफ़िक क्रम में अधिकतम क्रमचय फ़ंक्शन को पास किया जाता है)।
यह लूप में फ़ंक्शन का उपयोग करना संभव बनाता है, जो हमें एक ही बार में सभी क्रमपरिवर्तनों पर पुनरावृति करने की अनुमति देगा। 0-अनुक्रमण के कारण, व्यवहार में अक्सर 0 से n-1 तक की संख्याओं के क्रमचय के साथ काम करना अधिक सुविधाजनक होता है, हालांकि एक क्रमचय में औपचारिक रूप से 1 से n तक की संख्याएँ होती हैं। लेकिन सौभाग्य से, इससे कोड में अतिरिक्त ओवरले नहीं होते हैं, क्योंकि अगला_परमुटेशन फ़ंक्शन 0-अनुक्रमित क्रमपरिवर्तन (और यहां तक ​​कि सरणी में डुप्लिकेट तत्वों के लिए भी अनुकूलित किया गया है, लेकिन आप अपने दम पर अधिक जानकारी प्राप्त कर सकते हैं)।

सामान्य तौर पर, सभी क्रमपरिवर्तनों पर पुनरावृति के लिए कोड इस तरह दिखता है:   इंटन; // क्रमपरिवर्तन आकार वेक्टर पर्म (एन); // पर्म "क्रमपरिवर्तन" के लिए छोटा है, अर्थात। "क्रमपरिवर्तन" के लिए (int i = 0; i < n; i++) पर्म [i] = मैं; // आरंभिक क्रमपरिवर्तन 0, 1, ..., n - 1 प्रारंभ करें करना { // लूप के अंदर हम वर्तमान क्रमचय को संसाधित करते हैं } जबकि (next_permutation(perm.begin(), perm.end())); // यदि कोई अगला क्रमचय नहीं है, तो लूप को समाप्त करें

यह कोड O(n! * f(n)) में चलता है, जहाँ f(n) वह समय है जो आपको एक विशेष क्रमचय को संसाधित करने में लगता है।