std :: list :: splice और अन्य सूची कंटेनर की जटिलता

Question

मेरे पास कुछ कोड है जो विभिन्न std :: सूची ऑब्जेक्ट्स से संबंधित है, और मैं वर्तमान में उनके बीच सामग्री स्थानांतरित करने की एक बहुत ही अक्षम विधि का उपयोग कर रहा हूं (मैं इसके माध्यम से पुनरावृत्त कर रहा हूं एक सूची के मनमाने ढंग से खंड, और तत्वों को एक-दूसरे को दूसरी सूची में ले जाना)। मैं इस कोड में कुछ समय पहले लिखा था इससे पहले कि मैं std :: सूची :: जोड़ समारोह है, जो मैं अब के साथ अपने कोड को बदलने का इरादा के बारे में पता था, उदाहरण के लिए:

list<string> list1, list2; 

list1.push_back("a"); 
list1.push_back("b"); 
list1.push_back("c"); // list1: "a", "b", "c" 

list<string>::iterator iterator1 = list1.begin(); 
iterator1++: // points to "b" 

list2.push_back("x"); 
list2.push_back("y"); 
list2.push_back("z"); // list2: "x", "y", "z" 

list<string>::iterator iterator2 = list2.begin(); 
iterator2++; // points to "y" 

list1.splice(iterator1, list2, iterator2, list2.end()); 

// list1: "a", "y", "z", "b", "c" 
// list2: "x" 

मैं की जटिलता से संबंधित प्रश्न है splice समारोह।

http://www.cplusplus.com/reference/stl/list/splice/

यह रेंज में रैखिक जटिलता होना चाहिए पहली और आखिरी तत्वों के बीच (iterator2 और मेरे उदाहरण में list2.end()) में spliced ​​किया जा रहा है, और स्रोत संकेत यह है कि: इस स्रोत के अनुसार इटेटरेटर अग्रिम की वजह से है। मैं इसके साथ रह सकता हूं लेकिन मैं निरंतर जटिलता की उम्मीद कर रहा था।

मेरे धारणा (इससे पहले कि मैं इस स्रोत पाया जाता है) था जोड़ समारोह कुछ इस तरह करते हैं कि:

1. Sever के बीच "x" और "y" लिंक
2. Sever "Z" के बीच की कड़ी और list2.end()
3. के बीच "x" और list2.end()
4. Sever के बीच "एक" और "बी" लिंक
5. फार्म के बीच "एक" और "वाई" एक लिंक एक लिंक फार्म
6. "वाई" और "बी"

के बीच एक लिंक बनाएं इस प्रकार श्रृंखलाओं को पूरा करने के लिए दोनों सूचियों को पुनर्स्थापित करना।

वही सिद्धांत मनमाने ढंग से आकार की सूचियों पर लागू होगा। मुझे यकीन नहीं है कि मैं देखता हूं कि स्प्लिस फ़ंक्शन के लिए किसी भी इटरेटर को अग्रिम करने की आवश्यकता है, क्योंकि मैं इसे सभी इटरेटर के साथ प्रदान कर रहा हूं, इसे इसे करने की ज़रूरत है।

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

Answer 1

यह सी ++ 11 के मानकीकरण के दौरान एक बहुत ही विवादास्पद विषय था। समस्या यह है कि सूचियों समेत सभी मानक कंटेनरों में निरंतर समय size ऑपरेशन भी होता है।

सी ++ 11 से पहले, कई कार्यान्वयन size रैखिक समय और splice विभिन्न सूचियों के बीच निरंतर समय के बीच बनाते हैं। सी ++ 11 अब आवश्यक है कि size स्थिर रहें और splice रैखिक हो।

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

एक गैर-मानक list कंटेनर वांछित ऑपरेशन की आपूर्ति कर सकता है, क्योंकि जब तक आपको O (1) size की आवश्यकता नहीं है, तो आपका तर्क सही है।

अन्य पुस्तकालयों के लिए ... मुझे एक के बारे में पता नहीं है, लेकिन को बढ़ावा देना चाहिए एक होना चाहिए। (मैंने जांच की, ऐसा नहीं है, इसलिए कोई भी शुरू हो गया है!) चूंकि आप स्पष्ट रूप से समझते हैं कि खुद को कैसे लिखना है, ऐसा करना क्यूटी के रूप में ऐसी बड़ी लाइब्रेरी के साथ तुलना करने से कम प्रयास हो सकता है।

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