Looking for an inbuilt ordered list in C#

Question

I'm having a problem ordering the lists in C#. The solutions I come up with are unwieldy and seem a bit of a hack to me. I am looking for an elegant solution to the problem described below. I want to make the ordering remain in the class to avoid using .Sort() or .OrderBy() in other parts of the code. A 9 year old posting suggests that no such class/solution exists. But, I cannot help feeling there is something similar to an OrderedList somewhere which is not an IDictionary.

using System;
using System.Collections.Generic;

namespace ConsoleApp5
{
    class Program
    {
        static void Main(string[] args)
        {
                var obj = new Class1();
                obj.Test();
        }
    }

    public class Class1
    {
        public void Test()
        {
            var myList = new List<MyObject>();

            myList.Add(new MyObject { Id = 1, Name = "ZZZ" });
            myList.Add(new MyObject { Id = 2, Name = "NNN" });
            myList.Add(new MyObject { Id = 3, Name = "PPP" });
            myList.Add(new MyObject { Id = 4, Name = "AAA" });

            foreach (var obj in myList)
            {
                Console.WriteLine($"{obj.Name} -> {obj.Id}");
            }

        }

        public class MyObject
        {
            public int Id { get; set; }
            public string Name { get; set; }

        }
    }
}

And the list is printed out in the order:

ZZZ -> 1
NNN -> 2
PPP -> 3
AAA -> 4

Could anyone suggest an appropriate class for an ordered list which would deliver:

AAA -> 4
NNN -> 2
PPP -> 3
ZZZ -> 1

Answer 1

Multiple options here:

Sort the list in place:

myList.Sort((x, y) => string.Compare(x.Name, y.Name));

Sort the list in place with a comparer:

class MyObjectNameComparer : IComparer<MyObject>
{
    public int Compare(MyObject x, MyObject y)
    {
        return string.Compare(x.Name, y.Name);
    }
}

myList.Sort(new MyObjectNameComparer());

Mark your class as IComparable<MyObject> and then sort in place. This will affect the behavior of Comparer<MyObject>.Default:

class MyObject : IComparable<MyObject>
{
    public int Id { get; set; }
    public string Name { get; set; }

    public int CompareTo(MyObject other)
    {
        return string.Compare(this.Name, other.Name);
    }
}

// then
myList.Sort();

Use linq to iterate in a sorted manner, but keep the list as-is:

foreach (var myObject in myList.OrderBy(x => x.Name))
{
    // ordered results
}

Use a SortedList, which is somewhat like a dictionary, but then sorted on a key instead of a hashcode. That means you need unique 'names' (keys) for each object:

var sortedList = new SortedList<string, MyObject>();
sortedList.Add("ZZZ", new MyObject { Id = 1, Name = "ZZZ" });
sortedList.Add("NNN", new MyObject { Id = 2, Name = "NNN" });
sortedList.Add("PPP", new MyObject { Id = 3, Name = "PPP" });
sortedList.Add("AAA", new MyObject { Id = 4, Name = "AAA" });
// Below would fail, because the key needs to be unique...
// sortedList.Add("AAA", new MyObject { Id = 5, Name = "AAA" });

foreach (var entry in sortedList)
{
    Console.WriteLine($"{entry.Value.Name} -> {entry.Value.Id}");
}

Or use a SortedSet<T>, which maintains ordered, unique items (i.e. you cannot add doubles).

var set = new SortedSet<MyObject>(new MyObjectNameComparer());
set.Add(new MyObject { Id = 1, Name = "ZZZ" });
// etc.

Create a custom collection, with an ordered enumerator. That would let clients iterate over the items in a sorted manner. This version is 'optimized' on inserts:

class OrderedMyObjectCollection : ICollection<MyObject>
{
    private List<MyObject> innerList = new List<MyObject>();
    public int Count => this.innerList.Count;
    public bool IsReadOnly => false;
    public void Add(MyObject item) => this.innerList.Add(item);
    public void Clear() => this.innerList.Clear();
    public bool Contains(MyObject item) => this.innerList.Contains(item);

    public void CopyTo(MyObject[] array, int arrayIndex)
    {
        // Could be more efficient...
        this.ToList().CopyTo(array);
    }

    // Magic in the ordered enumerator.
    public IEnumerator<MyObject> GetEnumerator() => this.innerList.OrderBy(x => x.Name).GetEnumerator();
    public bool Remove(MyObject item) => this.innerList.Remove(item);
    IEnumerator IEnumerable.GetEnumerator() => this.GetEnumerator();
}

If you need to optimize on iteration, you could actually store the items at the right index on add:

class OrderedList<T> : IList<T>
{
    // see above for the comparer implementation 
    private readonly IComparer<T> comparer;
    private readonly IList<T> innerList = new List<T>();

    public OrderedList()
        : this(Comparer<T>.Default)
    {
    }

    public OrderedList(IComparer<T> comparer)
    {
        this.comparer = comparer ?? throw new ArgumentNullException(nameof(comparer));
    }

    public T this[int index]
    {
        get => this.innerList[index];
        set => throw new NotSupportedException("Cannot set an indexed item in a sorted list.");
    }

    public int Count => this.innerList.Count;
    public bool IsReadOnly => false;

    // Magic in the insert
    public void Add(T item)
    {
        int index = innerList.BinarySearch(item, comparer);
        index = (index >= 0) ? index : ~index;
        innerList.Insert(index, item);
    }

    public void Clear() => this.innerList.Clear();
    public bool Contains(T item) => this.innerList.Contains(item);
    public void CopyTo(T[] array, int arrayIndex) => this.innerList.CopyTo(array);
    public IEnumerator<T> GetEnumerator() => this.innerList.GetEnumerator();
    public int IndexOf(T item) => this.innerList.IndexOf(item);
    public void Insert(int index, T item) => throw new NotSupportedException("Cannot insert an indexed item in a sorted list.");
    public bool Remove(T item) => this.innerList.Remove(item);
    public void RemoveAt(int index) => this.innerList.RemoveAt(index);
    IEnumerator IEnumerable.GetEnumerator() => this.GetEnumerator();
}

Answer 2

Think I finally came across this, which is as simple as I can find. Never heard of SortedSet before.

    public void Test()
    {
        var myList = new SortedSet<MyObject>(new MyComparer());

        myList.Add(new MyObject { Id = 1, Name = "ZZZ" });
        myList.Add(new MyObject { Id = 2, Name = "NNN" });
        myList.Add(new MyObject { Id = 3, Name = "PPP" });
        myList.Add(new MyObject { Id = 4, Name = "AAA" });

        foreach (var obj in myList)
        {
            Console.WriteLine($"{obj.Name} -> {obj.Id}");
        }
    }

    public class MyComparer : IComparer<MyObject>
    {
        public int Compare(MyObject x, MyObject y) => String.Compare(x.Name, y.Name, StringComparison.Ordinal);
    }

    public class MyObject
    {
        public int Id { get; set; }
        public string Name { get; set; }
    }