क्या std :: map ज्ञात (और मानक द्वारा गारंटीकृत) के माध्यम से पुनरावृत्ति का क्रम है?

Question

मेरा मतलब है - हम जानते हैं कि std::map के तत्व कुंजी के अनुसार क्रमबद्ध होते हैं। तो, मान लीजिए कि चाबियाँ पूर्णांक हैं। यदि मैं std::map::begin() से std::map::end() से for का उपयोग कर पुन: प्रयास करता हूं, तो क्या मानक गारंटी है कि मैं परिणामस्वरूप क्रमशः कुंजी के साथ तत्वों के माध्यम से पुनरावृत्त करता हूं, आरोही क्रम में क्रमबद्ध करता हूं?

---

उदाहरण:

std::map<int, int> map_; 
map_[1] = 2; 
map_[2] = 3; 
map_[3] = 4; 
for(std::map<int, int>::iterator iter = map_.begin(); 
    iter != map_.end(); 
    ++iter) 
{ 
    std::cout << iter->second; 
} 

यह कार्यान्वयन परिभाषित किया गया है इस या 234 मुद्रित करने के लिए गारंटी है?

---

वास्तविक जीवन कारण: मैं एक int साथ std::map कुंजी है। बहुत दुर्लभ परिस्थितियों में, मैं सभी तत्वों के माध्यम से, एक ठोस int मान से अधिक कुंजी के साथ पुन: प्रयास करना चाहता हूं। हां, ऐसा लगता है कि std::vector बेहतर विकल्प होगा, लेकिन मेरी "बहुत दुर्लभ स्थितियों" पर ध्यान दें।

---

संपादित: मुझे पता है, कि std::map के तत्वों हल कर रहे हैं .. यह पता (उत्तर के अधिकांश के लिए यहाँ) बात करने के लिए कोई जरूरत नहीं। मैंने इसे अपने प्रश्न में भी लिखा है।
मैं एक कंटेनर के माध्यम से पुनरावृत्त कर रहा था जब मैं iterators और आदेश के बारे में पूछ रहा था। उत्तर के लिए धन्यवाद @ केरेक एसबी।

Answer 1

हां, यह गारंटी है।इसके अलावा, *begin() आपको तुलनात्मक ऑपरेटर द्वारा निर्धारित सबसे बड़ा तत्व और *rbegin() देता है, और दो प्रमुख मान a और b जिसके लिए अभिव्यक्ति !compare(a,b) && !compare(b,a) सत्य समान मानी जाती है। डिफ़ॉल्ट तुलना फ़ंक्शन std::less<K> है।

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

Answer 2

क्या यह 234 प्रिंट करने की गारंटी है या इसका कार्यान्वयन परिभाषित किया गया है?

हाँ, std::map एक क्रमबद्ध कंटेनर, आपूर्ति की Comparator साथ Key द्वारा आदेश दिया है। तो यह गारंटी है।

मैं सभी तत्वों के माध्यम से, एक ठोस int मूल्य से अधिक, कुंजी के साथ पुनरावृत्त करना चाहता हूं।

यह निश्चित रूप से संभव है।

Answer 3

हां ... std::map में तत्वों का सख्त कमजोर क्रम है, जिसका अर्थ है कि तत्व एक सेट से बने होंगे (यानी, "बराबर" कुंजी की कोई दोहराव नहीं होगी), और समानता किसी भी दो कुंजी ए और बी पर परीक्षण करके निर्धारित किया गया है कि यदि कुंजी ए कुंजी बी से कम नहीं है, और बी ए से कम नहीं है, तो कुंजी ए कुंजी बी के बराबर है।

