C＃可sorting的集合，它允许重复的键
我正在编写一个程序来设置一个序列，其中各种对象将出现在报告中。 序列是Excel电子表格中的Y位置（单元格）。
代码的演示部分如下。 我想完成的是有一个集合，这将允许我添加多个对象，我可以得到一个基于序列的sorting集合
SortedList list = new SortedList(); Header h = new Header(); h.XPos = 1; h.name = "Header_1"; list.Add(h.XPos, h); h = new Header(); h.XPos = 1; h.name = "Header_2"; list.Add(h.XPos, h); 我知道SortedList不会允许这个，我一直在寻找替代。 我不想消除重复，并已经尝试List<KeyValuePair<int, object>> 。
谢谢。
使用你自己的IComparer！
就像在其他一些答案中已经指出的那样，你应该使用你自己的比较器类。 为此，我使用了一个通用的IComparer类，它可以处理任何实现IComparable的任何事情：
/// <summary> /// Comparer for comparing two keys, handling equality as beeing greater /// Use this Comparer eg with SortedLists or SortedDictionaries, that don't allow duplicate keys /// </summary> /// <typeparam name="TKey"></typeparam> public class DuplicateKeyComparer<TKey> : IComparer<TKey> where TKey : IComparable { #region IComparer<TKey> Members public int Compare(TKey x, TKey y) { int result = x.CompareTo(y); if (result == 0) return 1; // Handle equality as beeing greater else return result; } #endregion }
在实例化一个新的SortedList，SortedDictionary等时你将使用它：
SortedList<int, MyValueClass> slist = new SortedList<int, MyValueClass>(new DuplicateKeyComparer<int>());
这里int是可以重复的键。
你可以放心使用List <>。 List有一个Sort方法，它的一个重载接受IComparer。 你可以创build你自己的分类器类。 这是一个例子：
private List<Curve> Curves; this.Curves.Sort(new CurveSorter()); public class CurveSorter : IComparer<Curve> { public int Compare(Curve c1, Curve c2) { return c2.CreationTime.CompareTo(c1.CreationTime); } }
我使用以下内容：
public class TupleList<T1, T2> : List<Tuple<T1, T2>> where T1 : IComparable { public void Add(T1 item, T2 item2) { Add(new Tuple<T1, T2>(item, item2)); } public new void Sort() { Comparison<Tuple<T1, T2>> c = (a, b) => a.Item1.CompareTo(b.Item1); base.Sort(c); } }
我的testing案例：
[TestMethod()] public void SortTest() { TupleList<int, string> list = new TupleList<int, string>(); list.Add(1, "cat"); list.Add(1, "car"); list.Add(2, "dog"); list.Add(2, "door"); list.Add(3, "elephant"); list.Add(1, "coconut"); list.Add(1, "cab"); list.Sort(); foreach(Tuple<int, string> tuple in list) { Console.WriteLine(string.Format("{0}:{1}", tuple.Item1,tuple.Item2)); } int expected_first = 1; int expected_last = 3; int first = list.First().Item1; //requires using System.Linq int last = list.Last().Item1; //requires using System.Linq Assert.AreEqual(expected_first, first); Assert.AreEqual(expected_last, last); }
输出：
1:cab 1:coconut 1:car 1:cat 2:door 2:dog 3:elephant
最简单的解决scheme（与以上所有方法相比）：使用SortedSet<T> ，它接受一个IComparer<SortableKey>类，然后用这种方法实现Compare方法：
public int Compare(SomeClass x, SomeClass y) { var compared = x.SomeSortableKeyTypeField.CompareTo(y.SomeSortableKeyTypeField); if (compared != 0) return compared; // to allow duplicates return x.GetHashCode().CompareTo(y.GetHashCode()); }
你有没有尝试Lookup<TKey, TElement> ，这将允许重复的键http://msdn.microsoft.com/en-us/library/bb460184.aspx
非常感谢你的帮助。 在search更多时，我find了这个解决scheme。 （可用在其他问题的Stackoverflow.com）
首先，我创build了一个封装我的对象的类（头，页脚等）
public class MyPosition { public int Position { get; set; } public object MyObjects{ get; set; } }
所以这个类应该保存在对象上，每个对象的PosX都是int型的
List<MyPosition> Sequence= new List<MyPosition>(); Sequence.Add(new MyPosition() { Position = 1, Headerobject }); Sequence.Add(new MyPosition() { Position = 2, Headerobject1 }); Sequence.Add(new MyPosition() { Position = 1, Footer }); League.Sort((PosA, PosB) => PosA.Position.CompareTo(PosB.Position));
最终我得到的是sorting的“序列”列表。
此集合类将保留重复项并为重复项插入sorting顺序。 诀窍是在插入项目时使用唯一的值来标记项目，以保持稳定的sorting顺序。 然后我们把它全部包装在一个ICollection接口中。
public class SuperSortedSet<TValue> : ICollection<TValue> { private readonly SortedSet<Indexed<TValue>> _Container; private int _Index = 0; private IComparer<TValue> _Comparer; public SuperSortedSet(IComparer<TValue> comparer) { _Comparer = comparer; var c2 = new System.Linq.Comparer<Indexed<TValue>>((p0, p1) => { var r = _Comparer.Compare(p0.Value, p1.Value); if (r == 0) { if (p0.Index == -1 || p1.Index == -1) return 0; return p0.Index.CompareTo(p1.Index); } else return r; }); _Container = new SortedSet<Indexed<TValue>>(c2); } public IEnumerator<TValue> GetEnumerator() { return _Container.Select(p => p.Value).GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } public void Add(TValue item) { _Container.Add(Indexed.Create(_Index++, item)); } public void Clear() { _Container.Clear();} public bool Contains(TValue item) { return _Container.Contains(Indexed.Create(-1,item)); } public void CopyTo(TValue[] array, int arrayIndex) { foreach (var value in this) { if (arrayIndex >= array.Length) { throw new ArgumentException("Not enough space in array"); } array[arrayIndex] = value; arrayIndex++; } } public bool Remove(TValue item) { return _Container.Remove(Indexed.Create(-1, item)); } public int Count { get { return _Container.Count; } } public bool IsReadOnly { get { return false; } } }
一个testing课
[Fact] public void ShouldWorkWithSuperSortedSet() { // Sort points according to X var set = new SuperSortedSet<Point2D> (new System.Linq.Comparer<Point2D>((p0, p1) => p0.X.CompareTo(p1.X))); set.Add(new Point2D(9,10)); set.Add(new Point2D(1,25)); set.Add(new Point2D(11,-10)); set.Add(new Point2D(2,99)); set.Add(new Point2D(5,55)); set.Add(new Point2D(5,23)); set.Add(new Point2D(11,11)); set.Add(new Point2D(21,12)); set.Add(new Point2D(-1,76)); set.Add(new Point2D(16,21)); var xs = set.Select(p=>pX).ToList(); xs.Should().BeInAscendingOrder(); xs.Count.Should() .Be(10); xs.ShouldBeEquivalentTo(new[]{-1,1,2,5,5,9,11,11,16,21}); set.Remove(new Point2D(5,55)); xs = set.Select(p=>pX).ToList(); xs.Count.Should() .Be(9); xs.ShouldBeEquivalentTo(new[]{-1,1,2,5,9,11,11,16,21}); set.Remove(new Point2D(5,23)); xs = set.Select(p=>pX).ToList(); xs.Count.Should() .Be(8); xs.ShouldBeEquivalentTo(new[]{-1,1,2,9,11,11,16,21}); set.Contains(new Point2D(11, 11)) .Should() .BeTrue(); set.Contains(new Point2D(-1, 76)) .Should().BeTrue(); // Note that the custom compartor function ignores the Y value set.Contains(new Point2D(-1, 66)) .Should().BeTrue(); set.Contains(new Point2D(27, 66)) .Should().BeFalse(); }
标记结构
public struct Indexed<T> { public int Index { get; private set; } public T Value { get; private set; } public Indexed(int index, T value) : this() { Index = index; Value = value; } public override string ToString() { return "(Indexed: " + Index + ", " + Value.ToString () + " )"; } } public class Indexed { public static Indexed<T> Create<T>(int indexed, T value) { return new Indexed<T>(indexed, value); } }
lambda比较器帮助器
public class Comparer<T> : IComparer<T> { private readonly Func<T, T, int> _comparer; public Comparer(Func<T, T, int> comparer) { if (comparer == null) throw new ArgumentNullException("comparer"); _comparer = comparer; } public int Compare(T x, T y) { return _comparer(x, y); } }
问题是，你使用的东西不是一个关键（因为它发生多次）的关键。
所以，如果你有真正的坐标，你也许应该把Point作为SortedList的关键字。
或者你创build一个List<List<Header>> ，你的第一个列表索引定义了x位置，内部列表索引定义了y位置（反之亦然）。
创build一个类并查询列表：
Public Class SortingAlgorithm { public int ID {get; set;} public string name {get; set;} public string address1 {get; set;} public string city {get; set;} public string state {get; set;} public int age {get; set;} } //declare a sorting algorithm list List<SortingAlgorithm> sortAlg = new List<SortingAlgorithm>(); //Add multiple values to the list sortAlg.Add( new SortingAlgorithm() {ID = ID, name = name, address1 = address1, city = city, state = state, age = age}); sortAlg.Add( new SortingAlgorithm() {ID = ID, name = name, address1 = address1, city = city, state = state, age = age}); sortAlg.Add( new SortingAlgorithm() {ID = ID, name = name, address1 = address1, city = city, state = state, age = age}); //query and order by the list var sortedlist = (from s in sortAlg select new { s.ID, s.name, s.address1, s.city, s.state, s.age }) .OrderBy(r => r.ID) .ThenBy(r=> r.name) .ThenBy(r=> r.city) .ThenBy(r=>r.state) .ThenBy(r=>r.age);
Linq.Lookup是很酷的，但如果你的目标是简单地循环“键”，同时允许它们被复制，你可以使用这个结构：
List<KeyValuePair<String, String>> FieldPatterns = new List<KeyValuePair<string, string>>() { new KeyValuePair<String,String>("Address","CommonString"), new KeyValuePair<String,String>("Username","UsernamePattern"), new KeyValuePair<String,String>("Username","CommonString"), };
那么你可以写：
foreach (KeyValuePair<String,String> item in FieldPatterns) { //use item.Key and item.Value }
HTH
这个关键（双关意图）是创build一个保持相等和散列的IComparable类，但如果不相等则不会比较0。 这可以完成，并可以创build一对夫妇的奖金 – 稳定的sorting（即，值添加到sorting列表首先将保持其位置）， ToString()可以简单地返回实际的键string值。
这里有一个结构键应该做的伎俩：
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; namespace System { /// <summary> /// Defined in Totlsoft.Util. /// A key that will always be unique but compares /// primarily on the Key property, which is not required /// to be unique. /// </summary> public struct StableKey : IComparable<StableKey>, IComparable { private static long s_Next; private long m_Sequence; private IComparable m_Key; /// <summary> /// Defined in Totlsoft.Util. /// Constructs a StableKey with the given IComparable key. /// </summary> /// <param name="key"></param> public StableKey( IComparable key ) { if( null == key ) throw new ArgumentNullException( "key" ); m_Sequence = Interlocked.Increment( ref s_Next ); m_Key = key; } /// <summary> /// Overridden. True only if internal sequence and the /// Key are equal. /// </summary> /// <param name="obj"></param> /// <returns></returns> public override bool Equals( object obj ) { if( !( obj is StableKey ) ) return false; var dk = (StableKey)obj; return m_Sequence.Equals( dk.m_Sequence ) && Key.Equals( dk.Key ); } /// <summary> /// Overridden. Gets the hash code of the internal /// sequence and the Key. /// </summary> /// <returns></returns> public override int GetHashCode() { return m_Sequence.GetHashCode() ^ Key.GetHashCode(); } /// <summary> /// Overridden. Returns Key.ToString(). /// </summary> /// <returns></returns> public override string ToString() { return Key.ToString(); } /// <summary> /// The key that will be compared on. /// </summary> public IComparable Key { get { if( null == m_Key ) return 0; return m_Key; } } #region IComparable<StableKey> Members /// <summary> /// Compares this Key property to another. If they /// are the same, compares the incremented value. /// </summary> /// <param name="other"></param> /// <returns></returns> public int CompareTo( StableKey other ) { var cmp = Key.CompareTo( other.Key ); if( cmp == 0 ) cmp = m_Sequence.CompareTo( other.m_Sequence ); return cmp; } #endregion #region IComparable Members int IComparable.CompareTo( object obj ) { return CompareTo( (StableKey)obj ); } #endregion } }
您可以使用SortedList，对TKey使用您的值，对TValue使用int（count）。
下面是一个示例：一个函数，用于对单词的字母进行sorting。
private string sortLetters(string word) { var input = new System.Collections.Generic.SortedList<char, int>(); foreach (var c in word.ToCharArray()) { if (input.ContainsKey(c)) input[c]++; else input.Add(c, 1); } var output = new StringBuilder(); foreach (var kvp in input) { output.Append(kvp.Key, kvp.Value); } string s; return output.ToString(); }
诀窍是用一个唯一的键来扩充你的对象。 看下面哪个testing通过。 我想保持我的点，按他们的X值sorting。 只是在我的比较函数中使用一个裸体的Point2D将会导致具有相同X值的点被消除。 所以我把Point2D包装在一个名为Indexed的标签类中。
[Fact] public void ShouldBeAbleToUseCustomComparatorWithSortedSet() { // Create comparer that compares on X value but when X // X values are uses the index var comparer = new System.Linq.Comparer<Indexed<Point2D>>(( p0, p1 ) => { var r = p0.Value.X.CompareTo(p1.Value.X); return r == 0 ? p0.Index.CompareTo(p1.Index) : r; }); // Sort points according to X var set = new SortedSet<Indexed<Point2D>>(comparer); int i=0; // Create a helper function to wrap each point in a unique index Action<Point2D> index = p => { var ip = Indexed.Create(i++, p); set.Add(ip); }; index(new Point2D(9,10)); index(new Point2D(1,25)); index(new Point2D(11,-10)); index(new Point2D(2,99)); index(new Point2D(5,55)); index(new Point2D(5,23)); index(new Point2D(11,11)); index(new Point2D(21,12)); index(new Point2D(-1,76)); index(new Point2D(16,21)); set.Count.Should() .Be(10); var xs = set.Select(p=>p.Value.X).ToList(); xs.Should() .BeInAscendingOrder(); xs.ShouldBeEquivalentTo(new[]{-1,1,2,5,5,9,11,11,16,21}); }
公用事业，使这项工作
比较器需要一个lambda
public class Comparer<T> : IComparer<T> { private readonly Func<T, T, int> _comparer; public Comparer(Func<T, T, int> comparer) { if (comparer == null) throw new ArgumentNullException("comparer"); _comparer = comparer; } public int Compare(T x, T y) { return _comparer(x, y); } }
标记结构
public struct Indexed<T> { public int Index { get; private set; } public T Value { get; private set; } public Indexed(int index, T value) : this() { Index = index; Value = value; } public override string ToString() { return "(Indexed: " + Index + ", " + Value.ToString () + " )"; } } public class Indexed { public static Indexed<T> Create<T>(int indexed, T value) { return new Indexed<T>(indexed, value); } }
问题是数据结构devise不符合要求：有必要为相同的XPos存储多个Headers。 因此， SortedList<XPos, value>不应该具有Header的值，而应该是List<Header>的值。 这是一个简单而小小的改变，但它解决了所有问题，并避免了像其他build议的解决scheme一样创build新的问题（请参阅下面的解释）：
using System; using System.Collections.Generic; namespace TrySortedList { class Program { class Header { public int XPos; public string Name; } static void Main(string[] args) { SortedList<int, List<Header>> sortedHeaders = new SortedList<int,List<Header>>(); add(sortedHeaders, 1, "Header_1"); add(sortedHeaders, 1, "Header_2"); add(sortedHeaders, 2, "Header_3"); foreach (var headersKvp in sortedHeaders) { foreach (Header header in headersKvp.Value) { Console.WriteLine(header.XPos + ": " + header.Name); } } } private static void add(SortedList<int, List<Header>> sortedHeaders, int xPos, string name) { List<Header> headers; if (!sortedHeaders.TryGetValue(xPos, out headers)){ headers = new List<Header>(); sortedHeaders[xPos] = headers; } headers.Add(new Header { XPos = xPos, Name = name }); } } } Output: 1: Header_1 1: Header_2 2: Header_3
请注意，添加一个“有趣”的键，如添加一个随机数字或者假装2个XPos具有相同的值是不同的，会导致很多其他问题。 例如，移除特定的标题变得困难甚至不可能。
还要注意，如果只有less数List<Header>必须比每个Header进行sorting，则sorting性能要好得多。 例如：如果有100个XPos，每个包含100个标题，则需要对10000个Header进行sorting，而不是100个List<Header> 。
当然，这个解决scheme也有一个缺点：如果有很多XPos只有一个Header，那么需要创build多个列表，这是一些开销。
