2011-10-21 11 views
7

द्वारा अगर मैंमैप मान को एक्सेस करना सूचकांक

std::map<string, int> myMap; 
myMap["banana"] = 1; 
myMap["apple"] = 1; 
myMap["orange"] = 1; 

मैं myMap कैसे उपयोग कर सकते हैं की तरह एक संरचना है [0]?

मुझे पता है कि मानचित्र आंतरिक रूप से टाइप करता है और मैं इसके साथ ठीक हूं, मैं इंडेक्स द्वारा मानचित्र में एक मूल्य प्राप्त करना चाहता हूं। मैं myMap [0] की कोशिश की है, लेकिन मैं त्रुटि मिलती है:

Error 1 error C2679: binary '[' : no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion) 

मुझे पता है मैं कुछ इस तरह कर सकता है:

string getKeyAtIndex (int index){ 
    map<string, int>::const_iterator end = myMap.end(); 

    int counter = 0; 
    for (map<string, int>::const_iterator it = myMap.begin(); it != end; ++it) { 
     counter++; 

     if (counter == index) 
      return it->first; 
    } 
} 

लेकिन निश्चित रूप से यह बेहद अक्षम है? क्या कोई बेहतर तरीका है?

उत्तर

18

आपके map को इस तरह से एक्सेस नहीं किया जाना चाहिए, इसकी कुंजी द्वारा क्रमबद्ध नहीं है। map इटेटरेटर list की तरह बिडरेक्शनल है, इसलिए आप जिस फ़ंक्शन का उपयोग कर रहे हैं वह list को स्थिति से एक्सेस करने से अधिक अक्षम नहीं है। begin() से std::advance(iter, index) से आपकी सहायता के साथ आपका फ़ंक्शन लिखा जा सकता है। यदि आप स्थिति के आधार पर यादृच्छिक पहुंच चाहते हैं तो vector या deque का उपयोग करें।

2

अच्छा, वास्तव में आप नहीं कर सकते हैं। जिस तरह से आपको मिला वह बहुत अक्षम है, इसमें ओ (एन) (एन ऑपरेशन सबसे खराब मामला, जहां मानचित्र में तत्वों की संख्या है) की कम्प्यूटेशनल जटिलता है।

वेक्टर या किसी सरणी में किसी आइटम तक पहुंचने से तुलनात्मकता (निरंतर कम्प्यूटेशनल जटिलता, एक एकल ऑपरेशन) जटिलता ओ (1) होती है।

मान लें कि नक्शा आंतरिक रूप से लाल काले पेड़ (या एवीएल पेड़, यह कार्यान्वयन पर निर्भर करता है) के रूप में कार्यान्वित किया जाता है और प्रत्येक डालने, हटाने और लुकअप ऑपरेशन ओ (लॉग एन) सबसे खराब मामला है (इसे बेस 2 परिचालनों में लॉगरिदम की आवश्यकता होती है पेड़ में एक तत्व खोजने के लिए), यह काफी अच्छा है।

एक तरीका जिस तरह से आप निपट सकते हैं एक वेक्टर और नक्शा दोनों के अंदर एक कस्टम क्लास का उपयोग करना है। कक्षा के अंत में सम्मिलन औसत (ओ) होगा, नाम से लुकअप ओ (लॉग एन) होगा, इंडेक्स द्वारा लुकअप ओ (1) होगा, लेकिन इस मामले में, निष्कासन ऑपरेशन ओ (एन) होगा।

3

पिछला जवाब (टिप्पणी देखें): कैसे बस myMap.begin();

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

+0

मैं अब देखना है ... आप यादृच्छिक पहुंच चाहते हैं। सूचकांक 0 केवल एक उदाहरण था, वास्तविक लक्ष्य नहीं। –

2

आपके लक्ष्य को प्राप्त करने के लिए एक कार्यान्वयन विशिष्ट (गैर-पोर्टेबल) विधि हो सकती है, लेकिन पोर्टेबल नहीं है।

सामान्य रूप से, std::map को बाइनरी पेड़ के प्रकार के रूप में कार्यान्वित किया जाता है, आमतौर पर कुंजी द्वारा क्रमबद्ध किया जाता है। ऑर्डरिंग के आधार पर पहले तत्व की परिभाषा अलग-अलग होती है। इसके अलावा, आपकी परिभाषा में, तत्व [0] पेड़ के शीर्ष पर नोड या बाएं सबसे अधिक पत्ता नोड है?

कई बाइनरी पेड़ लिंक किए गए सूचियों के रूप में लागू किए जाते हैं। अधिकांश लिंक्ड सूचियों को सरणी की तरह सीधे एक्सेस नहीं किया जा सकता है, क्योंकि तत्व 5 खोजने के लिए, आपको लिंक का पालन करना होगा। यह परिभाषा के अनुसार है।

आप दोनों एक std::vector और एक std::map का उपयोग करके अपनी समस्या का समाधान कर सकते हैं:

  1. गतिशील स्मृति से वस्तु आवंटित करें।
  2. std::map में कुंजी के साथ पॉइंटर स्टोर करें।
  3. std::vector में पॉइंटर को उस स्थिति पर स्टोर करें जहां आप इसे पर चाहते हैं।

std::map कुंजी द्वारा ऑब्जेक्ट तक पहुंचने के लिए एक कुशल विधि की अनुमति देगा।
std::vector इंडेक्स द्वारा ऑब्जेक्ट तक पहुंचने के लिए एक कुशल विधि की अनुमति देगा। स्टोरेज पॉइंटर्स एकाधिक प्रतियों को बनाए रखने के बजाय ऑब्जेक्ट का केवल एक उदाहरण देता है।

+0

और फिर जब आप मानचित्र में कोई नया तत्व डालने की आवश्यकता हो तो वेक्टर के साथ क्या करते हैं? – HighCommander4

+0

मानचित्र के अलावा आपके मानचित्र पर इटरेटर के वेक्टर को स्टोर करना एक दिलचस्प विकल्प है। इस तरह, आप अपने मानचित्र के प्रत्येक तत्व की कुंजी और मूल्य दोनों को फिर से स्टोर किए बिना इंडेक्स द्वारा एक्सेस कर सकते हैं। बेशक, आपको अभी भी वेक्टर को मानचित्र में सिंक्रनाइज़ करने की आवश्यकता होगी - प्रविष्टि पर इटरेटर को संलग्न करें, हटाने से पहले इसे पुनरावृत्त (ओ (एन)) हटा दें। – namey

1

आप कंटेनर जैसे किसी अन्य मानचित्र का उपयोग कर सकते हैं।
एक आकार के फ़ील्ड रखें बाइनरी खोज पेड़ को यादृच्छिक पहुंच के लिए आसान बना सकते हैं।
यहाँ मेरी कार्यान्वयन ...
एसटीडी शैली, रैंडम एक्सेस इटरेटर ...
आकार संतुलित पेड़ ...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
और B + ट्री ...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h

+2

एसओ में आपका स्वागत है! केवल लिंक से बचने का प्रयास करें क्योंकि लिंक भविष्य में टूटा जा सकता है, बस उस लिंक के कुछ स्निपेट को अपने उत्तर में शामिल करें, आप लिंक को बनाए रख सकते हैं, लेकिन कृपया, अपने उत्तर पर कुछ और शामिल करें, और यह समझाने की कोशिश करें कि आप क्यों सोचते हैं एक अच्छा विचार। –

संबंधित मुद्दे