# 原则31:用 IComparable<T> 和 IComparer<T> 实现排序关系
**By D.S.Qiu**
**尊重他人的劳动,支持原创,转载请注明出处:[http://dsqiu.iteye.com](http://dsqiu.iteye.com)**
你的类型需要排序关系用于定义集合的排序和搜索。 .NET 框架定义两个接口描述类型的排序关系: IComparable<T> 和 IComparer<T> 。IComparable 定义了类型的自然排序。类型实现的 IComparer 描述的另一个排序。你可以在接口中提供具体类型的比较并避免运行时低效率的自定义关系操作符( < ,>,<=,>= )的实现。本原则会讨论怎么实现排序关系,.NET 核心框架可以根据你定义的接口对你的类型进行排序,其他使用者可以这些操作得到更好的性能。
IComparable 接口包含一个方法: CompareTo() 。这个方法遵循了从 C 库函数 strmp 开始的传统:它返回小于0的数如果当前对象小于比较的对象,如果它们相等返回0,如果当前对象比比较的对象大则返回大于0的数。 IComparable<T> 会被 .NET 框架的大多数新 APIs 使用。然而,一些旧的 APIs 仍使用旧的的 IComparable 接口。因此,当你实现 IComparable<T> ,你也应该实现 IComparable 。IComparable 的参数类型为 System.Object 。你需要在运行时对参数进行检查。每次比较都是耗时的,你必须重新解读参数的类型:
```
和 IComparer <t>实现排序关系" style="display: none;">public struct Customer : IComparable<Customer>, IComparable
{
private readonly string name;
public Customer(string name)
{
this.name = name;
}
#region IComparable<Customer> Members
public int CompareTo(Customer other)
{
return name.CompareTo(other.name);
}
#endregion
#region IComparable Members
int IComparable.CompareTo(object obj)
{
if (!(obj is Customer))
throw new ArgumentException("Argument is not a Customer", "obj");
Customer otherCustomer = (Customer)obj;
return this.CompareTo(otherCustomer);
}
#endregion
}</t>
```
注意到这个结构体显示实现了 IComparable 。这就保证调用之前的接口实现参数为 Object 类型版本的 CompareTo() 的代码。太不喜欢旧版本的 IComparable 。你不得不要对参数的运行时类型进行检查。不正确的代码可以合法调用使用任何参数调用 CompareTo 方法。更糟糕的是,合适的参数也必须经过封箱和拆箱来进行比较。这样每次比较多了额外的运行花费。对集合进行排序,使用 IComparable 平均进行了 nlg(n) 次比较。每次都会引起三次的封箱和拆箱操作。对于长度为1000的数组,会有20000次封箱和拆箱操作,平均:nlg(n) 大约为7000,并且每次比较有3次封箱和拆箱的操作。
你可能会奇怪为什么你需要实现非泛型的 IComarable 接口。有两个理由。首先,这只是简单的向后兼容。你的类型交互的代码在 .NET 2.0之前创建的。这意味着支持泛型之前的接口。第二,即使现代的代码都会避免使用泛型,当它是基于反射。反射可能使用泛型,但是这比没有泛型定义的反射困难得多。支持非泛型版本的 IComparable 接口使得你的类型很容易使用利用反射的算法。
因为旧版本的 IComparable.CompareTo() 已经被接口显式实现,它只能通过 IComparable 引用调用。你 Customer struct 的使用者可以获得类型安排的比较,但类型不安全的比较是不可访问的。下面无辜的错误是不会通过编译:
```
和 IComparer <t>实现排序关系" style="display: none;">Customer c1;
Employee e1;
if (c1.CompareTo(e1) > 0)
Console.WriteLine("Customer one is greater");</t>
```
这不能通过编译因为参数对于 public Customer.CompareTo(Customer right) 方法是错误的。 IComparable.CompareTo(object right) 方法是不可访问的。你只能通过显式类型转换才能访问 IComparable 方法:
```
和 IComparer <t>实现排序关系" style="display: none;">Customer c1 = new Customer();
Employee e1 = new Employee();
if ((c1 as IComparable).CompareTo(e1) > 0)
Console.WriteLine("Customer one is greater");</t>
```
当你实现 IComparable ,使用显式的接口实现并提供一个强类型的 public 重写。强类型的重写提供性能而且减少一些人错误使用 CompareTo 方法的概率。你没有看到 .NET 框架使用 Sort 函数的所有优势,因为它通过接口指针访问 CompareTo() 方法(查看原则22),但是代码知道两个比较对象的类型会有更好的性能。
我们对 Customer struct 进行最后的小改变。C# 语言运行你重写标准关系操作符。这些可以充分利用类型安全的 CompareTo() 方法:
```
和 IComparer <t>实现排序关系" style="display: none;">public struct Customer : IComparable<Customer>, IComparable
{
private readonly string name;
public Customer(string name)
{
this.name = name;
}
#region IComparable<Customer> Members
public int CompareTo(Customer other)
{
return name.CompareTo(other.name);
}
#endregion
#region IComparable Members
int IComparable.CompareTo(object obj)
{
if (!(obj is Customer))
throw new ArgumentException("Argument is not a Customer", "obj");
Customer otherCustomer = (Customer)obj;
return this.CompareTo(otherCustomer);
}
#endregion
// Relational Operators.
public static bool operator <(Customer left, Customer right)
{
return left.CompareTo(right) < 0;
}
public static bool operator <=(Customer left, Customer right)
{
return left.CompareTo(right) <= 0;
}
public static bool operator >(Customer left, Customer right)
{
return left.CompareTo(right) > 0;
}
public static bool operator >=(Customer left, Customer right)
{
return left.CompareTo(right) >= 0;
}
}</t>
```
这就是标准的 Customer 的排序:通过名字。后面你必须创建对所有消费者根据收入的排序。你还是需要定义在 Customer struct 内的正轨的比较函数,即通过名字进行排序。在泛型成为 .NET 框架一部分后,很多 APIs 开发都会要求执行其他排序的 Comparison<T> 的委托。在 Customer 类中很简单创建一个执行其他排序的静态属性。例如,下面这个委托比较两个消费者的收入:
```
和 IComparer <t>实现排序关系" style="display: none;">public static Comparison<Customer> CompareByReview
{
get
{
return (left,right) =>
left.revenue.CompareTo(right.revenue);
}
}</t>
```
旧的类库会要求使用 IComparer 接口的类似功能。 IComparer 提供可选的标准没有泛型的排序。任何发布在 1.x .NET FCL 的 IComparable 实现方法都提供通过 IComparer 排序的重写。因为你是 Customer struct 的作者,你可以为次在 Customer struct 内部创建一个 pirvate 嵌套类( RevenueComparer )。它会暴露 Customer strcut 的一个静态属性:
```
和 IComparer <t>实现排序关系" style="display: none;">public struct Customer : IComparable<Customer>, IComparable
{
private readonly string name;
private double revenue;
public Customer(string name, double revenue)
{
this.name = name;
this.revenue = revenue;
}
#region IComparable<Customer> Members
public int CompareTo(Customer other)
{
return name.CompareTo(other.name);
}
#endregion
#region IComparable Members
int IComparable.CompareTo(object obj)
{
if (!(obj is Customer))
throw new ArgumentException("Argument is not a Customer", "obj");
Customer otherCustomer = (Customer)obj;
return this.CompareTo(otherCustomer);
}
#endregion
// Relational Operators.
public static bool operator <(Customer left, Customer right)
{
return left.CompareTo(right) < 0;
}
public static bool operator <=(Customer left, Customer right)
{
return left.CompareTo(right) <= 0;
}
public static bool operator >(Customer left, Customer right)
{
return left.CompareTo(right) > 0;
}
public static bool operator >=(Customer left, Customer right)
{
return left.CompareTo(right) >= 0;
}
private static RevenueComparer revComp = null;
// return an object that implements IComparer
// use lazy evaluation to create just one.
public static IComparer<Customer> RevenueCompare
{
get
{
if (revComp == null)
revComp = new RevenueComparer();
return revComp;
}
}
public static Comparison<Customer> CompareByReview
{
get
{
return (left,right) =>
left.revenue.CompareTo(right.revenue);
}
}
// Class to compare customers by revenue.
// This is always used via the interface pointer,
// so only provide the interface override.
private class RevenueComparer : IComparer<Customer>
{
#region IComparer<Customer> Members
int IComparer<Customer>.Compare(Customer left, Customer right)
{
return left.revenue.CompareTo(right.revenue);
}
#endregion
}
}</t>
```
最后的 Customer struct 版本,内嵌了 RevenueComparer ,你可以根据名字顺序,自然顺序进行排序,而且提供根据消费者收入排序实现的 IComparer 接口的可选排序。如果你不能访问 Customer 类的代码,你可以使用 public IComparer 的属性对消费者进行排序。当你不能访问到类的代码,就好像你对 .NET 框架的类使用不同的排序,你应该使用这种用法。
在本原则中我还没有提到 Equals() 或 == 操作符(查看原则6)。排序关系和相等是不同的操作。你不需要在排序关系中实现相等比较。事实上,引用类型通常根据对象内容实现排序,而相等是基于对象是否是同一个对象来判断。 CompareTo() 返回0,即使 Equals() 返回false。这是完全合法的。相等和排序关系没有必要相同。
IComparable 和 IComparer 是为你类型提供排序关系的标准机制。IComparable 主要用在自然排序中。当你实现 IComparable ,你也应该重写和 IComparable 排序一直的比较操作符(< ,> ,<= ,>= )。 IComparable.CompareTo() 使用的是 System.Object 参数,所以你还应该提供具体类型的 CompareTo() 方法的重写。 IComparer 可以提供另外的排序或者当类型没有为你提供的排序。
小结:
每天只能发原创博客两篇,先占个位置,未完待续!
终于整完这篇了,今天刚好是下半年的第一天(虽然现在已经是7月2日的凌晨1:20了),上半年因为身体状态不行,就一直耽搁了,虽然我要更加努力!
欢迎各种不爽,各种喷,写这个纯属个人爱好,秉持”分享“之德!
有关本书的其他章节翻译请[点击查看](/category/297763),转载请注明出处,尊重原创!
如果您对D.S.Qiu有任何建议或意见可以在文章后面评论,或者发邮件(gd.s.qiu@gmail.com)交流,您的鼓励和支持是我前进的动力,希望能有更多更好的分享。
转载请在**文首**注明出处:[http://dsqiu.iteye.com/blog/2087383](/blog/2087383)
更多精彩请关注D.S.Qiu的博客和微博(ID:静水逐风)
- 第一章 C# 语言习惯
- 原则1:使用 属性(Poperty)代替可直接访问的数据成员(Data Member)
- 原则2:偏爱 readonly 而不是 const
- 原则3:选择 is 或 as 而不是强制类型转换
- 原则4:使用条件特性(conditional attribute)代替 #if
- 原则5:总是提供 ToString()
- 原则6:理解几个不同相等概念的关系
- 原则7:明白 GetHashCode() 的陷阱
- 原则8:优先考虑查询语法(query syntax)而不是循环结构
- 原则9:在你的 API 中避免转换操作
- 原则10:使用默认参数减少函数的重载
- 原则11:理解小函数的魅力
- 第二章 .NET 资源管理
- 原则12:选择变量初始化语法(initializer)而不是赋值语句
- 原则13:使用恰当的方式对静态成员进行初始化
- 原则14:减少重复的初始化逻辑
- 原则15:使用 using 和 try/finally 清理资源
- 原则16:避免创建不需要的对象
- 原则17:实现标准的 Dispose 模式
- 原则17:实现标准的 Dispose 模式
- 原则18:值类型和引用类型的区别
- 原则19:确保0是值类型的一个有效状态
- 原则20:更倾向于使用不可变原子值类型
- 第三章 用 C# 表达设计
- 原则21:限制你的类型的可见性
- 原则22:选择定义并实现接口,而不是基类
- 原则23:理解接口方法和虚函数的区别
- 原则24:使用委托来表达回调
- 原则25:实现通知的事件模式
- 原则26:避免返回类的内部对象的引用
- 原则27:总是使你的类型可序列化
- 原则28:创建大粒度的网络服务 APIs
- 原则29:让接口支持协变和逆变
- 第四章 和框架一起工作
- 原则30:选择重载而不是事件处理器
- 原则31:用 IComparable&lt;T&gt; 和 IComparer&lt;T&gt; 实现排序关系
- 原则32:避免 ICloneable
- 原则33:只有基类更新处理才使用 new 修饰符
- 原则34:避免定义在基类的方法的重写
- 原则35:理解 PLINQ 并行算法的实现
- 原则36:理解 I/O 受限制(Bound)操作 PLINQ 的使用
- 原则37:构造并行算法的异常考量
- 第五章 杂项讨论
- 原则38:理解动态(Dynamic)的利与弊
- 原则39:使用动态对泛型类型参数的运行时类型的利用
- 原则40:使用动态接收匿名类型参数