我有一个问题,需要一个支持一个键对应多个值的.NET字典。过去我在C++程序中使用了STL multimap。一个multimap的设计与一个列表字典有何不同,例如性能、大小等(不包括泛型与模板)?
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)
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)
。请参见之前在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
:此方法有三个重载;我只考虑接受键并从multimap中删除该键的所有出现的那个。这是一个O(log n + m)
操作,其中n
个键和m
个对象与给定键相关联。
对于Dictionary<TKey,List<TValue>>
,等效的功能将是:
dictionary.Remove(key);
O(1)
。"为什么文档在这一点上含糊不清让我感到困惑。要么一个操作是O(1)
,要么就不是。不存在所谓的“接近于O(1)
”。multimap(多重映射): 插入/删除操作的时间复杂度是对数级别 Big-O(log n), 查找操作的时间复杂度是常数级别 Big-O(1)。
每个元素都使用一个键值访问,与map不同,multimap的键值不需要唯一,相关联的值也不需要唯一。map使用存储函数key_compare按照其键值对元素进行排序,该函数简单地执行小于比较。
这里有一篇关于IDictionary性能的文章,没有提及任何Big-O性能指标,但是给出了一些使用字典实际运行的经验。
IDictionary
的文档没有提到任何渐近指南;接口不能要求所有实现者满足某些渐近性能要求。此外,从Dictionary<TKey, TValue>
的文档中可以看出:“如果Count
小于容量,则 [Add
] 方法是一个接近O(1)
的操作。如果必须增加容量以容纳新元素,则此方法成为一个O(n)
操作,其中n
是Count
。”此外,“使用键检索值非常快,接近O(1)
。” 为什么他们在最后一点上含糊不清我不明白。 - jason