गैर-संगत कंटेनर (जैसे कि std :: deque) के लिए यादृच्छिक एक्सेस इटरेटर कैसे कार्यान्वित किए जाते हैं?

Question

मैं समझता हूं कि कैसे यादृच्छिक एक्सेस iterators std :: vector जैसे संगत कंटेनर के लिए काम करते हैं: इटेटरेटर वर्तमान तत्व के लिए एक सूचक को बनाए रखता है और पॉइंटर पर कोई भी अतिरिक्त/घटाव लागू होता है। हालांकि, मैं इस बात से परेशान हूं कि गैर-संगत कंटेनर के लिए समान कार्यक्षमता कैसे कार्यान्वित की जा सकती है। मेरा पहला अनुमान है कि कैसे std :: deque: iterator काम करता है कि यह इसमें शामिल स्मृति के समूहों की कुछ तालिका में एक सूचक को बनाए रखता है, लेकिन मुझे यकीन नहीं है।

एक सामान्य मानक पुस्तकालय यह कैसे कार्यान्वित करेगा?

Answer 1

आप की आवश्यकता वाले संदेशों को std::vector<std::unique_ptr<std::array<T,N>>> के साथ लगभग संतुष्ट कर सकते हैं। प्लस एक निम्न/उच्च जल चिह्न आपको बताता है कि पहले/आखिरी तत्व कहां हैं। (एक कार्यान्वयन परिभाषित एन के लिए जो T के साथ भिन्न हो सकता है, और std::array एस वास्तव में सही ढंग से गठित अनियमित स्मृति के ब्लॉक हैं और std::array एस नहीं हैं, लेकिन आपको विचार मिलता है)।

सामान्य घातीय वृद्धि का उपयोग करें, लेकिन आगे और पीछे दोनों पर।

लुकअप बस ब्लॉक और उप तत्व खोजने के लिए (index+first)/N और %N करता है।

यह std::vector लुकअप से अधिक महंगा है, लेकिन ओ (1) है।

Answer 2

एक डेक इटरेटर को संदर्भित मान पर एक पॉइंटर और स्मृति के संगत ब्लॉक में एक डबल पॉइंटर संग्रहीत करके कार्यान्वित किया जा सकता है जिसमें वह मान स्थित है। डबल पॉइंटर डेक द्वारा प्रबंधित ब्लॉक के लिए पॉइंटर्स की एक संगत सरणी में इंगित करता है।

class deque_iterator 
{ 
    T* value; 
    T** block; 
    … 
} 

क्योंकि value और सन्निहित स्मृति में block बिंदु दोनों आपके पास इन कार्यों में इस तरह के लगातार समय (उदाहरण के libc से अनुकूलित ++) में iterators के बीच की दूरी को खोजने लागू कर सकते हैं।

difference_type operator-(deque_iterator const& x, deque_iterator const& y) 
{ 
    return (x.block - y.block) * block_size 
     + (x.value - *x.block) 
     - (y.value - *y.block); 
} 

ध्यान दें कि, जबकि value ऐसे push_front और push_back, के रूप में संचालन से अवैध नहीं की जाएगी block हो सकता है, जिसके कारण deque_iterator इस तरह के आपरेशनों से अवैध है।