STL multimap如何与.NET Dictionary <key,List <values >>不同？

Question

我有一个问题,我需要一个支持每个键多个项目的.NET字典.在过去,我在我的C++程序中使用了STL multimap.多图的设计与列表字典(即性能,大小等)有何不同(不包括泛型与模板)？

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)操作，因为 Lookup 是O(1)¹并且List<T>.Count是O(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)。请参阅前面关于在 a 中按键查找的评论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：该方法有3个重载；我只会考虑接受一个键并从多重映射中删除该键的所有出现的那个。这是一个键和对象与给定键关联的O(log n + m)操作。nm

对于一个Dictionary<TKey, List<TValue>>等效的功能将是：

 dictionary.Remove(key);

来自文档：“此方法接近 O(1) 操作。” 同样的评论也适用。

¹：来自文档：“使用其键检索值非常快，接近O(1)。” 为什么文档在这一点上含糊不清让我感到困惑。一个操作要么是O(1)，要么不是。不存在“接近”这样的事情O(1)。