unordered_map में बिडरेक्शनल इटरेटर्स?

Question

निम्नलिखित न्यूनतम उदाहरण:

#include <iostream> 

#include <boost/unordered_map.hpp> 

int main() 
{ 
     boost::unordered_map<int, int> m; 
     boost::unordered_map<int, int>::const_iterator i; 

     m.insert(std::make_pair(1, 2)); 

     i = m.end(); 
     --i; 

     std::cout << i->first << " -> " << i->second << std::endl; 

     return 0; 
} 

... संकलित करने के लिए विफल रहता है।

bidi.cxx: In function ‘int main()’: 
bidi.cxx:13: error: no match for ‘operator--’ in ‘--i’ 

Boost's own documentation के अनुसार:

iterator, const_iterator कम से कम आगे श्रेणी के हैं।

ऐसा लगता है कि वे सब कुछ हैं। क्यूं कर? हैश-मैप किस तकनीकी प्रतिबंध को लगाता है जो इटरेटर को द्विपक्षीय होने से रोकता है?

(जीसीसी संस्करण 4.1.2, संस्करणों 1.40.0 और 1.43.0 बढ़ावा।)

Answer 1

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

आम तौर पर, एक तत्व-दर-तत्व आधार पर unordered_map तक पहुंच जाएगा, या पूरे मानचित्र को पार करेगा। मैंने कभी भी पर्ल में खुद को नहीं किया है। ऐसा करने के लिए, एक आगे इटेटरेटर आवश्यक है, और इसलिए वहां एक है, और बूस्ट इसकी गारंटी देता है। बिडरेक्शनल इटरेटर्स होने के लिए, प्रत्येक प्रविष्टि में एक अतिरिक्त सूचक शामिल करना आवश्यक होगा, जो स्मृति उपयोग और प्रसंस्करण समय को बढ़ाता है।

मैं यहां एक अच्छा, व्यावहारिक, उपयोग करने वाले मामले के साथ बिडरेक्शनल इटरेटर्स के लिए उपयोग नहीं कर रहा हूं। यदि आप कर सकते हैं, तो आप बूस्ट रखरखावकर्ताओं को इस पर विचार करने के लिए कह सकते हैं, हालांकि आप लगभग निश्चित रूप से सी ++ 0x के लिए बहुत देर हो चुकी हैं।