C#에서 SortedDictionary를 올바르게 사용하는 방법은 무엇입니까?

Question

나는 아주 간단하게하려고하지만, 이해가 안되는 것 같습니다. SortedDictionary.

난 할 노력하고있어 않습니다 :
난 후 지금 일부 부동 번호로 내 항목을 정렬 정렬 된 사전을 만들고, 그래서이

SortedDictionary<float, Node<T>> allNodes = new SortedDictionary<float, Node<T>>(); 

과 같은 사전을 만들고 항목을 추가 할 때 하나씩 제거하고 싶습니다. 모든 제거 작업은 최소에서 최대까지 O (log (n))의 복잡성을 가져야합니다.

어떻게하면됩니까? 단순히 allNodes[0] 내게 가장 작은 것을 주겠지 만, 그렇지 않습니다.

이상의 내용은 사전이 중복 키를 처리 할 수없는 것처럼 보입니다. 내가 잘못된 데이터 구조를 사용하고있는 것 같은 느낌이 든다.
거리 (부동 소수점)로 정렬되고 싶은 노드가 있다면 다른 것을 사용해야합니까?

Answer 1

allNodes[0] 당신에게 사전의 첫 번째 항목을 제공하지 않습니다 - 그것은당신에게 아이템을 줄 것이다 0 키 값은 0입니다.

첫 번째 항목을 원하면 allNodes.Values.First()을 사용해보십시오. 또는 하나 하나 항목을 제거 allNodes.Keys.First()

의 첫 번째 키 사용을 찾으려면 사본 이상 루프는 Keys 수집과에 부록에 대답하기 위해 allNodes.Remove(key);

foreach (var key in allNodes.Keys.ToList()) 
{ 
    allNodes.Remove(key); 
} 

를 호출하여 질문, 예 SortedDictionary (그 점에 대해서는 Dictionary의 맛)은 중복 키를 처리하지 않습니다. 기존 키가있는 항목을 추가하려고하면 이 덮어 쓰기 가치가있다.

당신이 사용할 수있는 SortedDictionary<float, List<Node<T>>>하지만 당신은 각 목록을 초기화 에 필요보다는 그것은 모든 가능성 등의 항목을 추가하고 여전히 가장 빠른 구조 일 수 있으며, 컬렉션 항목 대을 추출의 복잡성을 추가하고 가져 오지만 약간의 복잡성이 추가됩니다.

Answer 2

Dictionary<TKey, TValue>에는 고유 키가 있어야하므로 대신 List<Node<T>>을 사용합니다. 예를 들어, 당신의 Node<T> 클래스는 Value 재산

class Node<T> 
{ 
    float Value { get; set; } 
    // other properties 
} 

을 가지고 있으며,이 속성을 기준으로 정렬 할 경우, LINQ를 사용

var list = new List<Node<T>>(); 

// populate list 

var smallest = list.OrderBy(n => n.Value).FirstOrDefault(); 

그냥 목록 던졌다 반복, 하나 하나의 노드를 제거하려면 :

while (list.Count > 0) 
{ 
    list.RemoveAt(0); 
} 

Answer 3

네, 바로 당신이 복잡합니다.

SortedDictionary에서 모든 키가 정렬됩니다.당신이 가장 큰 가장 작은에서 반복 할 경우, foreach 충분히있을 것입니다 : 당신은 당신이 항목을 제거 할 것을 썼다

foreach(KeyValuePair<float, Node<T>> kvp in allNodes) 
{ 
    // Do Something... 
} 

. foreach을 사용하여 반복 중에 컬렉션에서 제거하는 것은 금지되어 있으므로 먼저 복사본을 만듭니다.

편집 : 당신이 열쇠를 복제 한 경우

예, SortedDictionary을 사용할 수 없습니다. Node<T>와 float와 구조 노드 만들기, 후 비교자를 쓰기 : 다음

public class NodeComparer : IComparer<Node> 
{ 
    public int Compare(Node n1, Node n2) 
    { 
     return n2.dist.CompareTo(n1.dist); 
    } 
} 

그리고 일종의 간단한 List<Node> allNodes에 모든 것을 넣어 :

allNodes.Sort(new NodeComparer());