c# - STL multimap 与 .NET Dictionary> 有何不同？

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)操作，因为查找是 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) .请参阅之前关于在 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)哪里有操作n键和 m对象与给定键关联。

对于 Dictionary<TKey, List<TValue>>等效的功能是:

 dictionary.Remove(key);

来自documentation :“此方法接近 O(1) 操作。”同样的评论适用。

¹:来自文档:“使用其键检索值非常快，接近于 O(1)。”为什么文档在这一点上含糊不清让我感到困惑。任一操作都是 O(1)或者不是。 O(1) 没有“接近”之类的东西.