How to sort an element as you add it to a list?

Question

I am trying to add a list of elements from one list to another but sorting them as I insert them as i would like to reuse the same list since i do it a lot.

My current setup is written like this which is not ideal:

// system entities is IReadOnly list in another class
//_sortedList is a field in the class that i wish to reuse for sorting

_sortedList.Clear();
for (int i = 0; i < _system.entities.Count; i++)
{
    _sortedList.Add(_system.entities[i]); // would rather sort here
}

// I want to sort the "_sortList" and not create a new collection like this line does
var newList = _sortedList.OrderBy(entity => entity.quantity).ThenBy(entity => entity.name).ToList();

Is there any way i can sort as i insert to _sortedList using LINQ? If so how do i do it ?

Are there duplicates in the elements? If not, you might be able to use a `SortedSet` here. — Sweeper, Aug 28 '21 at 03:20
There is instances of two (or more) elements having the same name and same quantity. — WDUK, Aug 28 '21 at 03:21
You can use `SortedList` where Key is `{quantity, name}`. My understanding, that in `SortedList`, unlike `SortedDirctionary` key doesn't have to be unique https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sortedlist-2?view=net-5.0 — Felix, Aug 28 '21 at 03:25
But if more than one element can have the same quantity and name wouldn't this produce the same key @Felix ? According to this https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sortedlist-2?view=net-5.0 the code example does a try catch for key already being used, does that mean it will error if i do have two of the same key? — WDUK, Aug 28 '21 at 03:28
@WDUK - if I was sure, I'd put it as an answer, not a comment :) I think that in Dictionary keys have to be unique, but not on List. give it a try... — Felix, Aug 28 '21 at 03:34
@Felix sadly it appears from this link: https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sortedlist-2.add?view=net-5.0 It does throw an exception on Add. — WDUK, Aug 28 '21 at 03:35
@WDUK - Please explain what you hope to gain from re-using the same list? — Enigmativity, Aug 28 '21 at 03:37
Take a look here: https://stackoverflow.com/questions/5716423/c-sharp-sortable-collection-which-allows-duplicate-keys. essentially, you need to write your own `Comparer` and it will make it difficult to remove - but maybe it's good enough for you — Felix, Aug 28 '21 at 03:42
Well i'm trying to avoid allocating new lists all the time when i want a sorted one, since I'm sorting the data frequently every time any item changes. @Enigmativity as this is running in a hot path. — WDUK, Aug 28 '21 at 03:42
@WDUK - You'd have to be doing something exceedingly special that allocating memory is a significant slow down compared to actually sorting the list. Can you explain what that is? — Enigmativity, Aug 28 '21 at 03:46
@Enigmativity i have around currently 1000 game agents that take damage / heal that calls my UI system to re-order the list of units by their health so the user can see who is taking damage. I do want to scale up the unit count in the future so i am trying to just make the code produce less heap allocations where possible. — WDUK, Aug 28 '21 at 03:47
@WDUK - It sounds to me like you need to implement your own `IList` class that responds to changes in damage of it's members and does the re-ordering of the list on the fly. — Enigmativity, Aug 28 '21 at 03:54
@WDUK - Nonetheless, I think you're prematurely optimising your code. I'd run with the "create multiple lists on the heap" approach until you can demonstrate you have an issue. — Enigmativity, Aug 28 '21 at 03:55
I don't believe its premature, according to Unity's profiler its quite significant chunk of the frame. Its infact the heaviest part in the whole project. — WDUK, Aug 28 '21 at 03:56
Which part is the heaviest? The allocation or the sort? Make sure you are correctly interpreting the results. — David L, Aug 28 '21 at 04:44
Why do you sort? What benefit does it bring? Is it for displaying the whole list purposes or for faster lookup (eg binary search)? — Caius Jard, Aug 28 '21 at 05:20
Maybe this helps? https://stackoverflow.com/questions/46734083/c-sharp-sorted-list-fast-with-removable-duplicated-keys — Klaus Gütter, Aug 28 '21 at 05:23
*Is there any way i can sort as i insert to _sortedList using LINQ?* - question makes no sense. You don't say what the type of the class is, only what the variable name is, and LINQ cannot (shouldn't) be used to insert anything. It's for querying and should not have side effects. Say what type your variable is — Caius Jard, Aug 28 '21 at 05:24
@CaiusJard i thought it was obvious by the title and code example that `_sortedList` was a list that would contain the same elements as the list i am reading from and inserting to. I'm sorting for user interface menu which lists my entities in order of health quantity then by name. — WDUK, Aug 28 '21 at 06:39
Yeah, but there are at least 3 different classes that spring to *my* mind when I see "list", not to mention the fact that there are umpteen collection classes not bearing the world list and that people also refer to arrays as lists. Be specific please; you're talking with other software engineers now. Layman's terms will only cause problems and "assumption is the mother of all screwups" — Caius Jard, Aug 28 '21 at 06:55
I don't know any one who refers to an array as a list, i say list because i am talking about `List` — WDUK, Aug 28 '21 at 07:17

score 1 · Accepted Answer · answered Aug 28 '21 at 08:14

Here's a fairly simple way to keep a list sorted as you insert. It doesn't keep things sorted if their values change though.

My type is this:

public class Entity
{
    public int Quantity;
    public string Name;
}

Now, let's write a comparer:

public class EntityComparer : IComparer<Entity>
{
    public int Compare(Entity x, Entity y) =>
        x.Quantity.CompareTo(y.Quantity) == 0
            ? x.Name.CompareTo(y.Name)
            : x.Quantity.CompareTo(y.Quantity);
}

Then it's a case of inheriting from List<Entity> and adding our Add method:

public class EntityList : List<Entity>
{
    public void Add(Entity entity, IComparer<Entity> comparer)
    {
        if (this.IsEmpty())
        {
            this.Add(entity);
        }
        else
        {
            var index = this.BinarySearch(entity, comparer);
            this.Insert(index < 0 ? ~index : index, entity);
        }
    }
}

Now, if I run this code:

var el = new EntityList();
var ec = new EntityComparer();
el.Add(new Entity() { Quantity = 3, Name = "Bob" }, ec);
el.Add(new Entity() { Quantity = 2, Name = "Bob" }, ec);
el.Add(new Entity() { Quantity = 2, Name = "Ally" }, ec);
el.Add(new Entity() { Quantity = 4, Name = "Sally" }, ec);
el.Add(new Entity() { Quantity = 2, Name = "Bob" }, ec);
el.Add(new Entity() { Quantity = 1, Name = "Rob" }, ec);
el.Add(new Entity() { Quantity = 9, Name = "Rob" }, ec);
el.Add(new Entity() { Quantity = 4, Name = "Greg" }, ec);
el.Add(new Entity() { Quantity = 4, Name = "Rob" }, ec);
el.Add(new Entity() { Quantity = 2, Name = "Charlie" }, ec);

I get this result:

Of course you could bake in the comparer as a private nested class within the list if you wanted to hide the implementation away.

How to sort an element as you add it to a list?

1 Answers1