C# 让类型在集合中可被查找

问题

您有一种数据类型，它将存储为 List 中的元素。您想使用 BinarySearch 方法，自定义您的数据类型在列表中的查找方式。

解决方法

使用 IComparable 和 IComparer 接口，使得 List 和 SortedList 集合可以排序和查找对象的数组和集合。

讨论

通过在类（或结构）上实现 IComparable 接口，就可以利用 List 和 SortedList 类的排序例程。排序算法内置在这些类中；您只需要通过在 IComparable.CompareTo 方法中实现的代码告诉它们如何对您的类进行排序即可。
要实现 CompareTo 方法，请参考这篇文章:

List 类提供了一个 BinarySearch 方法来查找该列表中的元素。列表中的元素会与传递给对象参数中的 BinarySearch 方法的某个对象进行比较。SortedList 类没有 BinarySearch 方法；作为替代，它拥有 ContainsKey 方法，用于对列表中包含的键值执行二分查找。SortedList 类的 ContainsValue 方法在查找值时执行线性查找。这种线性查找使用 SortedList 集合中的元素的 Equals 方法来执行其工作。Compare 和 CompareTo 方法对于 SortedList 类中执行的线性查找不起任何作用，但是它们确实会影响二分查找。
　为了使用 List 类的 BinarySearch 方法执行准确的查找，首先必须使用 List 的 Sort 方法对其进行排序。此外，如果把一个 IComparer 接口传入给 BinarySearch 方法，还必须把相同的接口传递给 Sort 方法。否则，BinarySearch 方法也许无法找到您正在寻找的对象。
例(1) 中的 TestSort 方法演示了如何对 List 和 SortedList 集合实例使用 Square 和 CompareHeight 类。
例 (1) ：使类型可查找

public static void TestSearch()
{
List listOfSquares = new List {
new Square(1,3),
new Square(4,3),
new Square(2,1),
new Square(6,1)};
IComparer heightCompare = new CompareHeight();
// Test a List
Console.WriteLine("List");
Console.WriteLine("Original list");
foreach (Square square in listOfSquares)
{
Console.WriteLine(square.ToString());
}
Console.WriteLine();
Console.WriteLine("Sorted list using IComparer=heightCompare");
listOfSquares.Sort(heightCompare);
foreach (Square square in listOfSquares)
{
Console.WriteLine(square.ToString());
}
Console.WriteLine();
Console.WriteLine("Search using IComparer=heightCompare");
int found = listOfSquares.BinarySearch(new Square(1, 3), heightCompare);
Console.WriteLine($"Found (1,3): {found}");
Console.WriteLine();
Console.WriteLine("Sorted list using IComparable");
listOfSquares.Sort();
foreach (Square square in listOfSquares)
{
Console.WriteLine(square.ToString());
}
Console.WriteLine("Search using IComparable");
found = listOfSquares.BinarySearch(new Square(6, 1));  // Use IComparable
Console.WriteLine($"Found (6,1): {found}");
// Test a SortedList
var sortedListOfSquares = new SortedList(){
{0, new Square(1,3)},
{2, new Square(4,3)},
{1, new Square(2,1)},
{4, new Square(6,1)}};
Console.WriteLine();
Console.WriteLine();
Console.WriteLine("SortedList");
foreach (KeyValuePair kvp in sortedListOfSquares)
{
Console.WriteLine($"{kvp.Key} : ${kvp.Value}");
}
Console.WriteLine();
bool foundItem = sortedListOfSquares.ContainsKey(2);
Console.WriteLine($"sortedListOfSquares.ContainsKey(2): {foundItem}");
//不使用IComparer或IComparable
//——使用线性搜索和Equals方法
//没有被重载
Square value = new Square(6, 1);
foundItem = sortedListOfSquares.ContainsValue(value);
Console.WriteLine($"sortedListOfSquares.ContainsValue(new Square(6,1)): {foundItem}");
}

这段代码显示的结果如下所示。
List Original list Height:1 Width:3 Height:4 Width:3 Height:2 Width:1 Height:6 Width:1 Sorted list using IComparer=heightCompare Height:1 Width:3 Height:2 Width:1 Height:4 Width:3 Height:6 Width:1 Search using IComparer=heightCompare Found (1,3): 0 Sorted list using IComparable Height:2 Width:1 Height:1 Width:3 Height:6 Width:1 Height:4 Width:3 Search using IComparable Found (6,1): 2 SortedList 0 : Height:1 Width:3 1 : Height:2 Width:1 2 : Height:4 Width:3 4 : Height:6 Width:1 sortedListOfSquares.ContainsKey(2): True sortedListOfSquares.ContainsValue(new Square(6,1)): True

参考

• (1) 《C# 通过实现IComparer 泛型接口比较对象》:
• (2) 《IComparable 接口 (System)》: https://docs.microsoft.com/zh-cn/dotnet/api/system.icomparable-1
• (3) 《IComparer 接口 (System.Collections.Generic)》: https://docs.microsoft.com/zh-cn/dotnet/api/system.collections.generic.icomparer-1?