एसटीडी की एक अप्रिय विशेषता :: सूची जिसके बारे में हर कोई नहीं जानता है

एक दोहरी लिंक की गई सूची एक मूलभूत डेटा संरचना है जिसे हर कोई जानता है और हर जगह उपयोग करता है। हर कोई जानता है कि क्यों और किन मामलों में यह वेक्टर से अधिक प्रभावी है, किन कार्यों में रैखिक जटिलता होती है, और जो निरंतर होती हैं ...

हालांकि प्रतीक्षा करें, क्या आप जानते हैं कि आकार () फ़ंक्शन कितना जटिल है?
"निश्चित रूप से मुझे पता है - ओ (1)!" आप में से कई लोग जवाब देंगे, "क्या सरल हो सकता है?"

size_type size() const { return _size; } 

तुच्छ, प्रभावी और सुरक्षित है, है ना?
मैं इस फ़ंक्शन को इस तरह से लागू करूंगा, आप में से अधिकांश ऐसा ही करेंगे।

हालांकि, जिन लोगों ने जीएनयू एसटीएल कार्यान्वयन लिखा है, उनकी एक अलग राय है।


इस प्रकार gcc 4.x में इस फ़ंक्शन का कार्यान्वयन कैसा दिखता है:

 /** Returns the number of elements in the %list. */ size_type size() const { return std::distance(begin(), end()); } 

यदि आप मुझ पर विश्वास नहीं करते हैं - अपने वितरण में जाँच करें।

हम यहां क्या देखते हैं? आकार प्राप्त करने के रूप में इस तरह के एक तुच्छ ऑपरेशन करने के लिए, हमारी सूची गिनती के साथ एक पूर्ण पास का प्रदर्शन करेगी!

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

 for (std::list <int>::const_iterator I = my_list.begin (); I != my_list.end (); ++I) { if (*I > my_list.size ()) { std::cout << "Haha! "<< *I << std::endl; } } 

स्पष्ट रूप से स्पष्ट O (N) के बजाय, हम यहाँ O (N ^ 2) प्राप्त करते हैं। यदि सूची में 100 आइटम हैं तो यह अच्छा है। लेकिन क्या अगर 1,000,000?

इसका अर्थ यह भी है कि कॉलिंग आकार () बहु-थ्रेडेड वातावरण में असुरक्षित है।

 std::list <int> my_list; // Thread 1 void thread1_proc () { while (!stop) { std::cout << "List size: " << my_list.size () << std::endl; } } // Thread 2 void thread2_proc () { while (!stop) { int n = rand () my_list.push_back (n); if (n % 2) my_list.pop_front (); } } 

हमें पहले धागे में दुर्घटना होने का गंभीर खतरा है।

इसका मतलब भी यही है

• दो सूचियों की तुलना करने के लिए, हमें हमेशा एक पूर्ण पास करना पड़ता है, बजाय एक तुच्छ आकार की तुलना में 90% मामलों को काटने से।
• कम कुशल आकार। यहां हमारे पास दो मामले हैं
  1. आकार में कमी। यदि सूची का आकार हमें ज्ञात है (O (1 के लिए उपलब्ध है) पढ़ें), तो हम यह तय कर सकते हैं कि क्या हम शुरुआत से या अंत से गुजरना शुरू करते हैं, इस आधार पर कि क्या हम अंत में कई तत्वों को हटाते हैं या इसके विपरीत, शुरुआत में कुछ छोड़ देते हैं। जीएनयू कार्यान्वयन में, यह संभव नहीं है।
  2. आकार में वृद्धि। यदि सूची का आकार हमें ज्ञात है, तो हमारे लिए बस गायब तत्वों को जोड़ना पर्याप्त है। जीएनयू कार्यान्वयन में, हमें हमेशा सूची पर एक पूर्ण पास करना होगा।
  
• शायद कुछ और जो जानता हो, मुझे बताओ।

तो क्या GNU प्रोग्रामर इस सूची को लागू करते हैं?

यह पता चला है कि _size आंतरिक चर बनाए रखने की आवश्यकता की कमी से ब्याह को O (1) में लागू किया जा सकता है, अन्यथा O (N) सबसे खराब स्थिति के लिए होगा।

विभाजन एक तत्व से दूसरी सूची में लगातार तत्वों को स्थानांतरित करने का संचालन है। सूचियों के नए आकारों को गिनने की कोई आवश्यकता नहीं है, यह हमारे लिए एक नोड से दूसरे नोड पर "स्विच" करने के लिए पर्याप्त है, अर्थात लगातार समय के लिए।

आंतरिक चर को _size करने के बाद, हमें गणना करना होगा कि हम कितने तत्वों को स्थानांतरित करते हैं और इसे दोनों सूचियों के अनुसार अपडेट करते हैं।

यहाँ ऐसा कारण है। वैसे, आप कितनी बार इस ऑपरेशन का उपयोग करते हैं? और उपरोक्त सभी?

सामान्य तौर पर, सावधान रहें। और ध्यान रखें कि अन्य एसटीएल कार्यान्वयनों में चर _ आकार (और) तदनुसार ओ (1) के लिए काम करता है। इसलिए दो बार सावधान रहें यदि आप विभिन्न प्लेटफार्मों पर विभिन्न एसटीएल कार्यान्वयनों के साथ अपनी परियोजना का निर्माण कर रहे हैं।

मैं इस पर झुकता हूं। शुक्रवार को वानस्पतिक पद के लिए क्षमा करें।

युपीडी
नए C ++ 11 मानक में O (1) के लिए सभी STL कंटेनरों के लिए उस आकार की आवश्यकता होती है, जो बहुत अच्छा है।
हालांकि, जीएनयू एसटीएल कार्यान्वयन में बदलाव करने का प्रयास बाइनरी संगतता मुद्दों के कारण अब तक विफल रहा है। यहां पढ़ें gcc.gnu.org/bugzilla/show_bug.cgi?id=49561