合併兩個SortedLists

Question

var h1 = SortedList { 
    {"one", 1}, 
    {"two", 2} 
}; 

var h2 = SortedList { 
    {"two", 22}, 
    {"three", 3} 
}; 

如何以慣用方式實現h3以{"one", 1},{"two", 2},{"three", 3}結尾？

Answer 1

您提供的示例數據有點奇怪，因爲密鑰「three」通常會在密鑰「two」之前排序。因此，我將假設在排序列表中的鍵的常規字符串比較適用於此答案。

下面的方法提供了合併算法，使用將元素添加到輸出時先進的枚舉器。如果列表包含具有相同鍵的元素，則將該值作爲聯繫斷路器進行比較。

public static IEnumerable<KeyValuePair<K, V>> MergeSortedLists<K, V>(
    SortedList<K, V> l1, 
    SortedList<K, V> l2) 
    where K : IComparable 
    where V : IComparable 
{ 
    using (var l1Iter = l1.GetEnumerator()) 
    using (var l2Iter = l2.GetEnumerator()) 
    { 
     var morel1 = l1Iter.MoveNext(); 
     var morel2 = l2Iter.MoveNext(); 
     while (morel1 || morel2) 
     { 
      if (!morel1) 
      { 
       yield return l2Iter.Current; 
       morel2 = l2Iter.MoveNext(); 
      } 
      else if (!morel2) 
      { 
       yield return l1Iter.Current; 
       morel1 = l1Iter.MoveNext(); 
      } 
      else 
      { 
       var cmp = l1.Comparer.Compare(l1Iter.Current.Key, l2Iter.Current.Key); 
       if (cmp < 0) 
       { 
        yield return l1Iter.Current; 
        morel1 = l1Iter.MoveNext(); 
       } 
       else if (cmp > 0) 
       { 
        yield return l2Iter.Current; 
        morel2 = l2Iter.MoveNext(); 
       } 
       else // keys equal: use value to break tie. 
       { 
        if (l1Iter.Current.Value.CompareTo(l1Iter.Current.Value) <= 0) 
         yield return l1Iter.Current; 
        else 
         yield return l2Iter.Current; 
        // or if l1 takes precedence, replace above 4 lines with: 
        // yield return l1Iter.Current; 
        morel1 = l1Iter.MoveNext(); 
        morel2 = l2Iter.MoveNext(); 
       } 
      } 
     } 
    } 
} 

用例：

public static void Main(params string[] args) 
{ 
    // Note: this is not an idiomatic way to instantiate sorted lists. 
    var h1 = new SortedList<string, int>() { 
     { "one", 1 }, 
     { "two", 2 } 
    }; 
    var h2 = new SortedList<string, int>() { 
     { "three", 3 }, // because "three" < "two" 
     { "two", 22 } 
    }; 
    var h3 = MergeSortedLists(h1, h2); 
    Console.WriteLine(string.Join(", ", h3.Select(e => string.Format("{{{0}, {1}}}", e.Key, e.Value)))); 
    // Outputs: 
    // {one, 1}, {three, 3}, {two, 2} 
} 

注意，這將是一個有點更地道的C＃，使這個擴展方法名稱類似MergeWith，因此，它可以被稱爲

var h3 = h1.MergeWith(h2); 

Answer 2

SortedList可以接受IDictionary，你可以使用一個構造函數的參數此解決辦法克服自己的問題

class Program 
{ 
    private static void Main(string[] args) 
    { 
     var h1 = new SortedList<string, int>(); 
      h1.Add("One", 1); 
      h1.Add("Two", 2); 
     var h2 = new SortedList<string, int>(); 
      h2.Add("One", 1); 
      h2.Add("Two", 22); 
      h2.Add("Three", 3); 
     var unDict = h1.Union(h2).Distinct(new SortedListComparer()).ToDictionary(d=>d.Key,v=>v.Value); 

     SortedList<string,int> finSortedList = new SortedList<string,int>((IDictionary<string,int>)unDict,StringComparer.InvariantCultureIgnoreCase); 
    } 
} 

class SortedListComparer:EqualityComparer<KeyValuePair<string,int>> 
{ 

    public override bool Equals(KeyValuePair<string, int> x, KeyValuePair<string, int> y) 
    { 
     return x.Key == y.Key; 
    } 

    public override int GetHashCode(KeyValuePair<string, int> obj) 
    { 
     return obj.Key.GetHashCode(); 
    } 
} 

我知道這是不是成語，但你可以嘗試一下; 亞特所有SortedList實施IDictionary

public class SortedList<TKey, TValue> : IDictionary<TKey, TValue> 

Answer 3

一些僞得到一個算法下來。

假設你可以遍歷這些列表：

var h3 = new SortedList; 
var ptrA, ptrB, ptrC = 0; 

while(ptrA ! h1.length && ptrB ! h2.length){ 

    if(h1.ptrA.key < h2.ptrB.key){ 
      h3.ptrC.key = h1.ptrA.key; 
      h3.ptrC.value = h1.ptrA.key; 
      ptrA++; 
      ptrC++; 
     } 
    else if(h1.ptrA.key > h2.ptrB.key){ 
      h3.ptrC.key = h2.ptrB.key; 
      h3.ptrC.value = h2.ptrB.key; 
      ptrB++; 
      ptrC++; 
     } 
    else if(h1.ptrA.key == h2.ptrB.key){ 
      h3.ptrC.key = h1.ptrA.key; 
      h3.ptrC.value = h1.ptrA.key; 
      ptrA++; 
      ptrB++; 
      ptrC++; 
      } 
} 

也許我的同事們有一個更好的方法或可能還有一些補充，這個相當強力的方法。

這裏的概念很簡單，因爲我們爲每個列表增加一些指針，我們在這個位置上鎖定鍵。取決於我們所發現的決定哪個鍵被寫入列表。如果我們找到相同的對，那麼我們從列表A中取值，並增加所有指針，從而有效地留下與列表B中的鍵匹配的值。

Answer 4

我花了一點自由讓你的問題在LinqPad4中工作。
基本上，就像你所擁有的一樣。創建兩個集合（列表<>這裏），然後一起加入差異。

var h1 = new List<Tuple<string,int>>(); 
h1.Add(new Tuple<string,int>("one",1)); 
h1.Add(new Tuple<string,int>("two",2)); 

var h2 = new List<Tuple<string,int>>(); 
h2.Add(new Tuple<string,int>("two", 22)); 
h2.Add(new Tuple<string,int>("three",3)); 

var h3 = from a in h2 
     where !(from b in h1 select b.Item1).Contains(a.Item1) 
     select a; 

h1.AddRange(h3); 

h1.Dump(); 

LinqPad4代碼鏈接。 http://share.linqpad.net/soivue.linq