Go语言中实现有序Map迭代的策略与实践

package main

import (
    "fmt"
    "sort"
)

// MyKey 是一个示例键类型，假设它实现了可比较性
type MyKey struct {
    ID   int
    Name string
}

// LessKey 是一个自定义的比较函数，用于对MyKey进行排序
func LessKey(a, b MyKey) bool {
    if a.ID != b.ID {
        return a.ID < b.ID
    }
    return a.Name < b.Name
}

// MyValue 是一个示例值类型
type MyValue struct {
    Data string
}

// PairKeyValue 结构体用于存储键值对
type PairKeyValue struct {
    Key   MyKey
    Value MyValue
}

// PairKeyValueSlice 实现了 sort.Interface 接口
type PairKeyValueSlice []PairKeyValue

func (ps PairKeyValueSlice) Len() int {
    return len(ps)
}

func (ps PairKeyValueSlice) Swap(i, j int) {
    ps[i], ps[j] = ps[j], ps[i]
}

func (ps PairKeyValueSlice) Less(i, j int) bool {
    return LessKey(ps[i].Key, ps[j].Key)
}

// NewPairKeyValueSlice 将map转换为排序后的PairKeyValueSlice
func NewPairKeyValueSlice(m map[MyKey]MyValue) PairKeyValueSlice {
    ps := make(PairKeyValueSlice, 0, len(m))
    for k, v := range m {
        ps = append(ps, PairKeyValue{Key: k, Value: v})
    }
    sort.Sort(ps)
    return ps
}

func main() {
    // 示例map
    myMap := map[MyKey]MyValue{
        {ID: 2, Name: "Beta"}: {Data: "ValueB"},
        {ID: 1, Name: "Alpha"}: {Data: "ValueA"},
        {ID: 3, Name: "Gamma"}: {Data: "ValueC"},
        {ID: 1, Name: "Delta"}: {Data: "ValueD"}, // 注意，ID相同，但Name不同
    }

    // 有序迭代
    fmt.Println("有序迭代结果:")
    for _, kv := range NewPairKeyValueSlice(myMap) {
        fmt.Printf("Key: %+v, Value: %+v\n", kv.Key, kv.Value)
    }
}

go get github.com/emirpasic/gods/trees/redblacktree

package main

import (
    "fmt"
    "github.com/emirpasic/gods/trees/redblacktree"
)

// MyKey 是一个示例键类型，假设它实现了可比较性
type MyKey struct {
    ID   int
    Name string
}

// CustomKeyComparator 是一个自定义的比较函数，用于MyKey
// 必须返回 -1 (a < b), 0 (a == b), 或 1 (a > b)
func CustomKeyComparator(a, b interface{}) int {
    keyA := a.(MyKey)
    keyB := b.(MyKey)

    if keyA.ID < keyB.ID {
        return -1
    }
    if keyA.ID > keyB.ID {
        return 1
    }
    // 如果ID相同，则按Name比较
    if keyA.Name < keyB.Name {
        return -1
    }
    if keyA.Name > keyB.Name {
        return 1
    }
    return 0 // 两键相等
}

// MyValue 是一个示例值类型
type MyValue struct {
    Data string
}

func main() {
    // 创建一个红黑树，并指定自定义的键比较器
    tree := redblacktree.NewWith(CustomKeyComparator)

    // 插入键值对
    tree.Put(MyKey{ID: 2, Name: "Beta"}, MyValue{Data: "ValueB"})
    tree.Put(MyKey{ID: 1, Name: "Alpha"}, MyValue{Data: "ValueA"})
    tree.Put(MyKey{ID: 3, Name: "Gamma"}, MyValue{Data: "ValueC"})
    tree.Put(MyKey{ID: 1, Name: "Delta"}, MyValue{Data: "ValueD"}) // 注意：如果键完全相同，会覆盖旧值

    // 有序迭代
    fmt.Println("使用红黑树进行有序迭代结果:")
    it := tree.Iterator()
    for it.Next() {
        key := it.Key().(MyKey)
        value := it.Value().(MyValue)
        fmt.Printf("Key: %+v, Value: %+v\n", key, value)
    }

    // 也可以反向迭代
    fmt.Println("\n反向迭代结果:")
    it = tree.Iterator()
    for it.Prev() { // 从最后一个元素开始
        key := it.Key().(MyKey)
        value := it.Value().(MyValue)
        fmt.Printf("Key: %+v, Value: %+v\n", key, value)
    }
}

使用红黑树进行有序迭代结果:
Key: {ID:1 Name:Alpha}, Value: {Data:ValueA}
Key: {ID:1 Name:Delta}, Value: {Data:ValueD}
Key: {ID:2 Name:Beta}, Value: {Data:ValueB}
Key: {ID:3 Name:Gamma}, Value: {Data:ValueC}

反向迭代结果:
Key: {ID:3 Name:Gamma}, Value: {Data:ValueC}
Key: {ID:2 Name:Beta}, Value: {Data:ValueB}
Key: {ID:1 Name:Delta}, Value: {Data:ValueD}
Key: {ID:1 Name:Alpha}, Value: {Data:ValueA}