वेक्टर के सदस्य फ़ंक्शन के रूप में वेक्टर() विधि क्यों नहीं है, जबकि सूची करता है?

Question

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

sort(v.begin(), v.end()); 

---

अद्यतन: (टिप्पणी का जवाब): ठीक है, वे निश्चित रूप से यह डिफ़ॉल्ट द्वारा प्रदान की है

Answer 1

जैसा कि पहले से ही कहा जा चुका है, मानक लाइब्रेरी एक गैर-सदस्य फ़ंक्शन टेम्पलेट प्रदान करती है जो किसी भी श्रेणी को यादृच्छिक एक्सेस इटरेटर्स की एक जोड़ी प्रदान कर सकती है।

वेक्टर को सॉर्ट करने के लिए सदस्य फ़ंक्शन के लिए पूरी तरह से अनावश्यक होगा। निम्नलिखित में एक ही अर्थ होगा:

std::sort(v.begin(), v.end()); 
v.sort(); 

एसटीएल के पहले सिद्धांतों में से एक है कि एल्गोरिदम कंटेनरों के लिए युग्मित नहीं कर रहे हैं। डेटा कैसे संग्रहीत किया जाता है और डेटा का उपयोग कैसे किया जाता है, उतना ही कम से कम युग्मित होना चाहिए।

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

कारण std::list एक सदस्य फ़ंक्शन के रूप में अपना sort फ़ंक्शन प्रदान करता है यह है कि यह एक यादृच्छिक सुलभ कंटेनर नहीं है; यह केवल बिडरेक्शनल इटरेटर्स प्रदान करता है (क्योंकि यह एक दोगुनी लिंक्ड सूची का प्रतिनिधित्व करने का इरादा है, यह समझ में आता है)। जेनेरिक std::sort फ़ंक्शन को यादृच्छिक एक्सेस इटरेटर्स की आवश्यकता होती है, इसलिए आप इसे std::list के साथ उपयोग नहीं कर सकते हैं। std::list अपना खुद का sort फ़ंक्शन प्रदान करता है ताकि इसे क्रमबद्ध किया जा सके।

सामान्य तौर पर, वहाँ दो मामलों में एक कंटेनर एक एल्गोरिथ्म को लागू करना चाहिए:

• सामान्य एल्गोरिथ्म कंटेनर पर काम नहीं कर सकते, लेकिन वहाँ एक अलग, कंटेनर विशेष एल्गोरिथ्म है कि प्रदान कर सकता है समान कार्यक्षमता, जैसा कि std::list::sort के मामले में है।

• कंटेनर, एल्गोरिथ्म सामान्य एल्गोरिथ्म तुलना में अधिक कुशल है कि की एक विशिष्ट कार्यान्वयन प्रदान कर सकते हैं के रूप में std::map::find के मामले में, एक तत्व लघुगणक समय में नक्शा (सामान्य std::find एल्गोरिथ्म में पाया जा करने की अनुमति देता है एक रैखिक खोज करता है क्योंकि यह मान नहीं सकता कि श्रेणी क्रमबद्ध है)।

Answer 2

आप आसानी से एक साथ vector सॉर्ट कर सकते हैं। अंतर यह है कि यह vector के लिए सदस्य फ़ंक्शन नहीं है। std::sort एक सामान्य एल्गोरिदम है जो के लिए कुछ भी के लिए काम करना चाहिए जो इटरेटर प्रदान करता है। हालांकि, यह वास्तव में एक यादृच्छिक अभिगम इटरेटर को कुशलतापूर्वक क्रमबद्ध करने की अपेक्षा करता है। std::list, एक लिंक्ड सूची होने के नाते, अपने तत्वों को कुशलता से यादृच्छिक पहुंच प्रदान नहीं कर सकता है। यही कारण है कि यह अपने विशेष प्रकार के एल्गोरिदम प्रदान करता है।

Answer 3

<algorithm>std::vector जैसे यादृच्छिक एक्सेस इटरेटर्स वाले कंटेनरों पर सॉर्टिंग करता है।

std::stable_sort() भी है।

संपादित करें - std::list का अपना sort() फ़ंक्शन बनाम std::vector क्यों है?

std::liststd::vector और std::deque दोनों यह कैसे लागू हो जाता है (दोनों यादृच्छिक iterable पहुँच) से अलग है, तो यह अपने आप ही sort एल्गोरिथ्म है कि इसके कार्यान्वयन के लिए विशेष होता है।

Answer 4

एक वेक्टर-विशिष्ट प्रकार <algorithm> से std::sort पर कोई लाभ नहीं प्रदान करेगा। हालांकि, std::list अपना खुद का sort प्रदान करता है क्योंकि यह विशेष जानकारी का उपयोग कर सकता है कि list वस्तुओं को कॉपी करने के बजाय लिंक को जोड़कर वस्तुओं को सॉर्ट करने के लिए लागू किया गया है।

Answer 5

