Wie unterscheidet sich ein STL-Multimap von einem .NET-Wörterbuch <Schlüssel, Liste <values>>?

Question

Ich habe ein Problem, wo ich ein .NET-Wörterbuch, das mehrere Elemente pro Schlüssel unterstützt. In der Vergangenheit habe ich die STL-Multimap in meinen C++ - Programmen verwendet. Wie unterscheidet sich das Design einer Multimap von einem Wörterbuch mit Listen, z. B. Leistung, Größe usw. (ausgenommen Generika und Vorlagen)?

Answer 1

multimap.count: O(log n + m) wo n ist Anzahl der Tasten und m ist die Anzahl der Einzelteile mit einem bestimmten Schlüssel zugeordnet ist.

Für eine Dictionary<TKey, List<TValue>> die entsprechende Funktionalität wäre:

int count = dictionary[key].Count; 

und sicherer ist

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

Dies ist ein O(1) Operation zu sagen, weil Lookup O(1) und List<T>.CountO(1) ist.

multimap.find: O(log n) wo n ist Anzahl der Tasten

Für eine Dictionary<TKey, List<TValue>> die entsprechende Funktionalität wäre:

List<TValue> elements = dictionary[key]; 

und sicherer ist

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

Diese O(1) zu sagen. Siehe die vorherige Bemerkung zum Nachschlagen nach Schlüssel in einer Dictionary<TKey, TValue>.

multimap.insert: O(log n) wobei n die Anzahl der Schlüssel ist.

Für eine Dictionary<TKey, List<TValue>> die entsprechende Funktionalität wäre:

// 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); 

Diese Regel O(1) ist, kann aber O(n) sein, wenn die Kapazität des Wörterbuchs erhöht werden muss, das neue Element zu empfangen.

multimap.remove: Es gibt drei Überladungen dieser Methode; Ich werde nur diejenige in Betracht ziehen, die einen Schlüssel akzeptiert und alle Vorkommen dieses Schlüssels aus der Multimap entfernt. Dies ist eine O(log n + m) Operation, bei der n Schlüssel und m Objekte mit einem bestimmten Schlüssel verknüpft sind.

Für ein Dictionary<TKey, List<TValue>> die äquivalente Funktionalität wäre:

dictionary.Remove(key); 

Vom documentation: "Das Verfahren nähert sich einen O (1) Betrieb." Gleicher Kommentar gilt.

: Aus der Dokumentation: "Das Abrufen eines Werts mithilfe seines Schlüssels ist sehr schnell, in der Nähe von O(1)." Warum die Dokumentation in diesem Punkt vage ist, ist für mich verwirrend. Entweder ist eine Operation O(1) oder nicht. Es gibt kein "nahes" zu O(1).

Answer 2

Definieren Sie eine Art von Schlüsselklasse und überschreiben Sie deren Methoden Equals und GetHashCode. Dann können Sie es als Schlüssel in einem Wörterbuch verwenden:

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

multimap: Ziehen-/Operationen nehmen logarithmischer Zeit Big-O (log n), Nachschlag nehmen konstante Zeit Big-O (1).

Auf jedes Element wird mit einem Schlüsselwert zugegriffen, im Gegensatz zur Map muss ein Multimap-Schlüsselwert nicht eindeutig sein, zugehörige Werte müssen nicht eindeutig sein. Die Karte ordnet die Elemente mit ihren Schlüsseln unter Verwendung einer gespeicherten Funktion key_compare an, die einfach einen weniger als einen Vergleich durchführt.

Here's ein Artikel über IDictionary-Leistung, der keine Big-O-Leistungsmetriken erwähnt, aber einige praktische Läufe mit dem Wörterbuch gibt.