合并两个排序列表

Question

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

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

如何以惯用的方式实现 h3 以 {"one", 1},{"two", 2},{"three", 3} 结束？

Answer 1

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 2

一些伪代码来降低算法。

假设您可以遍历这些列表：

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 3

我冒昧地让你的问题在 LinqPad4 中有效。
基本上，和你拥有的一样。创建两个集合（此处为 List<>），然后将差异合并在一起。

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 link 代码。 http://share.linqpad.net/soivue.linq

Answer 4

您提供的示例数据有点奇怪，因为键 "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}
}

请注意，将此扩展方法命名为类似于 MergeWith 的扩展方法会更符合 C# 的习惯，这样它就可以被称为

var h3 = h1.MergeWith(h2);

合并两个排序列表

Merging Two SortedLists

c#

c#-3.0