I’m using linq to sort items in my inventory system by rarity, name, and amount. However, I feel uncomfortable calling the sort every time a new item is added to the inventory, so I was wondering if there was a function for inserting an item at the correct sorted position in the list. I can make a system that handles this if need be but I was just curious if there’s an easier way.
Hi,
If I understand correctly, you are using a regular List.
Instead, you could use a SortedList : SortedList<TKey,TValue> Class (System.Collections.Generic) | Microsoft Learn
First insert the item into the list, then reorder it using OrderBy to maintain the sorting order.
If you have an IComparer that you use for sorting, a fairly efficient way would be to use List.BinarySearch. You can just define a struct implementing IComparer. The usual way to write those is to create comparisons like so:
public struct MyComparer : IComparer<MyType>
{
public int Compare(MyType a, MyType b)
{
// compare the first field, will order by this first
int comparison = a.IntField.CompareTo(b.IntField);
if (comparison != 0)
{
return comparison;
}
// compare the next field, will order by this if first values match
comparison = string.Compare(a.StringField, b.StringField, StringComparison.InvariantCulture);
if (comparison != 0)
{
return comparison;
}
// compare last value, will sort by this if everything else matches
return a.LastField.CompareTo(b.LastField);
}
}
Then the binary search can be used with that comparer.
List<MyType> list = new();
// ...
MyType objectToAdd = ???;
int index = list.BinarySearch(objectToAdd, new MyComparer());
if (index >= 0)
{
/*
* Another object exists that has the same compared value.
* If it makes sense for your use case, add the value or not.
*/
list.Insert(index, objectToAdd);
}
else
{
/*
* The object wasn't found, so BinarySearch returned the bitwise complement of the index of the first larger value, or List<T>.Count if there's no such value.
* Either way, you can just use the bitwise complement of that as an index to insert your value.
*/
list.Insert(~index, objectToAdd);
}
1 Like
Note that the previous two answers aren’t very good. The first one introduces unnecessary storage overhead since you need to track both a key and a value for every element (it’s basically usable as a dictionary, along with the limitation that you cannot have duplicate keys). The second one is not suggesting anything new, you’re already inserting and sorting after that.
1 Like
Another way of inserting without having to re-sort the collection each time, you can write an extension method that takes a Comparison<T> delegate, and inserts the element at the index where the comparison result is zero or below, or at the end of there was no insertion.
Off the top of my head code:
public static void InsertSorted<T>(this IList<T> collection, T element, Comparison<T> comparison)
{
bool inserted = false;
int count = collection.Count;
for (int i = 0; i < count; i++)
{
T compareElement = collection[i];
int compareResult = comparison(element, compareElement);
// once we hit a point where the comparison would either place element
// before or at the same index, we can insert the element and break
// from the loop
if (compareResult <= 0)
{
collection.Insert(i, element);
inserted = true;
break;
}
}
// elements that would naturally go to the end will not get inserted
// so we need to check if anything was inserted, and add it if not
if (inserted == false)
{
collection.Add(element);
}
}
3 Likes
You could also use the binary search approach with a Comparison:
public static int BinarySearch<T>(this IReadOnlyList<T> list, T value, Comparison<T> comparison)
{
int offset = 0;
for (int l = list.Count; l != 0; l >>= 1)
{
int i = offset + (l >> 1);
int r = comparison(value, list[i]);
if (r == 0)
{
return i;
}
if (r > 0)
{
offset = i + 1;
l--;
}
}
return ~offset;
}
My brain is kind of stuck on trying to avoid O(n) pieces of a solution even when other parts need to be O(n) (the list insertion).
1 Like
I was thinking about an easy solution that would be available by the language, but thanks for pointing this out !
If your list is already sorted, you could use FindIndex to find the index of the first item that matches your criteria:
List<Person> people = new() { new Person { Age = 5 }, new Person { Age = 15 }, new Person { Age = 25 } };
var personToInsert = new Person { Age = 20 };
// Returns -1 if no item found
var insertIndex = people.FindIndex(x => x.Age > personToInsert.Age);
// If not found, it means we have the oldest person, set insertIndex to list.Count to insert
// it at the end (equivalent to people.Add(personToInsert))
if (insertIndex < 0)
insertIndex = people.Count;
// We insert our item at insertIndex, pushing the current item at that index by one slot
people.Insert(insertIndex, personToInsert);
1 Like
This wouldn’t work when inserting an element where the Age is greater than any element in the list. It would incorrectly add the element to the beginning of the list.
If you’re using Rider, you can auto-generate an implementation of IComparable for your inventory items based on the order of fields you want. Visual Studio might have something similar. Implementing IComparable can be used in place of creating your own IComparer, and it’s basically just the same logic as IComparer except you’re using the “this” object instead of the first field, so the first example would be more like:
public class MyType : IComparable<MyType>
{
public int IntField;
public string StringField;
public int LastField;
public int CompareTo(MyType other)
{
// compare the first field, will order by this first
int comparison = IntField.CompareTo(other.IntField);
if (comparison != 0)
{
return comparison;
}
// compare the next field, will order by this if first values match
comparison = string.Compare(StringField, other.StringField, StringComparison.InvariantCulture);
if (comparison != 0)
{
return comparison;
}
// compare last value, will sort by this if everything else matches
return LastField.CompareTo(other.LastField);
}
}
Then with the binary search approach, you don’t need to pass in a comparer instance, because Comparer.Default is implicitly used, which will give you a correct IComparer that uses your IComparable implementation. That would look like this:
List<MyType> list = new();
// ...
MyType objectToAdd = ???;
int index = list.BinarySearch(objectToAdd);
list.Insert(index >= 0 ? index : ~index, objectToAdd);
To add to what I previously said, apparently it’s better to derive from Comparer instead of implementing IComparer, because it will automatically implement the non-generic IComparer as well.
So instead of
public struct MyComparer : IComparer<MyType>
{
public int Compare(MyType a, MyType b)
{
// …
}
}
That would better be written as
public class MyComparer : Comparer<MyType>
{
public override int Compare(MyType a, MyType b)
{
// …
}
}
Using an IComparer, IComparable, or Comparison (what spiney suggested) would work well, they’re pretty much doing the same thing. The last one needs the binary search extension method I posted earlier or an IComparer that wraps the Comparison, since the List class doesn’t have an overload that accepts that.
2 Likes
Yes you’re right, good catch. We should set the index to list.Count if nothing is found, and not 0, because it means it’s the oldest person, not the youngest. Fixed the code thanks!
1 Like