I wanted to have a sorted list, with the ability to have items duplicate, built in sorted collections doesn’t allow duplicate values, so I used a List, and for effeciancy, I maintained the items sorted in it while insertion, instead of calling the sort method with each insertion
To insert in the list sorted, I used the binary search method, to find the first item less then or equal to the inserted item
Suppose we have a sorted list “list”, and we want to insert item i keeping it sorted
To insert in the list sorted, I used the binary search method, to find the first item less then or equal to the inserted item
Suppose we have a sorted list “list”, and we want to insert item i keeping it sorted
List<int> list= new List<int>();
int index = list.BinarySearch(i);
if (index < 0)
list.Insert(~index, i);
else
list.Insert(index, i);
Another way of having sorted list with duplicates is to use a normal sorted list and a custom comparer
public class DuplicateKeyComparer<TKey>:IComparer<TKey> where TKey : IComparable
{
public int Compare(TKey x, TKey y)
{
int result = x.CompareTo(y);
if (result == 0)
return 1; // Handle equality as being greater
return result;
}
}
Only draw back of this method is that we can't find elements or remove, we can only iterate over them, as using the above comparer would always return 1 and won't match any elements.
