std :: forward_list और std :: forward_list :: push_back

Question

मैं उपयोग करने के लिए std::forward_list

क्योंकि चाहते हैं:

फॉरवर्ड सूची एक कंटेनर जो कहीं से भी तेजी से प्रविष्टि और तत्वों को हटाने का समर्थन करता है कंटेनर

लेकिन कोई * std :: forward_list :: push_back * कार्यान्वयन नहीं है।

क्या ऐसा करने के लिए एक या कोई कारण नहीं है, तो समर्थन जोड़ने के लिए एक उच्च प्रदर्शन तरीका है?

Answer 1

std::forward_list तेजी से सम्मिलन और हटाने का समर्थन करता है, लेकिन के अंत में ट्रैवर्सल नहीं है। .push_back को लागू करने के लिए, आपको पहले सूची के अंत तक पहुंचने की आवश्यकता होगी, जो ओ (एन) है और बिल्कुल तेज़ नहीं है, शायद यही कारण है कि इसे लागू नहीं किया गया है।

slist.insert_after(before_end, 1234); 

Answer 2

है:

 

आप incrementing .before_begin N बार

auto before_end = slist.before_begin(); 
for (auto& _ : slist) 
    ++ before_end; 

और फिर .insert_after या .emplace_after का उपयोग तत्व सम्मिलित करने के लिए से पिछले तत्व के लिए इटरेटर मिल सकता है नहीं push_back क्योंकि सूची सूची के पीछे का ट्रैक नहीं रखती है , केवल सामने।

आप सूची है कि पिछले तत्व के लिए एक इटरेटर कहना है, और है कि क्या सूची खाली है आधार पर या तो insert_after या push_front का उपयोग कर push_back लागू करता है के चारों ओर एक आवरण लिख सकते हैं। यदि आप अधिक जटिल परिचालनों का समर्थन करना चाहते हैं तो यह जटिल हो जाएगा (उदा। sort और splice_after)।

वैकल्पिक रूप से, यदि आपको push_back की आवश्यकता नहीं है, तो यह रैखिक समय में ऐसा करने के लिए सरल है।

जब तक स्मृति बहुत तंग नहीं होती है, तो सबसे अच्छा समाधान list का उपयोग करना है। इसमें forward_list के समान प्रदर्शन विशेषताएं हैं, और push_back के साथ-साथ push_front का समर्थन करने वाला बिडरेक्शनल है; लागत प्रति तत्व एक अतिरिक्त सूचक है।

Answer 3

std :: forward_list का बिंदु std :: सूची का अल्ट्रा-स्ट्रिप-डाउन संस्करण होना है, इसलिए यह अंतिम तत्व को पुनरावर्तक नहीं संग्रहीत करता है। आप एक की जरूरत है, तो आप इसे अपने आप को बनाए रखने के लिए है, तो तरह होगा:

forward_list<int> a; 

auto it = a.before_begin(); 

for(int i = 0; i < 10; ++i) 
    it = a.insert_after(it, i); 

Answer 4

मैं std::forward_list खिलाफ सलाह देते हैं वैसे ही जैसे मैं लगभग सभी स्थितियों में std::list के खिलाफ सलाह देते हैं। व्यक्तिगत रूप से, मुझे कभी भी मेरे कोड में कोई स्थिति नहीं मिली है जहां एक लिंक्ड सूची सबसे अच्छी डेटा संरचना थी।

सी ++ में, आपका डिफ़ॉल्ट डेटा-टू-डेटा संग्रह std::vector होना चाहिए। यह आपको push_back कुशल बनाता है, यदि आपको वही चाहिए जो आपको चाहिए। यह तकनीकी रूप से आपको मध्य से कुशल विलोपन और सम्मिलन नहीं देता है यदि आप केवल उस ऑपरेशन के अमूर्त बड़े-ओ जटिलता माप को देखते हैं।वास्तविक दुनिया में, std::vector अभी भी जीतने के लिए मध्य में डालने और हटाने के लिए भी जीतता है।

उदाहरण के तौर पर, बजेर्न स्ट्राउस्ट्रप ने 100,000 तत्व std::list बनाम std::vector का परीक्षण बनाया। वह प्रत्येक तत्व को खोजता है और इसे हटा देता है। फिर वह एक सम्मिलन बिंदु मिलेगा और बीच में डालेंगे। वह std::vector पर एक बाइनरी खोज का उपयोग कर सकता था, लेकिन तुलना 'अधिक निष्पक्ष' नहीं बना सका।

परिणाम std::vector के लिए एक मजबूत जीत दिखाते हैं, यहां तक ​​कि इस स्थिति में जहां std::list मजबूत होना चाहिए। बस std::list को घुमाने में इतनी अधिक समय लगती है कि सभी ऑब्जेक्ट्स मेमोरी में कितनी दूर हैं। std::list कैश-अनुकूल नहीं है, जो संभवतः आधुनिक प्रोसेसर के लिए सबसे महत्वपूर्ण बात है।

The complete talk by Bjarne Stroustrup

Thorough explanation of the effects, with benchmarks at multiple sizes

ध्यान दें कि यह दूसरी कड़ी यहाँ है जहाँ आप संभवतः इस तरह जब तत्वों का आकार बड़ा है के रूप में एक std::list, उपयोग कर सकते हैं की कुछ स्थितियों देता है। हालांकि, मैं ऐसी स्थिति में रहा हूं जहां मेरे पास किसी विशेष क्रम में कई तत्व हैं और कुछ को हटाने की आवश्यकता है।

ये तत्व किसी भी अंतर्निर्मित प्रकार से बड़े थे, लेकिन 32-बिट कंप्यूटर पर शायद 20-30 बाइट्स नहीं थे)। तत्वों की संख्या काफी बड़ी थी ताकि मेरी पूरी डेटा संरचना कुछ सौ एमआईबी थी। डेटा संग्रह मूल्यों का एक सेट था जो सैद्धांतिक रूप से वर्तमान में ज्ञात जानकारी के आधार पर वैध हो सकता है। एल्गोरिदम सभी तत्वों और हटाए गए तत्वों पर पुनरावृत्त होता है जो अब नई जानकारी के आधार पर मान्य नहीं हो सकते हैं, प्रत्येक पास संभवतः शेष तत्वों के लगभग 80% को हटा देता है।

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

Answer 5

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