"क्यों?" के सवाल का जवाब

std :: वेक्टर के लिए एक सॉर्टिंग एल्गोरिदम एक मूल सरणी को सॉर्ट करने जैसा ही है और एक कस्टम वेक्टर वर्ग को सॉर्ट करने के समान (संभवतः) है।

एसटीएल को कंटेनर और एल्गोरिदम को अलग करने के लिए डिज़ाइन किया गया था, और सही विशेषताओं वाले डेटा में एल्गोरिदम लागू करने के लिए एक कुशल तंत्र है।

यह आपको एक कंटेनर लिखने देता है जिसमें विशिष्ट विशेषताओं हो सकती है, और एल्गोरिदम मुक्त हो सकती है। केवल तभी जहां डेटा की कुछ विशेष विशेषता है जिसका मतलब है कि मानक एल्गोरिदम अनुपयुक्त है, एक कस्टम कार्यान्वयन है, जैसा कि std :: सूची के मामले में है।

Answer 6

उत्तर के पहले से ही दिलचस्प तत्व हैं, लेकिन वास्तव में सवाल के बारे में और कहा जाना चाहिए: "std::vector का जवाब sort सदस्य फ़ंक्शन क्यों है?" वास्तव में "क्योंकि मानक पुस्तकालय केवल सदस्य कार्य प्रदान करता है जब वे जेनेरिक एल्गोरिदम से अधिक ऑफर करते हैं", असली दिलचस्प सवाल यह है कि "std::list में sort सदस्य फ़ंक्शन क्यों है?", और कुछ चीजें अभी तक समझाई नहीं गई हैं: हां, std::sort केवल यादृच्छिक अभिगम iterators साथ काम करता है और std::list केवल द्विदिश iterators प्रदान करता है, लेकिन भी std::sort अगर द्विदिश iterators के साथ काम किया, std::list::sort अभी भी अधिक की पेशकश करेगा।

सभी की

• पहले, std::list::sort, स्थिर है, जबकि std::sort नहीं है: और यहाँ क्यों है। बेशक अभी भी std::stable_sort है, लेकिन यह बिडरेक्शनल इटरेटर्स के साथ भी काम नहीं करता है।

• std::list::sort आम तौर पर एक विलय को लागू करता है, लेकिन यह जानता है कि यह एक सूची को क्रमबद्ध कर रहा है और चीजों की प्रतिलिपि बनाने के बजाय नोड्स को फिर से जोड़ सकता है। एक सूची-जागरूक विलय, ओ (एन लॉग एन) समय में केवल ओ (लॉग एन) अतिरिक्त मेमोरी के साथ सूची को सॉर्ट कर सकता है, जबकि आपका सामान्य विलय (जैसे std::stable_sort) ओ (एन) अतिरिक्त मेमोरी का उपयोग करता है या ओ (एन लॉग²) एन) जटिलता।

• std::list::sort iterators को अमान्य नहीं करता है। यदि एक पुनरावर्तक सूची में किसी विशिष्ट ऑब्जेक्ट को इंगित कर रहा था, तो यह अभी भी उसी ऑब्जेक्ट को इंगित करेगा, इस प्रकार के बाद भी, यदि सूची में इसकी स्थिति क्रम से पहले समान नहीं है।

• अंतिम लेकिन कम से कम नहीं, std::list::sort वस्तुओं को स्थानांतरित या स्वैप नहीं करता है क्योंकि यह केवल नोड्स को रिलेक्स करता है। इसका मतलब यह है कि जब आप उन वस्तुओं को सॉर्ट करने की ज़रूरत होती है जो आपको स्थानांतरित करने/घूमने के लिए महंगी होती हैं, लेकिन यह भी उन वस्तुओं की एक सूची को सॉर्ट कर सकती है जो गतिशील नहीं हैं, जो std::sort के लिए पूरी तरह असंभव है!

मूल रूप से, यहां तक ​​कि अगर std::sort और std::stable_sort द्विदिश या आगे iterators के साथ काम किया है (और यह पूरी तरह से, हम एल्गोरिदम कि उनके साथ काम छँटाई पता संभव होगा), वे अभी भी सब कुछ प्रस्ताव दिया है std::list::sort की पेशकश नहीं कर सकता है, और वे नोड्स को फिर से नहीं जोड़ पाएंगे क्योंकि मानक लाइब्रेरी एल्गोरिदम को कंटेनर को संशोधित करने की अनुमति नहीं है, केवल उन्मुख मान (कंटेनर को संशोधित करने के रूप में नोड्स को प्रतिबिंबित करते हैं)। दूसरी ओर, एक समर्पित std::vector::sort विधि कुछ भी दिलचस्प नहीं प्रदान करेगी, इसलिए मानक पुस्तकालय एक प्रदान नहीं करता है।

ध्यान दें कि std::list::sort के बारे में जो भी कहा गया है, वह भी std::forward_list::sort के लिए भी सही है।