How is STL multi-frame different from .NET Dictionary <key, List <values ​​>>?

Question

I have a problem when I need a .NET dictionary that supports multiple items per key. I used to use multimap STL in my C ++ programs. How does a multimap design differ from a dictionary of lists, i.e. performance, size, etc. (Excluding common patterns and patterns)?

Answer 1

multimap.count : O(log n + m) where n is the number of keys and m is the number of elements associated with the given key.

With a Dictionary<TKey, List<TValue>> equivalent functionality would be:

 int count = dictionary[key].Count; 

And safer to say

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

This operation is O(1) , since the search is O(1) ¹ and List<T>.Count is O(1) .

multimap.find : O(log n) where n is the number of keys

With a Dictionary<TKey, List<TValue>> equivalent functionality would be:

 List<TValue> elements = dictionary[key]; 

And safer to say

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

This is O(1) . See the previous remark on key search in Dictionary<TKey, TValue> .

multimap.insert : O(log n) where n is the number of keys.

With a Dictionary<TKey, List<TValue>> equivalent functionality would be:

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

Usually this is O(1) , but it can be O(n) , when the dictionary capacity should be increased to accommodate a new element.

multimap.remove : There are three overloads of this method; I will only consider one that accepts the key and removes all occurrences of this key from the multimap. This is O(log n + m) operation, where the keys n and m are associated with the given key.

With a Dictionary<TKey, List<TValue>> equivalent functionality would be:

  dictionary.Remove(key); 

From the documentation : "This method is suitable for operation O (1)." The same comment is used.

¹ : From the documentation: "Getting the value using its key is very fast, close to O(1) ." Why the documentation is vague on this issue bothers me. Either operation O(1) or not. There is no such thing as "close" for O(1) .

Answer 2

MultiMap: inserts / deletes are performed using the Big-O logarithmic time (log n), the search takes a constant Big-O time (1).

Access to each element is carried out using the key value, unlike the card, the key value of the multimap should not be unique, the associated values ​​need not be unique. The map sorts items by their keys using the stored key_compare function, which simply does less than compare.

Here is an IDictionary performance article that does not mention Big-O performance metrics, but provides some practical vocabulary runs using the dictionary.

Answer 3

Define a key class and override its Equals and GetHashCode methods. Then you can use it as a key in the dictionary:

 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;