C++ std :: iterator ऑर्डर के बारे में मानचित्र प्रश्न

Question

मैं एक सी ++ नौसिखिया हूं जो मानचित्र का उपयोग करने की कोशिश कर रहा है, इसलिए मुझे ढूंढ() विधि के लिए निरंतर समय लुकअप मिल सकता है।

समस्या यह है कि जब मैं मानचित्र में तत्वों पर जाने के लिए एक इटरेटर का उपयोग करता हूं, तो तत्व उसी क्रम में प्रकट नहीं होते हैं जो उन्हें मानचित्र में रखा गया था।

एक और डेटा संरचना बनाए रखने के बिना, निरंतर समय की लुकअप क्षमता को बनाए रखने के दौरान पुनरावृत्ति क्रम में प्राप्त करने का कोई तरीका है?

कृपया मुझे बताएं।

धन्यवाद, jbu

संपादित करें: दे मुझे नक्शा :: लगता है पता() के लिए धन्यवाद निरंतर समय नहीं है।

Answer 1

आइटम पर लागू होने पर आइटम operator< (डिफ़ॉल्ट रूप से) द्वारा आदेश दिए जाते हैं।

पीएस। std :: नक्शा निरंतर समय की तलाश नहीं करता है।
यह gurantees ओ (एलएन (एन)) की अधिकतम जटिलता

Answer 2

सबसे पहले, std::map निरंतर समय की तलाश नहीं है। यह ओ (लॉग एन) है। बस सोचा कि मुझे इसे सीधे सेट करना चाहिए।

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

Answer 3

सबसे पहले, std::map ओ (लॉग एन) लुकअप समय की गारंटी देता है। आप std::tr1::unordered_map के बारे में सोच रहे होंगे। लेकिन परिभाषाओं द्वारा निरंतर समय के लुकअप को प्राप्त करने के लिए किसी भी आदेश को त्याग दिया जाता है।

आपको उस पर कुछ समय बिताना होगा, लेकिन मुझे लगता है कि आप जो चाहते हैं उसे करने के लिए boost::multi_index_container को बाँध सकते हैं।

Answer 4

कोई अन्य डेटा संरचना बनाए रखने के बिना, निरंतर समय की लुकअप क्षमता को बनाए रखने के दौरान पुनरावृत्ति के क्रम में प्राप्त करने का कोई तरीका है?

नहीं, यह संभव नहीं है। एक कुशल लुकअप प्राप्त करने के लिए, कंटेनर को सामग्री को ऐसे तरीके से ऑर्डर करने की आवश्यकता होगी जो कुशल लुकअप को संभव बनाता है। Std :: मानचित्र के लिए, यह कुछ प्रकार का क्रमबद्ध क्रम होगा; std :: unordered_map के लिए, यह कुंजी के हैश के आधार पर एक आदेश होगा।

किसी भी मामले में, ऑर्डर अलग होगा, जिस क्रम में उन्हें जोड़ा गया था।

Answer 5

नक्शा कुछ क्रम में तत्व रखने के लिए नहीं है - इसके लिए वेक्टर का उपयोग करें।

आप उपयोग कर [ऑपरेटर

तुम दोनों की जरूरत है नक्शे में कुछ आप कुंजी द्वारा "खोज" चाहिए पता लगाना चाहते हैं: यात्रा और कुंजी के आधार पर खोज इस topic

Answer 6

मैं जा रहा हूँ देखना वास्तव में ... पिछड़े जाओ।

आप जिस क्रम में तत्वों डाला गया, या सामान्य रूप में आदेश को नियंत्रित करने को संरक्षित करना चाहते हैं, तो आप एक दृश्य की जरूरत है कि आप को नियंत्रित करेगा:

• std::vector (हाँ वहाँ दूसरों रहे हैं, लेकिन डिफ़ॉल्ट रूप से std::find(vec.begin(), vec.end(), value);: वेक्टर में एक विशेष मूल्य के लिए खोज करने के लिए यह एक)

आप std::find एल्गोरिथ्म (<algorithm> से उपयोग कर सकते हैं) का उपयोग करें।

अरे हाँ, यह रैखिक जटिलता O(N) है, लेकिन छोटे संग्रहों के लिए यह कोई बात नहीं करना चाहिए।

अन्यथा, आप Boost.MultiIndex के रूप में पहले से ही सुझाव पर तलाश शुरू कर सकते हैं, लेकिन अभी शुरुआत के लिए आप शायद थोड़ा संघर्ष करेंगे।

तो, इस पल के लिए जटिलता मुद्दे को हिलाएं, और काम करने वाली किसी चीज़ के साथ आओ। जब आप भाषा से अधिक परिचित हों तो आप गति के बारे में चिंता करेंगे।

Answer 7

हाँ आप इस तरह के एक डेटा संरचना बना सकते हैं, लेकिन मानक पुस्तकालय का उपयोग नहीं ... कारण यह है कि मानक कंटेनर नेस्ट किया जा सकता है लेकिन नहीं मिलाया जा सकता है।

उदाहरण के लिए नक्शा डेटा संरचना लागू करने में कोई समस्या नहीं है, जहां सम्मिलन के क्रम में सभी नोड्स दोगुनी लिंक्ड सूची में हैं, या उदाहरण के लिए एक मानचित्र जहां सभी नोड सरणी में हैं। यह मेरे लिए इन संरचनाओं में से एक हो सकता है कि आप (निर्भर करता है जो आपरेशन आप तेजी से होने के लिए पसंद करते हैं) जो खोज रहे हैं लगता है, लेकिन उनमें से कोई भी मानक कंटेनरों का इस्तेमाल किया निर्माण करने के लिए मामूली बात है, क्योंकि हर मानक कंटेनर (vector, list, set, ...) निहित तत्वों तक पहुंचने का एकमात्र तरीका बनना चाहता है।

उदाहरण के लिए मुझे कई मामलों में उपयोगी पाया गया है जो एक साथ कई दोगुनी-लिंक्ड सूचियों में नोड्स थे, लेकिन आप std::list का उपयोग करके ऐसा नहीं कर सकते हैं।

Answer 8

मूल क्रम में कुंजी के लिए vector और डेटा के तेज़ पहुंच के लिए map का उपयोग करने के बारे में क्या?

कुछ इस तरह:

vector<string> keys; 
map<string, Data*> values; 

// obtaining values 
... 
keys.push_back("key-01"); 
values["key-01"] = new Data(...); 
keys.push_back("key-02"); 
values["key-02"] = new Data(...); 
... 

// iterating over values in original order 
vector<string>::const_iterator it; 
for (it = keys.begin(); it != keys.end(); it++) { 
    Data* value = values[*it]; 
}