数据结构(C++) 第三版 邓俊辉 - 向量、数组 PDF

第2章 向量  §2.1 从数组刡向量 第2章 向量 数据结构是数据项的结构化集合，其结构性表现为数据项之间的相互联系及作用，也可以理 解为定义于数据项之间的某种逻辑次序。根据这种逻辑次序的复杂程度，大致可以将各种数据结 构划分...

第2章 向量  §2.1 从数组刡向量 第2章 向量 数据结构是数据项的结构化集合，其结构性表现为数据项之间的相互联系及作用，也可以理 解为定义于数据项之间的某种逻辑次序。根据这种逻辑次序的复杂程度，大致可以将各种数据结 构划分为线性结构、半线性结构与非线性结构三大类。在线性结构中，各数据项按照一个线性次 序构成一个整体。最为基本的线性结构统称为序列（sequence），根据其中数据项的逻辑次序 与其物理存储地址的对应关系不同，又可进一步地将序列区分为向量（vector）和列表（list）。 在向量中，所有数据项的物理存放位置与其逻辑次序完全吻合，此时的逻辑次序也称作秩 （rank）；而在列表中，逻辑上相邻的数据项在物理上未必相邻，而是采用间接定址的方式通 过封装后的位置（position）相互引用。 本章的讲解将围绕向量结构的高效实现而逐步展开，包括其作为抽象数据类型的接口规范以 及对应的算法，尤其是高效维护动态向量的技巧。此外，还将针对有序向量，系统介绍经典的查 找与排序算法，并就其性能做一分析对比，这也是本章的重点与难点所在。最后，还将引入复杂 度下界的概念，并通过建立比较树模型，针对基于比较式算法给出复杂度下界的统一界定方法。 §2.1 从数组到向量 2.1.1 数组 C、C++和Java等程序设计语言，都将数组作为一种内置的数据类型，支持对一组相关元素 的存储组织与访问操作。具体地，若集合S由n个元素组成，且各元素之间具有一个线性次序，则 可将它们存放于起始于地址A、物理位置连续的一段存储空间，并统称作数组（array），通常 以A作为该数组的标识。具体地，数组A[]中的每一元素都唯一对应于某一下标编号，在多数高 级程序设计语言中，一般都是从0开始编号，依次是0号、1号、2号、...、n-1号元素，记作： A = { a0, a1,..., an-1 } 或者 A[0, n) = { A, A,..., A[n - 1] } 其中，对于任何0  i < j < n，A[i]都是A[j]的前驱（predecessor），A[j]都是A[i] 的后继（successor）。特别地，对于任何i  1，A[i - 1]称作A[i]的直接前驱（intermediate predecessor ） ; 对 于 任 何 i  n - 2 ， A[i + 1] 称 作 A[i] 的 直 接 后 继 （ intermediate successor）。任一元素的所有前驱构成其前缀（prefix），所有后继构成其后缀（suffix）。 采用这一编号规范，不仅可以使得每个元素都通过下标唯一指代，而且可以使我们直接访问 到任一元素。这里所说的“访问”包含读取、修改等基本操作，而“直接”则是指这些操作都可 28 以在常数时间内完成只要从数组所在空间的起始地址A出发，即可根据每一元素的编号，经 过一次乘法运算和一次加法运算，获得待访问元素的物理地址。具体地，若数组A[]存放空间的 起始地址为A，且每个元素占用s个单位的空间，则元素A[i]对应的物理地址为： A + i  s 因其中元素的物理地址与其下标之间满足这种线性关系，故亦称作线性数组（linear array）。  第2章 向量 §2.2 接口 2.1.2 向量 按照面向对象思想中的数据抽象原则，可对以上的数组结构做一般性推广，使得其以上特性 更具普遍性。向量（vector）就是线性数组的一种抽象与泛化，它也是由具有线性次序的一组 元素构成的集合V = { v0, v1,..., vn-1 }，其中的元素分别由秩相互区分。 各元素的秩（rank）互异，且均为[0, n)内的整数。具体地，若元素e的前驱元素共计r个， 则其秩就是r。以此前介绍的线性递归为例，运行过程中所出现过的所有递归实例，按照相互调 用的关系可构成一个线性序列。在此序列中，各递归实例的秩反映了它们各自被创建的时间先后， 每一递归实例的秩等于早于它出现的实例总数。反过来，通过r亦可唯一确定e = vr。这是向量 特有的元素访问方式，称作“循秩访问”（call-by-rank）。 经如此抽象之后，我们不再限定同一向量中的各元素都属于同一基本类型，它们本身可以是 来自于更具一般性的某一类的对象。另外，各元素也不见得同时具有某一数值属性，故而并不保 证它们之间能够相互比较大小。 以下首先从向量最基本的接口出发，设计并实现与之对应的向量模板类。然后在元素之间具 有大小可比性的假设前提下，通过引入通用比较器或重载对应的操作符明确定义元素之间的大小 判断依据，并强制要求它们按此次序排列，从而得到所谓有序向量，并介绍和分析此类向量的相 关算法及其针对不同要求的各种实现版本。 §2.2 接口 2.2.1 ADT接口 作为一种抽象数据类型，向量对象应支持如下操作接口。 表2.1 向量ADT支持癿操作接口 操 作 接 口 功 能 适 用 对 象 size() 报告向量弼前癿觃模（元素总数） 向量 get(r) 获叏秩为r癿元素 向量 put(r, e) 用e替换秩为r元素癿数值 向量 insert(r, e) e作为秩为r元素揑入，原后继元素依次后秱 向量 remove(r) 初除秩为r癿元素，迒回诠元素中原存放癿对象 向量 disordered() 刞断所有元素是否已按非降序排列 向量 sort() 调整各元素癿位置，使乀按非降序排列 向量 find(e) 查找等亍e且秩最大癿元素 向量 search(e) 查找目标元素e，迒回丌大亍e且秩最大癿元素 有序向量 deduplicate() 剔除重复元素 向量 29 uniquify() 剔除重复元素 有序向量 traverse() 遍历向量幵统一处理所有元素，处理斱法由函数对象指定 向量 以上向量操作接口，可能有多种具体的实现方式，计算复杂度也不尽相同。而在引入秩的概 念并将外部接口与内部实现分离之后，无论采用何种具体的方式，符合统一外部接口规范的任一 实现均可直接地相互调用和集成。  §2.2 接口 第2章 向量 2.2.2 操作实例 按照表2.1定义的ADT接口，表2.2给出了一个整数向量从被创建开始，通过ADT接口依次实 施一系列操作的过程。请留意观察，向量内部各元素秩的逐步变化过程。 表2.2 向量操作实例 操作 输出 向量组成（自左向右） 操作 输出 向量组成（自左向右） 刜始化 disordered() 3 4 3 7 4 9 6 insert(0, 9) 9 find(9) 4 4 3 7 4 9 6 insert(0, 4) 4 9 find(5) -1 4 3 7 4 9 6 insert(1, 5) 4 5 9 sort() 3 4 4 6 7 9 put(1, 2) 4 2 9 disordered() 0 3 4 4 6 7 9 get(2) 9 4 2 9 search(1) -1 3 4 4 6 7 9 insert(3, 6) 4 2 9 6 search(4) 2 3 4 4 6 7 9 insert(1, 7) 4 7 2 9 6 search(8) 4 3 4 4 6 7 9 remove(2) 2 4 7 9 6 search(9) 5 3 4 4 6 7 9 insert(1, 3) 4 3 7 9 6 search(10) 5 3 4 4 6 7 9 insert(3, 4) 4 3 7 4 9 6 uniquify() 3 4 6 7 9 size() 6 4 3 7 4 9 6 search(9) 4 3 4 6 7 9 2.2.3 Vector模板类 按照表2.1确定的向量ADT接口，可定义Vector模板类如代码2.1所示。 1 typedef int Rank; //秩 2 #define DEFAULT_CAPACITY 3 //默讣癿刜始容量（实际应用中可讴置为更大） 3 4 template class Vector { //向量模板类 5 protected: 6 Rank _size; int _capacity; T* _elem; //觃模、容量、数据匙 7 void copyFrom(T const* A, Rank lo, Rank hi); //复刢数组匙间A[lo, hi) 8 void expand(); //空间丌足时扩容 9 void shrink(); //装填因子过小时压缩 10 bool bubble(Rank lo, Rank hi); //扫描交换 11 void bubbleSort(Rank lo, Rank hi); //起泡排序算法 12 Rank max(Rank lo, Rank hi); //选叏最大元素 13 void selectionSort(Rank lo, Rank hi); //选择排序算法 30 14 void merge(Rank lo, Rank mi, Rank hi); //弻幵算法 15 void mergeSort(Rank lo, Rank hi); //弻幵排序算法 16 Rank partition(Rank lo, Rank hi); //轴点极造算法 17 void quickSort(Rank lo, Rank hi); //快速排序算法 18 void heapSort(Rank lo, Rank hi); //堆排序（秴后结合完全堆讱解） 19 public: 第2章 向量 §2.2 接口 20 // 极造函数 21 Vector(int c = DEFAULT_CAPACITY, int s = 0, T v = 0) //容量为c、觃模为s、所有元素刜始为v 22 { _elem = new T[_capacity = c]; for (_size = 0; _size < s; _elem[_size++] = v); } //s = _size) ? -1 : search(e, 0, _size); } 37 Rank search(T const& e, Rank lo, Rank hi) const; //有序向量匙间查找 38 // 可写讵问接口 39 T& operator[](Rank r) const; //重载下标操作符，可以类似亍数组形式引用各元素 40 Vector & operator=(Vector const&); //重载赋值操作符，以便直接克隆向量 41 T remove(Rank r); //初除秩为r癿元素 42 int remove(Rank lo, Rank hi); //初除秩在匙间[lo, hi)乀内癿元素 43 Rank insert(Rank r, T const& e); //揑入元素 44 Rank insert(T const& e) { return insert(_size, e); } //默讣作为末元素揑入 45 void sort(Rank lo, Rank hi); //对[lo, hi)排序 46 void sort() { sort(0, _size); } //整体排序 47 void unsort(Rank lo, Rank hi); //对[lo, hi)置乱 48 void unsort() { unsort(0, _size); } //整体置乱 49 int deduplicate(); //无序去重 50 int uniquify(); //有序去重 51 // 遍历 52 void traverse(void (*)(T&)); //遍历（使用函数指针，叧读戒尿部性修改） 53 template void traverse(VST&); //遍历（使用函数对象，可全尿性修改） 54 }; //Vector 代码2.1 向量模板类Vector 31 这里通过模板参数T，指定向量元素的类型。于是，以Vector或Vector之类 的形式，可便捷地引入存放整数或浮点数的向量；而以Vector之类的形式，则 可直接定义存放字符的二维向量等。这一技巧有利于提高数据结构选用的灵活性和运行效率，并 减少出错，因此将在本书中频繁使用。 在表2.1所列基本操作接口的基础上，这里还扩充了一些接口。比如，基于size()直接实现  §2.3 极造不枂极 第2章 向量 的判空接口empty()，以及区间删除接口remove(lo, hi)、区间查找接口find(e, lo, hi)等。 它们多为上述基本接口的扩展或变型，可使代码更为简洁易读，并提高计算效率。 这里还提供了sort()接口，以将向量转化为有序向量。为此可有多种排序算法供选用，本 章及后续章节，将陆续介绍它们的原理、实现并分析其效率。排序之后，向量的很多操作都可更 加高效地完成，其中最基本和最常用的莫过于查找。因此，这里还针对有序向量提供了search() 接口，并将详细介绍若干种相关的算法。为便于对sort()算法的测试，这里还设有一个unsort() 接口，以将向量随机置乱。在讨论这些接口之前，我们首先介绍基本接口的实现。 §2.3 构造与析构 由代码2.1可见，向量结构在内部维护一个元素类型为T的私有数组_elem[]：其容量由私有 变量_capacity指示；有效元素的数量（即向量当前的实际规模），则由_size指示。此外还进 一步地约定，在向量元素的秩、数组单元的逻辑编号以及物理地址之间，具有如下对应关系： 向量中秩为r的元素，对应于内部数组中的_elem[r]，其物理地址为_elem + r 因此，向量对象的构造与析构，将主要围绕这些私有变量和数据区的初始化与销毁展开。 2.3.1 默认构造方法 与所有的对象一样，向量在使用之前也需首先被系统创建借助构造函数（constructor） 做初始化（initialization）。由代码2.1可见，这里为向量重载了多个构造函数。 其中默认的构造方法是，首先根据创建者指定的初始容量，向系统申请空间，以创建内部私 有数组_elem[]；若容量未明确指定，则使用默认值DEFAULT_CAPACITY。接下来，鉴于初生的 向量尚不包含任何元素，故将指示规模的变量_size初始化为0。 整个过程顺序进行，没有任何迭代，故若忽略用于分配数组空间的时间，共需常数时间。 2.3.2 基于复制的构造方法 向量的另一典型创建方式，是以某个已有的向量或数组为蓝本，进行（局部或整体的）克隆。 代码2.1中虽为此功能重载了多个接口，但无论是已封装的向量或未封装的数组，无论是整体还 是区间，在入口参数合法的前提下，都可归于如代码2.2所示的统一的copyFrom()方法： 1 template //元素类型 2 void Vector::copyFrom(T const* A, Rank lo, Rank hi) { //以数组匙间A[lo, hi)为蓝本复刢向量 3 _elem = new T[_capacity = 2 * (hi - lo)]; _size = 0; //分配空间，觃模清零 4 while (lo < hi) //A[lo, hi)内癿元素逐一 5 _elem[_size++] = A[lo++]; //复刢至_elem[0, hi - lo) 32 6 } 代码2.2 基二复刢癿向量极造器 copyFrom()首先根据待复制区间的边界，换算出新向量的初始规模；再以双倍的容量，为 内部数组_elem[]申请空间。最后通过一趟迭代，完成区间A[lo, hi)内各元素的顺次复制。 若忽略开辟新空间所需的时间，运行时间应正比于区间宽度，即O(hi - lo) = O(_size)。  第2章 向量 §2.4 劢态空间管理 需强调的是，由于向量内部含有动态分配的空间，默认的运算符"="不足以支持向量之间的 直接赋值。例如，6.3节将以二维向量形式实现图邻接表，其主向量中的每一元素本身都是一维 向量，故通过默认赋值运算符，并不能复制向量内部的数据区。 为适应此类赋值操作的需求，可如代码2.3所示，重载向量的赋值运算符。 1 template Vector& Vector::operator=(Vector const& V ) { //重载赋值操作符 2 if (_elem) delete [] _elem; //释放原有内容 3 copyFrom(V._elem, 0, V.size()); //整体复刢 4 return *this; //迒回弼前对象癿引用，以便链式赋值 5 } 代码2.3 重轲向量赋值操作符 2.3.3 析构方法 与所有对象一样，不再需要的向量，应借助析构函数（destructor）及时清理（cleanup）， 以释放其占用的系统资源。与构造函数不同，同一对象只能有一个析构函数，不得重载。 向量对象的析构过程，如代码2.1中的方法~Vector()所示：只需释放用于存放元素的内部 数组_elem[]，将其占用的空间交还操作系统。_capacity和_size之类的内部变量无需做任何 处理，它们将作为向量对象自身的一部分被系统回收，此后既无需也无法被引用。 若不计系统用于空间回收的时间，整个析构过程只需O(1)时间。 同样地，向量中的元素可能不是程序语言直接支持的基本类型。比如，可能是指向动态分配 对象的指针或引用，故在向量析构之前应该提前释放对应的空间。出于简化的考虑，这里约定并 遵照“谁申请谁释放”的原则。究竟应释放掉向量各元素所指的对象，还是需要保留这些对象， 以便通过其它指针继续引用它们，应由上层调用者负责确定。 §2.4 动态空间管理 2.4.1 静态空间管理 内部数组所占物理空间的容量，若在向量的生命期内不允许调整，则称作静态空间管理策略。 很遗憾，该策略的空间效率难以保证。一方面，既然容量固定，总有可能在此后的某一时刻，无 法加入更多的新元素即导致所谓的上溢（overflow）。例如，若使用向量来记录网络访问 日志，则由于插入操作远多于删除操作，必然频繁溢出。注意，造成此类溢出的原因，并非系统 不能提供更多的空间。另一方面反过来，即便愿意为降低这种风险而预留出部分空间，也很难在 程序执行之前，明确界定一个合理的预留量。以上述copyFrom()方法为例，即便将容量取作初 始规模的两倍，也只能保证在此后足够长的一段时间内（而并非永远）不致溢出。 33 向量实际规模与其内部数组容量的比值（即_size/_capacity），亦称作装填因子（load factor），它是衡量空间利用率的重要指标。从这一角度，上述难题可归纳为： 如何才能保证向量的装填因子既不致于超过1，也不致于太接近于0？ 为此，需要改用动态空间管理策略。其中一种有效的方法，即使用所谓的可扩充向量。  §2.4 劢态空间管理 第2章 向量 2.4.2 可扩充向量 经过一段时间的生长，每当身体无法继续为其外壳所容纳，蝉就会蜕去外壳，同时换上一身 更大的外壳。扩充向量（extendable vector）的原理，与之相仿。若内部数组仍有空余，则 操作可照常执行。每经一次插入（删除），可用空间都会减少（增加）一个单元（图2.1(a)）。 一旦可用空间耗尽（图(b)），就动态地扩大内部数组的容量。这里的难点及关键在于： 如何实现扩容？新的容量取作多少才算适宜？ 首先解决前一问题。直接在原有物理空间的基础上追加空间？这并不现实。数组特有的定址 方式要求，物理空间必须地址连续，而我们却无法保证，其尾部总是预留了足够空间可供拓展。 图2.1 可扩充向量癿溢出处理 一种可行的方法，如图2.1(c~e)所示。我们需要另行申请一个容量更大的数组B[]（图(c)）， 并将原数组中的成员集体搬迁至新的空间（图(d)），此后方可顺利地插入新元素e而不致溢出 （图(e)）。当然，原数组所占的空间，需要及时释放并归还操作系统。 2.4.3 扩容 基于以上策略的扩容算法expand()，可实现如代码2.4所示。 1 template void Vector::expand() { //向量空间丌足时扩容 2 if (_size < _capacity) return; //尚未满员时，丌必扩容 3 if (_capacity < DEFAULT_CAPACITY) _capacity = DEFAULT_CAPACITY; //丌低亍最小容量 4 T* oldElem = _elem; _elem = new T[_capacity N。首先定义如下函数： size(n) = 连续插入n个元素后向量的规模 capacity(n) = 连续插入n个元素后数组的容量 T(n) = 为连续插入n个元素而花费于扩容的时间 35 其中，向量规模从N开始随着操作的进程逐步递增，故有： size(n) = N + n 既然不致溢出，故装填因子绝不会超过100%。同时，这里的扩容采用了“懒惰”策略 只有在的确即将发生溢出时，才不得不将容量加倍因此装填因子也始终不低于50%。  §2.4 劢态空间管理 第2章 向量 概括起来，始终应有： size(n)  capacity(n) < 2∙size(n) 考虑到N为常数，故有： capacity(n) = (size(n)) = (n) 容量以2为比例按指数速度增长，在容量达到capacity(n)之前，共做过(log2n)次扩容， 每次扩容所需时间线性正比于当时的容量（或规模），且同样以2为比例按指数速度增长。因此， 消耗于扩容的时间累计不过： T(n) = 2N + 4N + 8N +... + capacity(n) < 2∙capacity(n) = (n) 将其分摊到其间的连续n次操作，单次操作所需的分摊运行时间应为O(1)。 其它扩容策略 以上分析确凿地说明，基于加倍策略的动态扩充数组不仅可行，而且就分摊复杂度而言效率 也足以令人满意。当然，并非任何扩容策略都能保证如此高的效率。比如，早期可扩充向量多采 用另一策略：一旦有必要，则追加固定数目的单元。实际上，无论采用的固定常数多大，在最坏 情况下，此类数组单次操作的分摊时间复杂度都将高达(n)（习题[2-3]）。 2.4.5 缩容 导致低效率的另一情况是，向量的实际规模可能远远小于内部数组的容量。比如在连续的一 系列操作过程中，若删除操作远多于插入操作，则装填因子极有可能远远小于100%，甚至非常 接近于0。当装填因子低于某一阈值时，我们称数组发生了下溢（underflow）。 尽管下溢不属于必须解决的问题，但在格外关注空间利用率的场合，发生下溢时也有必要适 当缩减内部数组容量。代码2.5给出了一个动态缩容shrink()算法： 1 template void Vector::shrink() { //装填因子过小时压缩向量所占空间 2 if (_capacity < DEFAULT_CAPACITY >= 1]; //容量减半 5 for (int i = 0; i < _size; i++) _elem[i] = oldElem[i]; //复刢原向量内容 6 delete [] oldElem; //释放原空间 7 } 代码2.5 向量内部功能shrink() 可见，每次删除操作之后，一旦空间利用率已降至某一阈值以下，该算法随即申请一个容量 减半的新数组，将原数组中的元素逐一搬迁至其中，最后将原数组所占空间交还操作系统。这里 以25%作为装填因子的下限，但在实际应用中，为避免出现频繁交替扩容和缩容的情况，可以选 36 用更低的阈值，甚至取作0（相当于禁止缩容）。 与expand()操作类似，尽管单次shrink()操作需要线性量级的时间，但其分摊复杂度亦为 O(1)（习题[2-4]）。实际上shrink()过程等效于expand()的逆过程，这两个算法相互配合， 在不致实质地增加接口操作复杂度的前提下，保证了向量内部空间的高效利用。当然，就单次扩 容或缩容操作而言，所需时间的确会高达(n)，因此在对单次操作的执行速度极其敏感的应用 场合以上策略并不适用，其中缩容操作甚至可以完全不予考虑。  第2章 向量 §2.5 常觃向量 §2.5 常规向量 2.5.1 直接引用元素 与数组直接通过下标访问元素的方式（形如“A[i]”）相比，向量ADT所设置的get()和put() 接口都显得不甚自然。毕竟，前一访问方式不仅更为我们所熟悉，同时也更加直观和便捷。那么， 在经过封装之后，对向量元素的访问可否沿用数组的方式呢？答案是肯定的。 解决的方法之一就是重载操作符“[]”，具体实现如代码2.6所示。 1 template T& Vector::operator[](Rank r) const //重载下标操作符 2 { return _elem[r]; } // assert: 0 0; i--) //自后向前 3 swap(V[i - 1], V[rand() % i]); //V[i - 1]不V[0, i)中某一随机元素交换 4 } 代码2.7 向量整体置乱算法permute() 该算法从待置乱区间的末元素开始，逆序地向前逐一处理各元素。如图2.2(a)所示，对每 一个当前元素V[i - 1]，先通过调用rand()函数在[0, i)之间等概率地随机选取一个元素，再 令二者互换位置。注意，这里的交换操作swap()，隐含了三次基于重载操作符“[]”的赋值。 于是如图(b)所示，每经过一步这样的迭代，置乱区间都会向前拓展一个单元。因此经过O(n) 步迭代之后，即实现了整个向量的置乱。 37 图2.2 向量整体置乱算法permute()癿迭代过秳 在软件测试、仿真模拟等应用中，随机向量的生成都是一项至关重要的基本操作，直接影响 到测试的覆盖面或仿真的真实性。从理论上说，使用这里的算法permute()，不仅可以枚举出同 一向量所有可能的排列，而且能够保证生成各种排列的概率均等（习题[2-6]）。  §2.5 常觃向量 第2章 向量 区间置乱接口 为便于对各种向量算法的测试与比较，这里不妨将以上permute()算法封装至向量ADT中， 并如代码2.8所示，对外提供向量的置乱操作接口Vector::unsort()。 1 template void Vector::unsort(Rank lo, Rank hi) { //等概率随机置乱向量匙间[lo, hi) 2 T* V = _elem + lo; //将子向量_elem[lo, hi)规作另一向量V[0, hi - lo) 3 for (Rank i = hi - lo; i > 0; i--) //自后向前 4 swap(V[i - 1], V[rand() % i]); //将V[i - 1]不V[0, i)中某一元素随机交换 5 } 代码2.8 向量区间置乱接口unsort() 通过该接口，可以均匀地置乱任一向量区间[lo, hi)内的元素，故通用性有所提高。可见， 只要将该区间等效地视作另一向量V，即可从形式上完整地套用以上permute()算法的流程。 尽管如此，还请特别留意代码2.7与代码2.8的细微差异：后者是通过下标，直接访问内部 数组的元素；而前者则是借助重载的操作符“[]”，通过秩间接地访问向量的元素。 2.5.3 判等器与比较器 从算法的角度来看，“判断两个对象是否相等”与“判断两个对象的相对大小”都是至关重 要的操作，它们直接控制着算法执行的分支方向，因此也是算法的“灵魂”所在。在本书中为了 以示区别，前者多称作“比对”操作，后者多称作“比较”操作。当然，这两种操作之间既有联 系也有区别，不能相互替代。比如，有些对象只能比对但不能比较；反之，支持比较的对象未必 支持比对。不过，出于简化的考虑，在很多场合并不需要严格地将二者区分开来。 算法实现的简洁性与通用性，在很大程度上体现于：针对整数等特定数据类型的某种实现， 可否推广至可比较或可比对的任何数据类型，而不必关心如何定义以及判定其大小或相等关系。 若能如此，我们就可以将比对和比较操作的具体实现剥离出来，直接讨论算法流程本身。 为此，通常可以采用两种方法。其一，将比对操作和比较操作分别封装成通用的判等器和比 较器。其二，在定义对应的数据类型时，通过重载"