कहा जा रहा है, आप ठीक से नहीं कर सकते std::map के तत्वों को सॉर्ट करें यदि उस प्रकार के कमजोर क्रम में संदिग्ध है (आपके मामले में, जहां आप कुंजी-प्रकार के रूप में पूर्णांक का उपयोग कर रहे हैं, यह कोई समस्या नहीं है)। आप एक ऐसे ऑपरेशन को परिभाषित करने में सक्षम होना चाहिए जो आपके std::map में कुंजियों के लिए उपयोग किए जाने वाले प्रकार के कुल क्रम को परिभाषित करता है, अन्यथा आपके पास केवल आपके तत्वों या पॉकेट के लिए आंशिक क्रम होगा, जिसमें संपत्ति हो सकती है जहां कोई तुलनीय नहीं हो सकता बी के लिए आम तौर पर इस परिदृश्य में क्या होगा, यह है कि आप कुंजी/मान जोड़ों को सम्मिलित करने में सक्षम होंगे, लेकिन यदि आप पूरे मानचित्र के माध्यम से पुन: प्रयास करते हैं, और/या "गायब" का पता लगाते हैं तो आप डुप्लिकेट कुंजी/मान जोड़ों के साथ समाप्त हो सकते हैं "कुंजी/मान जोड़े जब आप मानचित्र में किसी विशिष्ट कुंजी/मान जोड़ी के std::map::find() निष्पादित करने का प्रयास करते हैं।

Answer 4

मुझे लगता है कि डेटा संरचनाओं में भ्रम है।

अधिकांश भाषाओं में, map केवल एक सहयोगीकंटनर है: यह किसी मान के लिए कुंजी को मानचित्र करता है। "नई" भाषाओं में, यह आमतौर पर हैश मानचित्र का उपयोग करके हासिल किया जाता है, इस प्रकार कोई ऑर्डर गारंटी नहीं दी जाती है।

सी ++ में, हालांकि, यह नहीं इतना है:

• std::map एक अनुसार क्रमबद्ध साहचर्य कंटेनर
• std::unordered_map एक हैश तालिका आधारित साहचर्य कंटेनर में पेश सी ++ 11

है

तो, ऑर्डर करने पर गारंटी को स्पष्ट करने के लिए।

C++ में 03:

• std::set, std::multiset, std::map और std::multimap
std::multiset में
• और std::multimap, मानक कुंजी के अनुसार आदेश दिया जा करने के लिए गारंटी दी जाती है (और कसौटी आपूर्ति) समकक्ष तत्वों पर किसी ऑर्डर गारंटी (यानी, जो बराबर तुलना करते हैं)

सी ++ 11 में:

• std::set, std::multiset, std::map और std::multimap कुंजी के अनुसार आदेश दिया जा करने के लिए गारंटी दी जाती है (और कसौटी आपूर्ति) std::multiset में
• और std::multimap, स्टैंडर्ड लगाता कि बराबर तत्व (जो बराबर तुलना करते हैं) उनके प्रविष्टि आदेश (पहले पहले डाला गया) के अनुसार आदेश दिया जाता है
• std::unordered_* कंटेनर, जैसा कि नाम का अर्थ है, आदेश नहीं दिया गया है। सबसे विशेष रूप से, तत्वों का क्रम बदल सकता है जब कंटेनर संशोधित किया जाता है (सम्मिलन/हटाने पर)।

जब स्टैंडर्ड का कहना है कि तत्वों एक तरह से आदेश दिया जाता है, इसका मतलब है कि:

• जब बार-बार दोहराना, आप परिभाषित क्रम में तत्वों को देखने के
• रिवर्स के समय पुनरावृत्ति, आप देखते हैं विपरीत क्रम में तत्व

मुझे उम्मीद है कि यह किसी भी भ्रम को साफ़ कर देगा।

Answer 5

यह सी ++ मानक में सहयोगी कंटेनर आवश्यकताओं द्वारा गारंटीकृत है। जैसे देख 23.2.4/10 सी ++ 11 में:

 
The fundamental property of iterators of associative containers is that they 
iterate through the containers in the non-descending order of keys where 
non-descending is defined by the comparison that was used to construct them. 
For any two dereferenceable iterators i and j such that distance from i to j is 
positive, 
    value_comp(*j, *i) == false 

और 23.2.4/11

 
For associative containers with unique keys the stronger condition holds, 
    value_comp(*i, *j) != false.