C# Sortable collection which allows duplicate keys

Question

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.

Parasang

Does the collection need to support inserts / removals after it is given the initial list of members? – Casemaker

What didn't work when you tried List? – Lithography

I dont want just sorting and get the object. But rather I want to get the entire sorted list. So in example below, both the Header objects should exists and in sequence one below other. If I add another Header object with XPos=2, I should then have 3 objects in the list, 2 objects with XPos=1 and third as XPos=2 – Parasang

Just a note: when I encounter this type of situation I find that the generic List in combination with the little-known BinarySearch behavior for items not found works wonders. – Pseudonymous

Answer 1

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.

Parasang

Answer 2

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.

Elswick

But you won't be able to remove any key from it. – Unbend

Yes thats right, Shachwat! You cannot use Remove(key) or IndexOfKey(key), because the comparer never returns 0 to signal key equality. But you might RemoveAt(index) to delete items if you have their index. – Elswick

I also encountered the same problem, I used SortedDictionary. It allows removal as well. – Unbend

Note that you are breaking reflexivity of your comparer this way. It can (and will) break things in BCL. – Tuchman

If you want to use Remove, you can compare their IDs (generate one if they don't have one) after you found out their keys are equal. – Suppression

The DuplicateKeyComparer is a regular class, so you could add a bool member to separate the case when you want to delete. But still you could not safely delete the item you want, as you have duplicate keys. Maybe it even deletes all items with the given key. – Warmonger

If s.o. is interested in it: Here's the equivalent for C++CLI: generic <class TKey> where TKey : System::IComparable public ref class DuplicateKeyComparer : System::Collections::Generic::IComparer<TKey> – Warmonger

Thaks a little non generic example just to handle float: public class DuplicateKeyComparer : IComparer<float> { public int Compare(float x, float y) { return (x < y) ? -1 : 1; } } – Arlin

this should actually return -1 to keep order – Pandect

@Unbend probably a better option to still be able to remove, is comparing GetHashCode (or your own unique id of that object) instead of returning 1, as suggested in the answer by knocte. But that answer sadly has much less votes. – Blackmarket

this is madness, just use a list inside the sorted list as peter huber suggests https://mcmap.net/q/179467/-c-sortable-collection-which-allows-duplicate-keys – Holm

I concur with @ghord, you may e.g. run into infinite loops for certain operations if unlucky. So you NEED a consistent way to compare items when breaking the tie, like e.g. if (result == 0) return RuntimeHelpers.GetHashCode(x) - RuntimeHelpers.GetHashCode(y); – Gobetween

@BasSmit "This is madness - just use a list inside the sorted list". Well, it all depends on your requirements. I need to sort a few hundred thousand items by millisecond timestamp and simply iterate the result. Duplicate keys are very rare but possible. To be making millions of lists plus nested iteration to avoid these rare clashes is not efficient, as Peter Huber himself advises. But the tree sorting in SortedDictionary is performant for me, and this custom comparer solution handles the occasional clash with little overhead or inconvenience. Horses for courses... – Litharge

Answer 3

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

Loan

I dont want just sorting and get the object. But rather I want to get the entire sorted list. So in example below, both the Header objects should exists and in sequence one below other. If I add another Header object with XPos=2, I should then have 3 objects in the list, 2 objects with XPos=1 and third as XPos=2 – Parasang

all right you mean to say, that the very time an element is inserted in the list, it should be inserted in the correct position as per the sort. Please correct me if wrong. Let me have a look, will get back in short moment – Loan

Note that List<T>.Sort uses multiple sorting algorithms depending on the collection size and not all of them are stable sorts. So objects added to the collection that compare to equivalent may not appear in the order they were added. – Preshrunk

i went with this option so i could stop creating inordinate amounts of KeyValuePairs with applying reduce functions to a dictionary – Henslowe

Answer 4

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

Afterword

Tuple is not available in all releases of .NET, but can be substitued with KeyValuePair<K,V> – Murat

Answer 5

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

Wystand

This is the most straightforward solution. Also check SortedDictionary, it is similar, faster in some cases. – Exergue

This is a really good solution. One could quite easily wrap that functionality into some custom collection object and it'd be quite useful. Good thought, thanks for sharing Peter! – Galiot

@AdamP: Thanks for the suggestion, I just did exactly that, write a collection with the name SortedBucketCollection which acts like SortedList<int, List<Header>>, but uses less memory. See Update in my answer. – Wystand

Answer 6

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

}

Bussell

I used SortedSet<T> and T had it's own incrementing int ID that incremented on each instantiation to insure each T is unique even with the other Field(s) are the same. – Supertonic

GetHashCode for comparison is dangerous. Might lead to unexpected false duplicate. It might work most of the time, but i would never use this for anything serious. – Exergue

Answer 7

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

Gujral

Thanks. My problem is the objects will not be only of one type (just not Header), those can vary (lets say Footer,Sidebar etc) but each will have XPos – Parasang

Also, there is no public constructor on Lookup I believe. Any good way around this? – Abrade

@JeffBridgman you will have to rely on Linq. You can do ToLookup on any IEnumerable<T>. – Extravagance

Yes it allows duplicate keys, but it doesn't keep anything sorted! – Sethrida

Answer 8

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

    }

Jurywoman

Answer 9

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

Jamille

Answer 10

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

Kemerovo

A Key may have multiple instances as long as it is not a primary key. At least that's what they told me in the Databases class I took. – Acanthocephalan

This answer is a bit short, but it explains the problem properly and provides the correct solution, i.e. using SortedList<int, List<Header>>. This maintains the header sorted and can store many headers at the same xPos. For a code sample look for my answer. I plussed one this answer, since it points in the right direction. Please plus 1 my answer too if you feel it is helpful. – Wystand

Answer 11

Linq.Lookup 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

Kweisui

Answer 12

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

Portsmouth

That's a nice idea. I wrapped the concept into a custom ICollection. See https://mcmap.net/q/179467/-c-sortable-collection-which-allows-duplicate-keys – Jamille

Answer 13

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

Constantino

Answer 14

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

Jamille

See my other answer for a complete wrap of the above concepts into a custom ICollection class – Jamille

Answer 15

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

Paralyze

There is already a class Queue in BCL, which represents a first-in, first-out collection of items. The semantics of your class are different. Your class has a beginning (where items are dequeued) but no end (an item can be inserted anywhere). So the Enqueue method in your class is meaningless IMHO. – Lu

@TheodorZoulias Yup, naming is a bit sh*t here but I hardly think it deserves a downvote, it has what OP needs and it's only a matter of renaming and reimplementing the input/output methods. Why it's called like this? I needed a structure which I can empty from the start in a while loop and add new items based on priority value. So PriorityQueue would be more appropriate name. – Paralyze

The OP wants a sortable collection which allows duplicate keys. Your class is not a collection, since it cannot be enumerated. I also dislike the use of public fields. Don't take the downvotes personally. You can repair the reputation damage of 5 downvotes with a single upvote (-2 * 5 == +10), so it's not a big deal. :-) – Lu

Answer 16

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

Encincture