3. 记录比较¶
3.1. 记录比较¶
要想对一些东西排序，我们必须能够比较它们，判断哪个更大。 怎么比较两个东西呢？ 如果我们要排序或查找的只是简单的整数值，这就不是个有趣的 问题。 直接用"<"或">"这类标准比较运算符即可。 即使要存储的是字符串，大多数编程语言也内置了按字母顺序 比较字符串的函数。 但我们通常不想在数据结构里只存整数或字符串。 我们通常想存的是记录，一条记录由多个值组成，比如姓名、 地址和电话号码。 这种情况下，怎么"比较"记录、判断哪条"更小"呢？ 我们不能直接用"<"来比较记录！ 几乎在所有这类情形中，我们真正感兴趣的其实是依据代表该 记录的某个特定字段的值来排序记录， 而这个字段本身是整数之类的简单类型。 这个字段被称为记录的 键 。
同样地，如果想在数据库中查找某条给定记录，该怎么描述我们 要找的东西？ 一条数据库记录可以只是一个数，也可能相当复杂，比如带有 许多不同类型字段的工资记录。 我们不想通过罗列并匹配记录的全部内容来描述要找的东西。 如果我们已经知道关于这条记录的一切，多半也就不需要找它了。 实际上，我们通常用键值来定义想要的记录。 例如，查找工资记录时，我们可能想找出与某个特定 ID 号匹配 的记录。 在这个例子中，ID 号就是 查找键 。
要实现排序或查找，我们要求键是 可比较 的。 至少，我们必须能对两个键做出可靠的判断：它们相等还是不等。 这就足以支持在记录数据库中做顺序查找，找出与给定键匹配的一条记录。 然而，我们通常希望键定义一个 全序 ， 即总能判断两个键中哪个更大。 使用具有全序关系的键类型，数据库实现者就有机会用某种 方式组织记录集合，让查找更高效。 一个例子是把记录按有序顺序存进数组，这样可以做二分查找。 所幸在实践中，大多数记录的大多数字段都是具有自然全序的 简单数据类型。 例如，整数、浮点数、双精度数和字符串都是全序的。
但如果我们想写一个通用的排序或查找函数，就需要一种通用的
办法来获取记录的键。
我们可以要求每条记录都有一个名为 .key() 的特定方法。
这听起来就是个好名字！
Java 和 C++ 这类语言为此提供了专门的基础设施（例如 Java 的
Comparable 接口，其中的 .compareTo() 方法定义了
两个对象比较的确切过程）。
但 Processing 和 JavaScript 这类语言没有。
可是，如果程序员已经把那个方法名用在了别的用途上怎么办？ 一个更大的问题是：如果程序员这次想以某个字段作为键 排序记录，之后又想用另一个字段呢？ 或者有时按一个键查找，有时按另一个键查找？ 问题在于，某个字段的"键身份"并不是记录固有的属性， 而是取决于上下文。 所以，你不能总指望能用自己喜欢的方法名（甚至 comparable 接口）来提取想要的键值。
另一种更通用的做法是提供一个函数或类—称为 比较器—， 它的职责是从记录中提取键。 比较器函数可以作为参数传入，比如在调用排序函数时传入。 这时，每当两条记录需要比较，就会调用这个比较器函数。 这样，传入不同的比较器函数就能处理不同的记录类型，或同一 记录内的不同字段。 在 Java（带泛型）或 C++（带模板）中，比较器类可以作为另 一个类定义的参数。 例如，二叉搜索树可以把一个比较器类作为 Java 的泛型参数。 这个比较器类负责处理两条记录之间的比较。
遗憾的是，尽管比较器灵活且几乎能应付所有情形，仍有少数 情况无法编写键提取方法。 这时比较器也无能为力。[1]
一个好的通用解决方案是在数据结构中显式存储 键值对 。 例如，想对一批记录排序时，可以把它们存进一个数组，其中 每个数组元素既包含该记录的键值，又包含指向记录本身的 指针。 这看起来要占很多额外空间，但请记住：我们随后可以在另一个 数组里存储指向这些记录的指针，用另一个字段作为键来 满足另一种用途。 记录本身无需复制。 下面是一个表示键值对的简单类。
// KVPair class definition
public class KVPair implements Comparable {
Comparable theKey;
Object theVal;
KVPair(Comparable k, Object v) { theKey = k; theVal = v; }
public int compareTo(Object it) throws ClassCastException {
if (it instanceof KVPair) // Compare two KVPair objects
return theKey.compareTo(((KVPair)it).key());
else if (it instanceof Comparable) // Compare against a key value
return theKey.compareTo(it);
else
throw new ClassCastException("Something comparable is expected.");
}
public Comparable key() { return theKey; }
public Object value() { return theVal; }
public String toString() {
String s = "(";
if (theKey != null) { s += theKey.toString(); }
else { s += "null"; }
s += ", ";
if (theVal != null) { s += theVal.toString(); }
else { s += "null"; }
s += ")";
return s;
}
}
// KVPair class definition
public class KVPair<K extends Comparable<K>, E> implements Comparable<KVPair<K, E>> {
K theKey;
E theVal;
KVPair(K k, E v) {
theKey = k;
theVal = v;
}
// Compare KVPairs
public int compareTo(KVPair<K,E> it) {
return theKey.compareTo(it.key());
}
// Compare against a key
public int compareTo(K it) {
return theKey.compareTo(it);
}
public K key() {
return theKey;
}
public E value() {
return theVal;
}
public String toString() {
String s = "(";
if (theKey != null) { s += theKey.toString(); }
else { s += "null"; }
s += ", ";
if (theVal != null) { s += theVal.toString(); }
else { s += "null"; }
s += ")";
return s;
}
}
// Container for a key-value pair
class KVPair: public Comparable {
public:
// Constructors
KVPair() : k(0), e(nullptr) {}
KVPair(const KVPair& KV): k(KV.k), e(KV.e) {}
KVPair& operator=(const KVPair&) = delete;
KVPair(int kval, void* eval) : k(kval), e(eval) {}
void print(std::ostream& ostr) const {
ostr << k;
}
bool operator <(const Comparable& other) const { // < operator
const KVPair& KVother = static_cast<const KVPair&>(other);
return k < KVother.k;
}
bool operator >(const Comparable& other) const { // > operator
const KVPair& KVother = static_cast<const KVPair&>(other);
return k > KVother.k;
}
bool operator <=(const Comparable& other) const { // <= operator
const KVPair& KVother = static_cast<const KVPair&>(other);
return k <= KVother.k;
}
bool operator >=(const Comparable& other) const { // >= operator
const KVPair& KVother = static_cast<const KVPair&>(other);
return k >= KVother.k;
}
KVPair& operator=(const Comparable& i) {
auto KV = static_cast<const KVPair&>(i);
k = KV.k;
e = KV.e;
return *this;
};
// Data member access functions
int key() { return k; }
void setKey(int ink) { k = ink; }
void* value() { return e; }
void setValue(void* ine) { e = ine; }
private:
int k;
void* e;
};
我们主要在各种 词典 实现和排序算法中需要
关心记录比较和键提取。
为了清晰简单，排序算法的可视化通常把它们显示成对数组中的
整数值进行操作。
但几乎没有人真的想对整数数组排序。
要有实用价值，真正的排序算法通常必须面对它排序的是记录
集合这一事实。
一个要在多种记录类型上工作的通用排序程序，必须以能处理
通用比较问题的方式来编写。
为了说明这一点，下面是一个
插入排序 的例子，
它实现为对存储支持 Comparable 接口的记录的数组工作。
注意，由于 KVPair 实现了 Comparable 接口，
KVPair 数组同样可以交给这个排序函数处理。
void inssort(int[] A) {
for (int i=1; i<A.length; i++) // Insert i'th record
for (int j=i; (j>0) && (A[j] < A[j-1]); j--)
swap(A, j, j-1);
}
void inssort(T[] A) {
for (int i=1; i<A.length; i++) // Insert i'th record
for (int j=i; (j>0) && (A[j].compareTo(A[j-1]) < 0); j--)
swap(A, j, j-1);
}
void inssort(Comparable* A[], int n) { // Insertion Sort
for (int i = 1; i < n; i++) // Insert i'th record
for (int j = i; (j > 0) && (*A[j] < *A[j-1]); j--)
swap(A, j, j-1);
}
下面是一些复习题，用来检验你对本模块内容的掌握。
