STL 다중 맵은 .NET 사전 <key, List <values>>과 어떻게 다른가요?

Question

키 당 여러 항목을 지원하는 .NET 사전이 필요한 곳에 문제가 있습니다. 과거에는 C++ 프로그램에서 STL 멀티 맵을 사용했습니다. 멀티 맵의 디자인은 성능, 크기 등 목록 사전 (제네릭 대 템플릿 제외)과 어떻게 다릅니 까?

Answer 1

multimap.count : O(log n + m) 여기서 n은 키의 수이고 m은 주어진 키와 관련된 항목의 수입니다.

Dictionary<TKey, List<TValue>>의 경우에 해당하는 기능은 다음과 같습니다

int count = dictionary[key].Count; 

그리고 안전은 조회 O(1)¹ 및 List<T>.Count이 O(1)입니다 때문에이 O(1) 작업입니다

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

말을하는 것입니다.

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 :이 방법에는 세 가지 오버로드가 있습니다. 나는 오직 하나의 키를 받아들이고 그 키의 모든 발생을 멀티 맵에서 제거하는 것을 고려할 것이다. 이것은 O(log n + m) 작업이고 n 키와 m 개체가 주어진 키와 연결됩니다.

Dictionary<TKey, List<TValue>>에 대해 동등한 기능 것 다음 documentation 가입일

dictionary.Remove(key); 

는 "이 방법은 O (1) 동작에 접근한다." 같은 코멘트가 적용됩니다.

: 문서에서 : "키를 사용하여 값을 검색하는 것이 매우 빠릅니다. O(1)에 가깝습니다." 이 시점에서 문서가 모호한 이유는 나에게 혼란을줍니다. 작업이 O(1)이거나 그렇지 않습니다. O(1)에는 "가까운"것이 없습니다.

Answer 2

어떤 종류의 키 클래스를 정의하고 Equals 및 GetHashCode 메서드를 재정의합니다. 그런 다음 사전의 핵심으로 사용할 수 있습니다 :

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 : 삽입/제거 작업은 로그 시간에 큰-O를 (로그 n), 조회는 일정 시간 큰-O을 받아 (1).

각 요소는 키 값을 사용하여 액세스됩니다. 맵과 달리 멀티 맵 키 값은 고유 할 필요가 없으며 연관된 값은 고유 할 필요가 없습니다. 맵은 키보다 작은 값을 비교하는 저장 함수 key_compare를 사용하여 요소를 정렬합니다.

Here's Big-O 성능 메트릭은 언급하지 않지만 사전을 사용하여 실제 실행을 제공하는 IDictionary 성능에 관한 기사입니다.