5.7. Keeping Your List<T> Sorted
Problem
You will be using the BinarySearch method of the List<T> to periodically search the List<T> for specific elements. The addition, modification, and removal of elements will be interleaved with the searches. The BinarySearch method, however, presupposes a sorted array; if the List<T> is not sorted, the BinarySearch method will possibly return incorrect results. You do not want to have to remember to always call the List<T>.Sort method before calling the List<T>.BinarySearch method, not to mention incurring all the overhead associated with this call. You need a way of keeping the List<T> sorted without always having to call the List<T>.Sort method.
Solution
The following SortedList generic class enhances the adding and modifying of elements within a List<T>. These methods keep the array sorted when items are added to it and modified. Note that a DeleteSorted method is not required because deleting an item does not disturb the sorted order of the remaining items:
using System; using System.Collections; using System.Collections.Generic; public class SortedList<T> : List<T> { public new void Add(T item) { int position = this.BinarySearch(item); if (position < 0) { // This bit of code will be described in detail later. position = ~position; } this.Insert(position, item); } public void ModifySorted(T item, int index) { this.RemoveAt(index); int position = this.BinarySearch(item); if (position < 0) { position = ~position; } this.Insert(position, item); ...Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access