
This is the Title of the Book, eMatter Edition
Copyright © 2007 O’Reilly & Associates, Inc. All rights reserved.
304
|
Chapter 5: Collections
5.9 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, presup-
poses a sorted array; if the
List<T> is not sorted, the BinarySearch method will possi-
bly 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 men-
tion 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 ele-
ments 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 since 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 void AddSorted(T item)
{
int position = this.BinarySearch(item);
if (position < 0)
{
// This bit of code will be described in detail later.
position ...