我们已经知道，字典类型的值有一个共同特点，即其中的元素值的迭代顺序是不确定的。但是在一些应用场景下，我们是需要固定的元素迭代顺序的。 我们在前面的章节中多次提到过，如果要使元素可排序就需要让数据类型实现sort.Interface接口类型。该接口类型中的方法Len、Less和Swap的含义分别是获取元素的数量、比较相邻元素的大小以及交换它们的位置。我们在基于数组类型或切片类型的自定义数据类型之上可以非常轻松地实现这几个方法。但是，对于基于字典类型的扩展数据类型来说，实现它们可就不那么容易了。因为字典类型值中的元素值是无序的。我们没有任何方法可以确定它们的位置以及与它们相邻的元素值。 因此，要想自定义一个有序字典类型，仅基于Go语言的字典类型是不可能实现的。我们应该使用一个元素有序的数据类型值作为辅助。依据这一思路，我声明了一个名为OrderedMap的结构体类型： type OrderedMap struct { keys []interface{} m map[interface{}]interface{} } 可以看到，该类型的基本结构中，除了一个字典类型的字段，还有一个切片类型的字段。为了让OrderedMap类型实现sort.Interface接口类型，我们需要为它添加如下几个方法： func (omap *OrderedMap) Len() int { return len(omap.keys) } func (omap *OrderedMap) Less(i, j int) bool { // 省略若干条语句 } func (omap *OrderedMap) Swap(i, j int) { omap.keys[i], omap.keys[j] = omap.keys[j], omap.keys[i] } 这样，*OrderedMap类型（注意，不是OrderedMap类型）就是一个sort.Interface接口类型的实现类型了。可以看到，我们在这些方法中操作的实际上都是OrderedMap类型中的字段keys的值。在Len方法中，我们以keys字段的值的长度作为结果值。而在Swap方法中，我们使用平行赋值语句交换的两个元素值也都是在keys字段的值中的。这就意味着，我们会使用字段keys的值的元素迭代顺序全权代表字段m的值的元素迭代顺序。 为了达到这个目的，我们就必须要在添加和删除字段m的值中的键值对的时候对字段keys的值进行完全同步的操作。在编写相关方法之前，我们先来关注一下刚刚提到却被省略实现的Less方法。 方法Less的功能是比较相邻的两个元素值的大小并返回判断结果。我们在上一章讲值的可比性与有序性的时候介绍过各种数据类型值的比较方法。已知，只有当值的类型具备有序性的时候，它才可能与其他的同类型值比较大小。Go语言规定，字典类型的键类型的值必须是可比的（即可判定两个该类型的值是否相等）。然而，在具有可比性的数据类型中只有一部分同时具备有序性。也就是说，我们只依靠Go语言本身对字典类型的键类型的约束是不够的。在Go语言中，具备有序性的预定义数据类型只有整数类型、浮点数类型和字符串类型。 类型OrderedMap中的字段keys是[]interface{}类型的。也就是说，我们总是需要比较两个interface{}类型值的大小。这显然是不可行的，因为接口类型的值只具有可比性而不具备有序性。所以，我们刚才声明的OrderedMap类型是不可用的。如果把keys字段的元素类型改为某一个具体的数据类型（整数类型、浮点数类型或字符串类型），虽然可以轻松编写出比较各个元素值大小的代码，但是这样做却会使OrderedMap类型的应用价值大打折扣。 总之，我们还需要重新审视一下将要创建的这个类型。 首先，我们先要对OrderedMap类型的主要功能需求进行收集和整理。实际上，这些需求都集中在对字段keys的值的操作上，如下所示。 字段keys的值中的元素值应该都是有序的。我们应该可以方便地比较它们之间的大小。 字段keys的值的元素类型不应该是一个具体的类型。我们应该可以在运行时再确定它的元素类型。 我们应该可以方便地对字段keys的值进行添加元素值、删除元素值以及获取元素值等操作，就像对待一个普通的切片值那样。 字段keys的值中的元素值应该可以被依照固定的顺序获取。 字段keys的值中的元素值应该能够被自动地排序。 由于字段keys的值中的元素值总是已排序的，所以我们应该能够确定某一个元素值的具体位置。 既然我们可以在运行时决定字段keys的值的元素类型，那么也应该可以在运行时获知这个元素类型。 我们应该可以在运行时获取到被用于比较keys的值中的不同元素值的大小的具体方法。 根据上面这些需求，我们有了这样一个接口类型声明： type Keys interface { sort.Interface Add(k interface{}) bool Remove(k interface{}) bool Clear() Get(index int) interface{} GetAll() []interface{} Search(k interface{}) (index int, contains bool) ElemType() reflect.Type CompareFunc() func(interface{}, interface{}) int8 } 在Keys接口类型中嵌入sort.Interface接口类型，就意味着Keys类型的值一定是可排序的。Add、Remove、Clear和Get这4个方法使得我们可以对Keys的值进行添加、删除、清除和获取元素值的操作。GetAll方法让我们可以获取到一个与Keys类型值有着相同的元素值集合和元素迭代顺序的切片值。Search、ElemType和CompareFunc方法分别体现了需求列表中第6项、第7项和第8项所描述的功能。其中，ElemType方法返回一个reflect.Type类型的结果值。我们在之前提到过reflect代码包，但是并没有对它进行说明。实际上，reflect包中的程序实体为我们提供了Go语言运行时的反射机制。通过它们，我们可以编写出一些代码来动态的操纵任意类型的对象。比如，其中TypeOf函数用于获取一个interface{}类型的值的动态类型信息。在本小节，我们会展示它的用法。 细心的读者可能会发现，在Keys接口类型的声明中并没有体现出需求列表中的第1、2、5项所描述的功能。不用着急，我们会在Keys接口类型的实现类型中实现它们。既然Keys接口类型的值必是sort.Interface接口的一个实现，那么我们使用sort代码包中的程序实体应该不难实现元素自动排序的功能。因此，我们编码的重点就落在了实现第1项和第2项中的功能上。 为了能够动态地决定元素类型，我们不得不在这个Keys的实现类型中声明一个[]interface{}类型的字段，以作为存储被添加到Keys类型值中的元素值的底层数据结构： container []interface{} 由于Go语言本身并没有对自定义泛型的提供支持，所以只有这样我们才能够用这个字段的值存储某一个数据类型的元素值。但是，我们前面提到的那个问题又出现了——接口类型的值不具备有序性，不可能比较它们的大小。不过，也许把这个问题抛出去并让使用这个Keys的实现类型的编程人员来解决它是一个可行的方案。因为他们应该知道添加到Keys类型值中的元素值的实际类型并知道应该怎样比较它们。所以，我们还应该有这样的一个字段： compareFunc func(interface{}, interface{}) int8 这是一个函数类型的字段。就像我们刚才说的，Keys的实现的使用者应该知道需要对作为该函数参数的那两个元素值进行怎样的类型转换以及怎样比较它们。这个函数返回一个int8类型的结果值。我们在这里做出如下规定。 当第一个参数值小于第二个参数值时，结果值应该小于0。 当第一个参数值大于第二个参数值时，结果值应该大于0。 当第一个参数值等于第二个参数值时，结果值应该等于0。 现在，通过把比较两个元素值大小的问题抛给使用者，我们既解决了需要动态确定元素类型的问题，又明确了比较两个元素值大小的解决方式。不过还有一个问题，由于container字段是[]interface{}类型的，所以我们常常不能够很方便地在运行时获取到它的实际元素类型（比如在它的值中还没有任何元素值的时候）。因此，我们还需要一个明确container字段的实际元素类型的字段。这个字段的值所代表的类型也应该是当前的Keys类型值的实际元素类型。 综上所述，这个Keys接口类型的实现类型的声明应该是这样的： type myKeys struct { container []interface{} compareFunc func(interface{}, interface{}) int8 elemType reflect.Type } 其中compareFunc和elemType字段的值应该是相对应的。比如，如果我们想使用一个*myKeys类型的值来存储int64类型的元素值，那么我就应该这样来初始化它： int64Keys := &myKeys{ container: make([]interface{}, 0), compareFunc: func(e1 interface{}, e2 interface{}) int8 { k1 := e1.(int64) k2 := e2.(int64) if k1 < k2 { return -1 } else if k1 > k2 { return 1 } else { return 0 } }, elemType: reflect.TypeOf(int64(1))} 注意，compareFunc字段的值中的那两个类型断言表达式的目标类型一定要与elemType字段的值所代表的类型保持一致。在这里，elemType字段的值所代表的类型其实就是调用reflect.TypeOf函数时传入的那个参数值的类型，即int64。这与前面在e1和e2上应用的类型断言表达式中的类型字面量是相对应的。只有存在这样的对应关系才能够保证在对变量int64Keys的使用过程中不会出现问题。我们会在编写myKeys类型的方法的过程中逐渐体现出如此设计的真正含义。 我们已经在前面的内容中多次讲过怎样实现sort.Interface接口类型中的那几个方法。不过，在这里，由于元素值之间的比较方法是由int64Keys的值的创建者确定的，所以其中的Less方法的实现会稍有不同。这些被用于实现sort.Interface接口类型的方法的声明如下： func (keys *myKeys) Len() int { return len(keys.container) } func (keys *myKeys) Less(i, j int) bool { return keys.compareFunc(keys.container[i], keys.container[j]) == -1 } func (keys *myKeys) Swap(i, j int) { keys.container[i], keys.container[j] = keys.container[j], keys.container[i] } 在Less方法中，我们把比较两个元素值的操作全权交给了compareFunc字段所代表的那个函数（以下简称compareFunc函数）。如果当前值是按照我们上面所说的正确的方式来初始化的话，那么这种比较方式应该总是有效的。另外，请注意，这3个方法的接收者类型都是*myKeys，所以实现sort.Interface接口类型的类型是*myKeys而不是myKeys。 现在我们来看Add方法怎样实现。在真正向字段container的值添加元素值之前，我们应该先判断这个元素值的类型是否符合要求。这需要使用到字段elemType的值，因为它代表了可接受的元素值的类型。由于我们在很多地方都会用到这种判断，所以我们应该把实现这一功能的代码独立为一个方法，像这样： func (keys *myKeys) isAcceptableElem(k interface{}) bool { if k == nil { return false } if reflect.TypeOf(k) != keys.elemType { return false } return true } 因为Add方法的参数的类型是interface{}类型的，所以isAcceptableElem方法的参数类型也应该是interface{}的。我们先使用reflect.TypeOf函数确定参数k的实际类型，再让它与当前值的elemType字段的值进行比较。由于reflect.Type是一个接口类型，所以我们使用比较操作符!=来判定它们的相等性是合法的。 在Add方法中，我们首先使用isAcceptableElem方法来判定元素值的类型是否可被接收。如果结果是否定的，那么我们就直接返回false。如果结果是肯定的，那么我们就向container字段的值添加这个元素值。在添加之后，我们应该对container的值中的元素值进行一次排序。这需要用到sort代码包中的排序函数sort.Sort。sort.Sort函数的声明是这样的： func Sort(data Interface) { // 省略若干条语句 } 函数sort.Sort的签名中的参数类型Interface其实就是接口类型sort.Interface。由于这两个程序实体处在同一个代码包中，所以在该参数类型的名称中并不用加入所属代码包名称和“.”（也就是限定前缀）。 值得一提的是，sort.Sort函数使用的排序算法是一种由三向切分的快速排序算法、堆排序算法和插入排序算法组成的混合算法。虽然快速排序是最快的通用排序算法，但在元素值很少的情况下它比插入排序要慢一些。而堆排序的空间复杂度是常数级别的，且它的时间复杂度在大多数情况下只略逊于其他两种排序算法。所以在快速排序中的递归达到一定深度的时候，切换至堆排序来节约空间是值得的。 这样的算法组合使得sort.Sort函数的时间复杂度在最坏的情况下是O(N*logN)的，并且能够有效地控制对空间的使用。但是，请注意，它并不提供稳定性的保证。稳定性是指在排序过程中能够保留数组（这里是切片值）中重复元素的相对位置。如果我们对稳定性没有特殊要求，那么选用sort.Sort函数提供的排序算法往往是最佳选择。 我们在这里选择使用sort.Sort函数对Add方法的接收者值（实际上是字段container的值）中的元素值进行排序是在算法特性和代码量之间进行权衡的结果。如果我们在使用过程中发现它的某些方面（时间复杂度、空间复杂度、稳定性等）并没有满足要求，也可以使用其他排序算法（组合）来替换对sort.Sort函数。 另一方面，由于*myKeys类型是sort.Interface接口类型的一个实现类型，所以我们可以直接使用Add方法的接收者值来作为sort.Sort的参数值。 按照上面的描述和分析，我们编写出了Add方法的声明： func (keys *myKeys) Add(k interface{}) bool { ok := keys.isAcceptableElem(k) if !ok { return false } keys.container = append(keys.container, k) sort.Sort(keys) return true } 正是有了isAcceptableElem方法的保证，我们才能够放心大胆地使用sort.Sort函数对当前值进行排序。sort.Sort函数会通过对keys的值的Len、Less和Swap方法的调用来完成排序。而在Less方法中，我们是通过那个compareFunc函数对相邻的元素值进行比较的。 这样一来，我们就真正地把elemType和compareFunc函数间接地关联了起来。换句话说，如果一个值能够通过isAcceptableElem方法的检查并被添加到container的值当中，那么这个元素值就肯定能够在compareFunc函数中被正确地比较。因此，我们在初始化myKeys类型值的时候，就必须保证这两个字段的值在类型设定方面的一致性。否则，在我们比较两个元素值的过程中就会引发运行时恐慌。 我们在从container中删除一个指定元素值之前先要找到它所处的位置。所以，我们在实现Remove方法之前先来看看Search方法应该怎样编写。在Search方法中，我们要搜索参数k代表的值在container中对应的索引值。由于k的类型是interface{}的，所以我们同样需要先使用isAcceptableElem方法对它进行判定。如果结果是否定的，我们就在把该方法的结果声明中的contains赋值为false之后直接返回。如果结果是肯定的，那么我就需要在container中搜索该元素值。我们可以通过调用sort.Search函数来实现搜索元素值的核心逻辑。sort.Search函数的声明如下： func Search(n int, f func(int) bool) int { // 省略若干条语句 } 由于sort.Search函数使用二分查找算法在切片值中搜索指定的元素值。这种搜索算法有着稳定的O(logN)的时间复杂度，但它要求被搜索的数组（这里是切片值）必须是有序的。因此，我们必须确保container字段的值中的元素值是已被排过序的。幸好我们在添加元素值的时候保证了这一点。 从上面的声明可知，sort.Search函数有两个参数。第一个参数接受的应该是欲排序的切片值的长度，而第二个参数接受的是一个函数值。这个函数值的含义是：对于一个给定的索引值，判定与之对应的元素值是否等于欲查找的元素值或者应该排在欲查找的元素值的右边。由此，参数f的值应该是这样的： func(i int) bool { return keys.compareFunc(keys.container[i], k) >= 0 } 与Less方法相同，我们在这里也是通过compareFunc函数对两个元素值进行比较的。 这个参数f的值到底意味着什么呢？假设我们有这样一个切片值： []int{1, 3, 5, 7, 9, 11, 13, 15} 且要查找的元素值是7。依据二分查找算法，sort.Search函数内部会在第三次折半的时候使用7的索引值3作为函数f的参数值。这时，函数f的结果值应该是true。同时，由于已经没有可以被折半的目标子序列了，所以sort.Search函数的执行会结束并返回7的索引值3作为它的结果值。显然，这个结果值对应的元素值就是我们要查找的。 另一种情况，我们要查找的元素值根本就不在这个切片值里，比如是6或8。这时，sort.Search函数的执行也会在f(3)被求值之后结束，且它的结果值会是4或3。但是，这两个结果值对应的元素值都不是我们要查找的。 总之，sort.Search函数的结果值总会在[0, n]的范围内，但结果值并不一定就是欲查找的元素值所对应的索引值。因此，我们还需要在得到调用sort.Search函数的结果值之后再进行一次判断。代码如下： if index < keys.Len() && keys.container[index] == k { contains = true } 其中index代表了sort.Search函数的结果值。我们需要先检查结果值是否在有效的索引范围之内，然后还要判断它所对应的元素值是否就是我们要查找的。 经过前面这一系列的分析，相信读者已经能够自己实现*myKeys类型的Search函数了。现在就把它编写出来吧。 等这个函数被实现之后，我们再来看Remove函数。首先，我们需要调用*myKeys类型的Search函数，以获取欲删除的元素值对应的索引值和它是否被包含在container中的判断结果。如果第二个结果值是false，那么就直接忽略剩余的操作并直接返回false，否则就从container中删除掉这个元素值。从切片值中删除一个元素值有很多种方式，比如使用for语句、copy函数或append函数，等等。我们在这里选择用append函数来实现，因为它可以在不增加时间复杂度和空间复杂度的情况下使用更少的代码来完成功能，且不降低可读性。下面这行代码实现了删除一个元素值的功能： keys.container = append(keys.container[0:index], keys.container[index+1:]...) 这行代码充分地使用了切片表达式和append函数。首先，我们使用切片表达式 keys.container[0:index] 和 keys.container[index+1:] 分别把container字段的值中的、在预删除元素值之前和之后的子元素序列提取出来。然后，我们再把这两个元素子序列拼接起来。还记得吗？append是一个可变参函数。所以，我们可以在第二个参数值之后添加“...”以表示把第二个参数值中的每个元素值都作为传给append函数的独立参数。这样，我们就把第二个子序列中的所有元素值逐个追加到了第一个子序列的尾部。最后，我们把拼接后的元素序列赋值给了container字段。 根据上面的描述，请读者自行编写出Remove函数。 通过在上一小节中对HashSet类型的实现，我们已经了解了Clear方法的编写手法。其声明如下： func (keys *myKeys) Clear() { keys.container = make([]interface{}, 0) } 又由于container字段本身就是切片类型的，所以Get方法也是相当好实现的。它的声明如下： func (keys *myKeys) Get(index int) interface{} { if index >= keys.Len() { return nil } return keys.container[index] } 方法GetAll的编写方式与*HashSet类型的Elements方法基本一致。唯一要注意的地方就是切片值的第一个迭代变量（左边的）代表了元素值的索引值，而第二个迭代变量（右边的）才代表了元素值本身。GetAll方法的声明如下： func (keys *myKeys) GetAll() []interface{} { initialLen := len(keys.container) snapshot := make([]interface{}, initialLen) actualLen := 0 for _, key := range keys.container { if actualLen < initialLen { snapshot[actualLen] = key } else { snapshot = append(snapshot, key) } actualLen++ } if actualLen < initialLen { snapshot = snapshot[:actualLen] } return snapshot } 至于ElemType和CompareFunc方法的实现就更不用多说了，我们直接把字段elemType和compareFunc字段的值分别作为它们的结果值就可以了： func (keys *myKeys) ElemType() reflect.Type { return keys.elemType } func (keys *myKeys) CompareFunc() CompareFunction { return keys.compareFunc } 作为一个可选的方法，String方法被用于生成可读性更好的接收者值的字符串表示形式。读者可以仿照*HashSet类型的String方法完成这一方法的编写。 至此，我们已经完成了myKeys类型以及相关方法的编写。不过按照Go语言的惯例，我们还应该编写一个用于初始化*myKeys类型值的函数。由于当前只有一个Keys接口类型的实现，所以我们就把这个函数定名为NewKeys，并把它的结果的类型设定为Keys。下面就是这个函数的声明： func NewKeys( compareFunc func(interface{}, interface{}) int8, elemType reflect.Type) Keys { return &myKeys{ container: make([]interface{}, 0), compareFunc: compareFunc, elemType: elemType, } } 可以看到，在NewKeys函数的参数声明列表中没有与container字段相对应的参数声明。原因是container字段的值总应该是一个长度为0的[]interface{}类型值。因此它不必由NewKeys函数的调用方提供。另外，NewKeys函数的compareFunc参数和elemType参数之间的关系，也应该满足我们在讲怎样初始化myKeys类型值的时候所提及的约束条件。最后，由于只有*myKeys类型的方法集合中才包含了Keys接口类型中声明的所有方法，所以在NewKeys函数中返回的是一个*myKeys类型值，而不是一个myKeys类型值。 好了，我们已经编写完成了OrderedMap类型所需要用到的最核心的数据类型Keys和myKeys。并且，在这个过程中，我们不仅对Go语言的很多基础知识进行了复习，还了解到了一些与元素排序和运行时反射有关的知识。下面，我们再回过头来看OrderedMap类型。 由于有了Keys接口类型，OrderedMap类型的声明被修改为： type myOrderedMap struct { keys Keys elemType reflect.Type m map[interface{}]interface{} } 是的，我们更改了该类型的名称，这是因为我们要声明一个接口类型来描述有序字典类型所提供的功能。OrderedMap更适合作为这个接口类型的名称。OrderedMap接口类型的声明如下： type OrderedMap interface { // 获取给定键值对应的元素值。若没有对应元素值则返回nil。 Get(key interface{}) interface{} // 添加键值对，并返回与给定键值对应的旧的元素值。若没有旧元素值则返回(nil, true)。 Put(key interface{}, elem interface{}) (interface{}, bool) // 删除与给定键值对应的键值对，并返回旧的元素值。若没有旧元素值则返回nil。 Remove(key interface{}) interface{} // 清除所有的键值对 Clear() // 获取键值对的数量 Len() int // 判断是否包含给定的键值 Contains(key interface{}) bool // 获取第一个键值。若无任何键值对则返回nil。 FirstKey() interface{} // 获取最后一个键值。若无任何键值对则返回nil。 LastKey() interface{} // 获取由小于键值toKey的键值所对应的键值对组成的OrderedMap类型值。 HeadMap(toKey interface{}) OrderedMap // 获取由小于键值toKey且大于等于键值fromKey的键值所对应的键值对组成的OrderedMap类型值。 SubMap(fromKey interface{}, toKey interface{}) OrderedMap // 获取由大于等于键值fromKey的键值所对应的键值对组成的OrderedMap类型值。 TailMap(fromKey interface{}) OrderedMap // 获取已排序的键值所组成的切片值 Keys() []interface{} // 获取已排序的元素值所组成的切片值 Elems() []interface{} // 获取已排序的键值对所组成的字典值 ToMap() map[interface{}]interface{} // 获取键的类型 KeyType() reflect.Type // 获取元素的类型 ElemType() reflect.Type } 我们要使*myOrderedMap类型成为OrderedMap接口类型的实现类型。虽然OrderedMap接口类型中的方法声明很多，但是有了之前编写HashSet类型和myKeys类型的经验，我们实现myOrderedMap类型的这些方法应该难度不大。读者能试着把这些方法的完整声明编写出来吗？请记得再编写一个NewOrderedMap函数，并把初始化好的*myOrderedMap类型值作为结果值返回。 别担心，完整的myOrderedMap类型以及相关方法的声明连同本小节所提及的所有代码都被放到了goc2p项目的basic/omap代码包中。在必要时读者可以把它们作为参考。但是，千万不要只动眼不动手。 另外，有些读者可能会认为，这样实现出来的有序字典类型的时间复杂度和空间复杂度都比较高。当然，我们也可以使用基于B树（及其衍生数据结构）或跳跃表来实现有序字典类型。在通过这两个小节的复习和训练之后，读者应该在Go语言基础语法的运用上已经基本没有什么障碍了。那么读者是否可以试着使用Go语言来实现更高效的有序字典类型呢？