push_back या push_front एक डेक के इटरेटर को अमान्य क्यों करता है? शीर्षक के रूप में

Question

।

एक डेक की मेरी समझ यह थी कि इसे "ब्लॉक" आवंटित किया गया था। मैं नहीं देखता कि अधिक जगह आवंटित करने से इटरेटर्स को अमान्य कर दिया जाता है, और यदि कुछ भी हो, तो कोई ऐसा सोचता है कि एक डेक के इटरेटर को वेक्टर की तुलना में अधिक गारंटी होगी, कम नहीं।

Answer 1

सी ++ मानक निर्दिष्ट नहीं करता है कि डेक कैसे कार्यान्वित किया जाता है। नए हिस्से को आवंटित करके इसे पिछले स्थान पर आवंटित करने के लिए नई जगह आवंटित करने की आवश्यकता नहीं है, यह आवश्यक है कि प्रत्येक छोर पर सम्मिलन निरंतर समय को आवंटित किया जाए।

तो, डेक को कार्यान्वित करने के तरीके को देखना आसान है, जैसे कि यह गारंटी देता है [*], यह ऐसा करने का एकमात्र तरीका नहीं है।

[*] इटरेटर्स के पास एक तत्व का संदर्भ है, साथ ही ब्लॉक के संदर्भ में यह संदर्भ है ताकि वे ब्लॉक के सिरों को आगे बढ़कर आगे बढ़ सकें। इसके अलावा मुझे लगता है कि डेक के संदर्भ में, operator+ यादृच्छिक-पहुंच इटरेटर्स के लिए अपेक्षित समय के रूप में निरंतर समय हो सकता है - ब्लॉक से ब्लॉक तक लिंक की एक श्रृंखला के बाद पर्याप्त नहीं है।

Answer 2

जब भी आप भाग में आवंटित होते हैं, तब भी एक सम्मिलित होने पर उस विशेष खंड को फिर से स्थानांतरित किया जाएगा यदि पर्याप्त जगह नहीं है (जैसा वैक्टर के साथ मामला है)।

Answer 3

मुख्य बात यह है कि किसी भी धारणा को केवल इटरेटर के साथ नहीं माना जाता है जैसे कि इसे अमान्य कर दिया जाएगा।

भले ही यह ठीक काम करता है, फिर भी एक अलग मंच के लिए कंपाइलर या कंपाइलर का बाद का संस्करण साथ आ सकता है और आपका कोड तोड़ सकता है। वैकल्पिक रूप से, एक सहयोगी साथ आ सकता है और अपने डेक को वेक्टर या लिंक्ड सूची में बदलने का फैसला कर सकता है।

Answer 4

अधिक रूचिकर है कि push_back और push_frontनहीं एक Deque के तत्वों के लिए किसी भी संदर्भ अमान्य हो जाएगी है। केवल इटेटर को अमान्य माना जाना चाहिए।

मानक, मेरे ज्ञान के लिए, यह क्यों नहीं बताता है। हालांकि अगर एक पुनरावर्तक को कार्यान्वित किया गया था जो कि उसके तत्काल पड़ोसियों से अवगत था - एक सूची है - कि इटेटरेटर अमान्य हो जाएगा अगर यह उस तत्व को इंगित करता है जो डेक के किनारे और ब्लॉक के किनारे दोनों था।

Answer 5

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

कार्यान्वयनकर्ता जो कुछ भी चुनते हैं, उन्हें लागू करने के लिए स्वतंत्र हैं, जब तक कि यह उन सभी आवश्यकताओं को पूरा करता है। एक समझदार कार्यान्वयन भाग की सूचियों का उपयोग कर सकता है, या यह विभिन्न व्यापार-बंद के साथ किसी अन्य तकनीक का उपयोग कर सकता है।

यह कहना असंभव है कि एक तकनीक सभी परिस्थितियों में सभी उपयोगकर्ताओं के लिए सख्ती से बेहतर है। यही कारण है कि मानक कार्यान्वयन करने वालों को कुछ स्वतंत्रता चुनने देता है।

Answer 6

मेरा अनुमान है। push_back/push_front एक नया मेमोरी ब्लॉक आवंटित कर सकता है। एक डेक इटरेटर को पता होना चाहिए कि वृद्धि/कमी ऑपरेटर को अगले ब्लॉक में कूदना चाहिए। कार्यान्वयन उस जानकारी को इटेटरेटर में ही स्टोर कर सकता है। पुश_बैक/पुश_फ्रंट के बाद पुराने पुराने पुनरावर्तक को बढ़ाने/घटाने के उद्देश्य से काम नहीं कर सकता है।

यह कोड रन टाइम त्रुटि के साथ विफल हो सकता है या नहीं। मेरे विजुअल स्टूडियो पर यह डीबग मोड में विफल रहा लेकिन रिलीज मोड में निष्कर्ष पर चला गया। लिनक्स पर यह सेगमेंटेशन गलती हुई।

#include <iostream> 
#include <deque> 

int main() { 
    std::deque<int> x(1), y(1); 
    std::deque<int>::iterator iterx = x.begin(); 
    std::deque<int>::iterator itery = y.begin(); 

    for (int i=1; i<1000000; ++i) { 
     x.push_back(i); 
     y.push_back(i); 
     ++iterx; 
     ++itery; 
     if(*iterx != *itery) { 
      std::cout << "increment failed at " << i << '\n'; 
      break; 
     } 
    } 
} 

Answer 7

एक पुनरावर्तक डेटा का संदर्भ नहीं है। यह जानना चाहिए कि कैसे वृद्धि करना है, आदि

यादृच्छिक अभिगम का समर्थन करने के लिए, कार्यान्वयन में भाग के लिए पॉइंटर्स की गतिशील सरणी होगी। डेक इटरेटर इस गतिशील सरणी में इंगित करेगा। जब डेक बढ़ता है, तो एक नया हिस्सा आवंटित करने की आवश्यकता हो सकती है। गतिशील सरणी बढ़ेगी, इसके इटरेटर को अमान्य कर देगा और इसके परिणामस्वरूप, डेक के इटरेटर।

तो ऐसा नहीं है कि भाग को फिर से आवंटित किया गया है, लेकिन इन हिस्सों के पॉइंटर्स की सरणी हो सकती है। दरअसल, जोहान्स शैब ने नोट किया, संदर्भों को अवैध नहीं किया गया है।

यह भी ध्यान दें कि डेक की इटरेटर गारंटी वेक्टर की तुलना में कम नहीं है, जो कंटेनर बढ़ने पर भी अमान्य होती है।