एक एसटीएल मल्टीमैप एक .NET शब्दकोश <कुंजी, सूची <values>> से भिन्न कैसे है?

Question

मुझे एक समस्या है जहां मुझे एक .NET शब्दकोश की आवश्यकता है जो प्रति कुंजी एकाधिक आइटम का समर्थन करता है। अतीत में मैंने अपने सी ++ कार्यक्रमों में एसटीएल मल्टीमैप का उपयोग किया है। मल्टीमैप का डिज़ाइन सूचियों के शब्दकोश यानी प्रदर्शन, आकार इत्यादि से अलग कैसे होता है (जेनेरिक बनाम टेम्पलेट को छोड़कर)?

Answer 1

multimap.count: O(log n + m) जहां n कुंजी की संख्या है और m किसी दिए गए कुंजी से जुड़े आइटमों की संख्या है।

एक Dictionary<TKey, List<TValue>> के लिए बराबर कार्यक्षमता होगा:

int count = dictionary[key].Count; 

और सुरक्षित

int count; 
List<TValue> list; 
if(dictionary.TryGetValue(key, out list)) { 
    int count = list.Count; 
} 

कहने के लिए यह एक O(1) आपरेशन क्योंकि देखने O(1) और List<T>.CountO(1) है है।

multimap.find: O(log n) जहां n कुंजी

एक Dictionary<TKey, List<TValue>> के लिए की संख्या बराबर कार्यक्षमता होगा:

List<TValue> elements = dictionary[key]; 

और सुरक्षित कहने के लिए

List<TValue> list; 
if(dictionary.TryGetValue(key, out list)) { 
    // safe to iterate list 
} 

यह O(1) है। Dictionary<TKey, TValue> में कुंजी द्वारा लुकअप पर पिछली टिप्पणी देखें।

multimap.insert: O(log n) जहां n कुंजी की संख्या है।

एक Dictionary<TKey, List<TValue>> के लिए बराबर कार्यक्षमता होगा:

// value is TValue to insert 
List<TValue> list; 
if(!dictionary.TryGetValue(key, out list)) { 
    list = new List<TValue>(); 
    dictionary.Add(key, list); 
} 
list.Add(value); 

यह आमतौर पर O(1) है, लेकिन O(n) हो सकता है जब शब्दकोश की क्षमता नए तत्व को समायोजित करने के वृद्धि की जानी चाहिए।

multimap.remove: इस विधि के तीन अधिभार हैं; मैं केवल उस व्यक्ति पर विचार करूंगा जो एक कुंजी स्वीकार करता है और उस कुंजी की सभी घटनाओं को मल्टीमैप से हटा देता है। यह O(log n + m) ऑपरेशन है जहां n कुंजी और m ऑब्जेक्ट्स किसी दिए गए कुंजी से संबद्ध होते हैं।

एक Dictionary<TKey, List<TValue>> के लिए बराबर कार्यक्षमता होगा:

dictionary.Remove(key); 

documentation से: "इस विधि एक हे (1) आपरेशन दृष्टिकोण।" वही टिप्पणी लागू होती है।

: प्रलेखन से: "इसकी कुंजी का उपयोग करके एक मूल्य पुनर्प्राप्त करना बहुत तेज है, O(1) के करीब।" इस बिंदु पर दस्तावेज अस्पष्ट क्यों है मुझे भ्रमित कर रहा है। या तो एक ऑपरेशन O(1) है या यह नहीं है। O(1) पर "बंद" जैसी कोई चीज़ नहीं है।

Answer 2

किसी प्रकार की कुंजी श्रेणी को परिभाषित करें और इसके बराबर और GetHashCode विधियों को ओवरराइड करें। तो फिर तुम एक शब्दकोश में एक महत्वपूर्ण के रूप में उपयोग कर सकते हैं:

class MyKey : IEquatable<MyKey> 
{ 
    public int x; 
    public string y; 


    public bool Equals(MyKey other) 
    { 
     return other != null && x == other.x && y == other.y; 
    } 

    public override int GetHashCode() 
    { 
     return x.GetHashCode()^y.GetHashCode(); // for example 
    } 
} 


Dictionary<MyKey, Foo> dict; 

Answer 3

मल्टीमैप: सम्मिलित/हटाने के संचालन लघुगणक समय बिग-ओ (लॉग एन), देखने ले निरंतर समय बिग-ओ ले (1)।

मानचित्र के विपरीत, प्रत्येक तत्व को एक महत्वपूर्ण मान का उपयोग करके एक्सेस किया जाता है, एक मल्टीमैप कुंजी मान अद्वितीय नहीं होना चाहिए, संबंधित मानों को अद्वितीय होने की आवश्यकता नहीं है। नक्शा तत्वों को उनके कुंजी द्वारा संग्रहित फ़ंक्शन key_compare का उपयोग करके ऑर्डर करता है, जो तुलनात्मक रूप से कम से कम करता है।

Here's आईडीकी प्रदर्शन पर एक लेख जो किसी भी बिग-ओ प्रदर्शन मीट्रिक का उल्लेख नहीं करता है लेकिन शब्दकोश का उपयोग करके कुछ व्यावहारिक रन देता है।