सेट <pair> और सी ++ में मानचित्र के बीच क्या अंतर है?

Question

दो तरीके हैं जिनमें मैं सी ++ एसटीएल में आसानी से एक कुंजी, मूल्य विशेषता बना सकता हूं: मानचित्र और जोड़ों के सेट। उदाहरण के लिए, मैं

map<key_class,value_class> 

या

set<pair<key_class,value_class> > 

एल्गोरिथ्म जटिलता और कोडिंग शैली के संदर्भ में हो सकता है, इन प्रयोगों के बीच मतभेद क्या हैं?

Answer 1

सेट तत्वों के लिए एक से अधिक मान की अनुमति देगा होगा। set के iterator और const_iterator समकक्ष हैं। इसलिए, set<pair<key_class,value_class> > के साथ, आप value_class इन-जगह को संशोधित नहीं कर सकते हैं। आपको सेट से पुराने मान को हटाना होगा और नया मान जोड़ना होगा। हालांकि, अगर value_class एक सूचक है, तो यह आपको उस ऑब्जेक्ट को संशोधित करने से नहीं रोकता है जो इसे इंगित करता है।

map<key_class,value_class> के साथ, आप value_class को जगह में संशोधित कर सकते हैं, मानते हैं कि आपके पास मानचित्र के लिए गैर-कॉन्स्ट संदर्भ है।

Answer 2

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

दोनों आम तौर पर एक ही डेटा संरचना (आमतौर पर एक लाल-काले संतुलित बाइनरी पेड़) के साथ लागू होते हैं, इसलिए दोनों के लिए जटिलता समान होनी चाहिए।

Answer 3

वे अर्थात् अलग हैं। पर विचार करें:

#include <set> 
#include <map> 
#include <utility> 
#include <iostream> 

using namespace std; 

int main() { 
    pair<int, int> p1(1, 1); 
    pair<int, int> p2(1, 2); 
    set< pair<int, int> > s; 
    s.insert(p1); 
    s.insert(p2); 
    map<int, int> m; 
    m.insert(p1); 
    m.insert(p2); 
    cout << "Set size = " << s.size() << endl; 
    cout << "Map size = " << m.size() << endl; 
} 

http://ideone.com/cZ8Vjr

आउटपुट:

सेट आकार = 2
मानचित्र आकार = 1

Answer 4

map<key_class,value_class> key_class पर सॉर्ट और key_class का कोई डुप्लिकेट की अनुमति देगा।
set<pair<key_class,value_class> > key_class पर सॉर्ट और फिर value_class अगर key_class उदाहरणों के बराबर हैं, और जब वे सेट में हैं बदला नहीं जा सकता key_class

Answer 5

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

ए std::set<pair<K,V> > इस तरह काम करने के लिए बनाया जा सकता है, लेकिन आपको मूल्य को संशोधित करने के लिए एक कुंजी और अधिक कोड का उपयोग करके क्वेरी के लिए अतिरिक्त कोड लिखना होगा (यानी पुरानी जोड़ी को हटाएं और एक ही कुंजी के साथ दूसरे को डालें और एक अलग मूल्य)। आपको यह भी सुनिश्चित करना होगा कि एक ही कुंजी के साथ दो से अधिक मूल्य नहीं हैं (आपने अनुमान लगाया है, अधिक कोड)।

दूसरे शब्दों में, आप std::map जैसे काम करने के लिए जूता-सींग को std::set करने का प्रयास कर सकते हैं, लेकिन इसका कोई कारण नहीं है।

Answer 6

एल्गोरिदमिक जटिलता को समझने के लिए, आपको पहले कार्यान्वयन को समझने की आवश्यकता है।

std :: नक्शा आरबी-पेड़ का उपयोग करके कार्यान्वित किया गया है जहां हैश_मैप को लिंक की गई सूची के सरणी का उपयोग करके लागू किया गया है। std :: नक्शा ओ (लॉग (एन)) को डालने/हटाने/खोज ऑपरेशन के लिए प्रदान करता है, हैश_मैप ओ (1) हैश टकराव के आधार पर सबसे अच्छा मामला है और ओ (एन) सबसे अच्छा मामला है।

Answer 7

विज्युअलाइजिंग अर्थ अंतर फिलिप कोड के माध्यम से कदम के बाद कहा कि, ध्यान दें कैसे मानचित्र कुंजी एक स्थिरांक पूर्णांक है और कैसे p2 मीटर में सम्मिलित नहीं किया गया था: