C# Sortable collection which allows duplicate keys

I am writing a program to set a sequence in which various objects will appear in report. The sequence is the Y position (cell) on Excel spreadsheet.

A demo part of code is below. What I want to accomplish is to have a collection, which will allow me to add multiple objects and I can get a sorted collection based on the sequence

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);

I know that the SortedList will not allow this and I have been searching for alternate. I don't want to eliminate the duplicates and already tried List<KeyValuePair<int, object>>.

Thanks.

Use your own IComparer!

Like already stated in some other answers, you should use your own comparer class. For this sake I use a generic IComparer class, that works with anything that implements IComparable:

/// <summary>
/// Comparer for comparing two keys, handling equality as beeing greater
/// Use this Comparer e.g. 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 being greater. Note: this will break Remove(key) or
        else          // IndexOfKey(key) since the comparer never returns 0 to signal key equality
            return result;
    }

    #endregion
}

You will use it when instancing a new SortedList, SortedDictionary etc:

SortedList<int, MyValueClass> slist = new SortedList<int, MyValueClass>(new DuplicateKeyComparer<int>());

Here int is the key that can be duplicate.

You can safely use List<> . The List has a Sort method , an overload of which accepts IComparer. You can create your own sorter class as . Here's an example :

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);
    }
}

I use the following:

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);
	}

}

My test case:

[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);
	}

The output:

1:cab
1:coconut
1:car
1:cat
2:door
2:dog
3:elephant

The problem is that the data structure design doesn't match the requirements: It is necessary to store several Headers for the same XPos. Therefore, SortedList<XPos, value> should not have a value of Header, but a value of List<Header>. It's a simple and small change, but it solves all problems and avoids creating new problems like other suggested solutions (see explanation below):

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

Please note that adding a "funny" key, like adding a random number or pretending that 2 XPos with the same value are different lead to many other problems. For example it becomes difficult or even impossible to remove a particular Header.

Also note that the sorting performance is much better if only few List<Header> have to be sorted than every Header. Example: If there are 100 XPos and each has 100 headers, 10000 Header need to be sorted as opposed to 100 List<Header>.

Of course, also this solution has a disadvantage: If there are many XPos with only 1 Header, as many Lists need to be created, which is some overhead.

Update 22.12.2021

I finally found time to write a proper collection called SortedBucketCollection, which behaves like a SortedList. It uses 2 keys for each item, the first is the same as a SortedList key and many items can have for that key the same value. The second key is used to differentiate items sharing the same values for key1. SortedBucketCollection uses less storage space than SortedList<int, List<Header>>, because it uses for each "bucket" a linked list and not a List<>.

Code using SortedBucketCollection looks like this:

using System;

namespace SortedBucketCollectionDemo {

  public record FinanceTransaction
  (int No, DateTime Date, string Description, decimal Amount);

  class Program {
    static void Main(string[] args) {
      //Constructing a SortedBucketCollection
      var transactions = 
        new SortedBucketCollection<DateTime, int, FinanceTransaction>
                                  (ft=>ft.Date, ft=>ft.No);
      var date1 = DateTime.Now.Date;

      //Adding an item to SortedBucketCollection
      transactions.Add(new FinanceTransaction(3, date1, "1.1", 1m));
      transactions.Add(new FinanceTransaction(1, date1, "1.2", 2m));
      transactions.Add(new FinanceTransaction(0, date1, "1.3", 3m));
      var date2 = date1.AddDays(-1);
      transactions.Add(new FinanceTransaction(1, date2, "2.1", 4m));
      transactions.Add(new FinanceTransaction(2, date2, "2.2", 5m));

      //Looping over all items in a SortedBucketCollection
      Console.WriteLine("foreach over all transactions");
      foreach (var transaction in transactions) {
        Console.WriteLine(transaction.ToString());
      }

      //Accessing one particular transaction
      var transaction12 = transactions[date1, 1];

      //Removing  a transaction
      transactions.Remove(transaction12!);

      //Accessing all items of one day
      Console.WriteLine();
      Console.WriteLine("foreach over transactions of one day");
      Console.WriteLine(date1);
      foreach (var transaction in transactions[date1]) {
        Console.WriteLine(transaction.ToString());
      }
    }
  }
}

Output of first foreach:

FinanceTransaction { No = 1, Date = 07.11.2021 00:00:00, Description = 2.1, Amount = 4 }
FinanceTransaction { No = 2, Date = 07.11.2021 00:00:00, Description = 2.2, Amount = 5 }
FinanceTransaction { No = 0, Date = 08.11.2021 00:00:00, Description = 1.3, Amount = 3 }
FinanceTransaction { No = 1, Date = 08.11.2021 00:00:00, Description = 1.2, Amount = 2 }
FinanceTransaction { No = 3, Date = 08.11.2021 00:00:00, Description = 1.1, Amount = 1 }

Note that the item are not iterated in the sequence they were added, but sorted by their key1 and key2.

For a detailed description of SortedBucketCollection and the source code see my article on CodeProject SortedBucketCollection: A memory efficient SortedList accepting multiple items with the same key

Simplest solution (compared to all of the above): use SortedSet<T>, it accepts an IComparer<SortableKey> class, then implement the Compare method this way:

public int Compare(SomeClass x, SomeClass y)
{
    var compared = x.SomeSortableKeyTypeField.CompareTo(y.SomeSortableKeyTypeField);
    if (compared != 0)
        return compared;

    // to allow duplicates
    var hashCodeCompare = x.GetHashCode().CompareTo(y.GetHashCode());
    if (hashCodeCompare != 0)
        return hashCodeCompare;

    if (Object.ReferenceEquals(x, y))
        return 0;
    
    // for weird duplicate hashcode cases, throw as below or implement your last chance comparer
    throw new ComparisonFailureException();
    
}

Thanks a lot for your help. While searching more, I found this solution. (Available in Stackoverflow.com in other question)

First, I created a class which would encapsulate my objects for classes (Headers,Footer etc)

public class MyPosition
{
    public int Position { get; set; }
    public object MyObjects{ get; set; }
}

So this class is supposed to hold on the objects, and PosX of each object goes as int Position

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));

What eventually I get is the sorted "Sequence" list.

Did you try Lookup<TKey, TElement> that will allow duplicate keys http://msdn.microsoft.com/en-us/library/bb460184.aspx

You can use the SortedList, use your value for the TKey, and int (count) for the TValue.

Here's a sample: A function that sorts the letters of a word.

    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();

    }

This collection class will maintain duplicates and insert sort order for the duplicate. The trick is to tag the items with a unique value as they are inserted to maintain a stable sort order. Then we wrap it all up in an ICollection interface.

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; }
    }
}

a test class

[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=>p.X).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=>p.X).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=>p.X).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();

}

The tagging struct

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);
    }
}

The lambda comparer helper

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);
	}
}

The problem is that you use something as key that isn't a key (cause it occurs multiple times).

So if you have real coordinates you should maybe take the Point as the key for your SortedList.

Or you create a List<List<Header>> where your first list index defines the x-position and the inner list index the y-position (or vice versa if you like).

http://msdn.microsoft.com/en-us/library/bb460184.aspx">Linq.Lookup</a> is cool and all, but if your target is to simply loop over the "keys" while allowing them to be duplicated you can use this structure:

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"),
};

Then you can write:

foreach (KeyValuePair<String,String> item in FieldPatterns)
{
   //use item.Key and item.Value
}

HTH

The key (pun intended) to this is to create an IComparable-based class that maintains equality and hashing, but never compares to 0 if not equal. This can be done, and can be created with a couple bonuses - stable sorting (that is, values added to the sorted list first will maintain their position), and ToString() can simply return the actual key string value.

Here's a struct key that should do the trick:

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
	}
}

This is how I solved the problem. It's meant to be thread-safe though you can simply remove the locks if you don't need that. Also note arbitrary Insert at an index is not supported because that could violate the sort condition.

public class ConcurrentOrderedList<Titem, Tsort> : ICollection<Titem>
{
    private object _lock = new object();
    private SortedDictionary<Tsort, List<Titem>> _internalLists;
    Func<Titem, Tsort> _getSortValue;
    
    public ConcurrentOrderedList(Func<Titem,Tsort> getSortValue)
    {
        _getSortValue = getSortValue;
        _internalLists = new SortedDictionary<Tsort, List<Titem>>();            
    }

    public int Count { get; private set; }

    public bool IsReadOnly => false;

    public void Add(Titem item)
    {
        lock (_lock)
        {
            List<Titem> values;
            Tsort sortVal = _getSortValue(item);
            if (!_internalLists.TryGetValue(sortVal, out values))
            {
                values = new List<Titem>();
                _internalLists.Add(sortVal, values);
            }
            values.Add(item);
            Count++;
        }            
    }

    public bool Remove(Titem item)
    {
        lock (_lock)
        {
            List<Titem> values;
            Tsort sortVal = _getSortValue(item);
            if (!_internalLists.TryGetValue(sortVal, out values))
                return false;

            var removed = values.Remove(item);
            if (removed)
                Count--;
            return removed;
        }
    }

    public void Clear()
    {
        lock (_lock)
        {
            _internalLists.Clear();
        }
    }

    public bool Contains(Titem item)
    {
        lock (_lock)
        {
            List<Titem> values;
            Tsort sortVal = _getSortValue(item);
            if (!_internalLists.TryGetValue(sortVal, out values))
                return false;
            return values.Contains(item);
        }
    }

    public void CopyTo(Titem[] array, int arrayIndex)
    {
        int i = arrayIndex;
        lock (_lock)
        {
            foreach (var list in _internalLists.Values)
            {
                list.CopyTo(array, i);
                i += list.Count;
            }
        }
    }

    public IEnumerator<Titem> GetEnumerator()
    {
        foreach (var list in _internalLists.Values)
        {
            foreach (var item in list)
                yield return item;
        }
    }

    public int IndexOf(Titem item)
    {
        int i = 0;
        var sortVal = _getSortValue(item);
        lock (_lock)
        {               
            foreach (var list in _internalLists)
            {
                if (object.Equals(list.Key, sortVal))
                {
                    int intIndex = list.Value.IndexOf(item);
                    if (intIndex == -1)
                        return -1;
                    return i + intIndex;
                }
                i += list.Value.Count;
            }
            return -1;
        }           
    }

    public void Insert(int index, Titem item)
    {
        throw new NotSupportedException();
    }

    // Note this method is indeterminate if there are multiple
    // items in the same sort position!
    public void RemoveAt(int index)
    {
        int i = 0;
        lock (_lock)
        {
            foreach (var list in _internalLists.Values)
            {
                if (i + list.Count < index)
                {
                    i += list.Count;
                    continue;
                }
                else
                {
                    list.RemoveAt(index - i);
                    return;
                }
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

The trick is to augment your object with a unique key. See the following test which passes. I want to keep my points sorted by their X value. Just using a naked Point2D in my comparison function will cause points with the same X value to be eliminated. So I wrap the Point2D in a tagging class called 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});

}

Utilities to make this work are

A comparer that takes a 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);
	}
}

A tagging struct

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);
    }
}

Create a class and query the list:

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);

Here's my take on this. Be aware, here might be dragons, C# still still quite new for me.

• Duplicate keys are allowed, values are stored in a list
• I used it as a sorted queue, hence the names and methods

Usage:

SortedQueue<MyClass> queue = new SortedQueue<MyClass>();
// new list on key "0" is created and item added
queue.Enqueue(0, first);
// new list on key "1" is created and item added
queue.Enqueue(1, second);
// items is added into list on key "0"
queue.Enqueue(0, third);
// takes the first item from list with smallest key
MyClass myClass = queue.Dequeue();

class SortedQueue<T> {
  public int Count;
  public SortedList<int, List<T>> Queue;
  
  public SortedQueue() {
    Count = 0;
    Queue = new SortedList<int, List<T>>();
  }

  public void Enqueue(int key, T value) {
    List<T> values;
    if (!Queue.TryGetValue(key, out values)){
      values = new List<T>();
      Queue.Add(key, values);
      Count += 1;
    }
    values.Add(value);
  }

  public T Dequeue() {
    if (Queue.Count > 0) {
      List<T> smallest = Queue.Values[0];
      if (smallest.Count > 0) {
        T item = smallest[0];
        smallest.Remove(item);
        return item;
      } else {
        Queue.RemoveAt(0);
        Count -= 1;
        return Dequeue();
      }
    }
    return default(T);
  }
}