Go Map有序遍历：理解限制与选择合适的有序数据结构

package main

import (
    "fmt"
    "sort"
)

// PairKeyValue 定义键值对结构体
type PairKeyValue[K comparable, V any] struct {
    Key   K
    Value V
}

// PairKeyValueSlice 定义可排序的键值对切片
type PairKeyValueSlice[K comparable, V any] struct {
    data []PairKeyValue[K, V]
    less func(a, b K) bool // 比较函数
}

// Len 实现 sort.Interface 接口
func (pks PairKeyValueSlice[K, V]) Len() int {
    return len(pks.data)
}

// Swap 实现 sort.Interface 接口
func (pks PairKeyValueSlice[K, V]) Swap(i, j int) {
    pks.data[i], pks.data[j] = pks.data[j], pks.data[i]
}

// Less 实现 sort.Interface 接口
func (pks PairKeyValueSlice[K, V]) Less(i, j int) bool {
    return pks.less(pks.data[i].Key, pks.data[j].Key)
}

// NewSortedPairKeyValueSlice 从map创建并排序键值对切片
func NewSortedPairKeyValueSlice[K comparable, V any](m map[K]V, less func(a, b K) bool) PairKeyValueSlice[K, V] {
    ps := make([]PairKeyValue[K, V], 0, len(m))
    for k, v := range m {
        ps = append(ps, PairKeyValue[K, V]{Key: k, Value: v})
    }
    sortedSlice := PairKeyValueSlice[K, V]{data: ps, less: less}
    sort.Sort(sortedSlice)
    return sortedSlice
}

// 假设的自定义Key类型
type MyKey struct {
    ID   int
    Name string
}

// 自定义Key的比较函数
func LessMyKey(a, b MyKey) bool {
    if a.ID != b.ID {
        return a.ID < b.ID
    }
    return a.Name < b.Name
}

func main() {
    // 示例使用
    myMap := map[MyKey]string{
        {ID: 2, Name: "Beta"}:  "Value B",
        {ID: 1, Name: "Alpha"}: "Value A",
        {ID: 3, Name: "Gamma"}: "Value C",
    }

    // 创建并排序切片
    sortedPairs := NewSortedPairKeyValueSlice(myMap, LessMyKey)

    // 遍历排序后的切片
    fmt.Println("Sorted iteration:")
    for _, kv := range sortedPairs.data {
        fmt.Printf("  Key: {%d, %s}, Value: %s\n", kv.Key.ID, kv.Key.Name, kv.Value)
    }
}

package main

import (
    "fmt"
    "sort"
    // "github.com/google/btree" // 假设引入B树库
)

// MyKey 自定义键类型
type MyKey struct {
    ID   int
    Name string
}

// Less 方法，用于比较MyKey类型，以满足B树或排序的需求
func (mk MyKey) Less(other MyKey) bool {
    if mk.ID != other.ID {
        return mk.ID < other.ID
    }
    return mk.Name < other.Name
}

// OrderedMap 定义一个有序映射接口
type OrderedMap[K comparable, V any] interface {
    Put(key K, value V)
    Get(key K) (V, bool)
    Delete(key K)
    Len() int
    // Ascend 允许按升序遍历，可以传入一个回调函数处理每个键值对
    Ascend(iterator func(key K, value V) bool)
    // Descend 允许按降序遍历
    Descend(iterator func(key K, value V) bool)
    // AscendRange 允许在指定范围内按升序遍历
    AscendRange(greaterOrEqual, lessThan K, iterator func(key K, value V) bool)
    // ... 其他有序操作，如Min(), Max()
}

// SimpleSortedSliceMap 是一个基于排序切片的OrderedMap实现（仅用于演示概念，不推荐生产环境大规模使用）
type SimpleSortedSliceMap[K MyKey, V any] struct {
    data []PairKeyValue[K, V]
}

func NewSimpleSortedSliceMap[K MyKey, V any]() *SimpleSortedSliceMap[K, V] {
    return &SimpleSortedSliceMap[K, V]{}
}

func (m *SimpleSortedSliceMap[K, V]) Put(key K, value V) {
    // 在一个始终保持有序的切片中插入/更新，效率为O(N)
    // 实际实现会使用二分查找找到插入位置，然后插入
    for i, kv := range m.data {
        if kv.Key == key { // 键已存在，更新
            m.data[i].Value = value
            return
        }
    }
    // 键不存在，插入新元素并保持有序
    m.data = append(m.data, PairKeyValue[K, V]{Key: key, Value: value})
    sort.Slice(m.data, func(i, j int) bool {
        return m.data[i].Key.Less(m.data[j].Key)
    })
}

func (m *SimpleSortedSliceMap[K, V]) Get(key K) (V, bool) {
    // 实际实现会使用二分查找，效率O(log N)
    for _, kv := range m.data {
        if kv.Key == key {
            return kv.Value, true
        }
    }
    var zero V
    return zero, false
}

func (m *SimpleSortedSliceMap[K, V]) Delete(key K) {
    // 实际实现会使用二分查找，然后删除，效率O(N)
    for i, kv := range m.data {
        if kv.Key == key {
            m.data = append(m.data[:i], m.data[i+1:]...)
            return
        }
    }
}

func (m *SimpleSortedSliceMap[K, V]) Len() int {
    return len(m.data)
}

func (m *SimpleSortedSliceMap[K, V]) Ascend(iterator func(key K, value V) bool) {
    for _, kv := range m.data {
        if !iterator(kv.Key, kv.Value) {
            return
        }
    }
}

func (m *SimpleSortedSliceMap[K, V]) Descend(iterator func(key K, value V) bool) {
    for i := len(m.data) - 1; i >= 0; i-- {
        kv := m.data[i]
        if !iterator(kv.Key, kv.Value) {
            return
        }
    }
}

func (m *SimpleSortedSliceMap[K, V]) AscendRange(greaterOrEqual, lessThan K, iterator func(key K, value V) bool) {
    for _, kv := range m.data {
        // 假设MyKey有比较方法
        if kv.Key.Less(greaterOrEqual) {
            continue
        }
        if !kv.Key.Less(lessThan) { // kv.Key >= lessThan
            break
        }
        if !iterator(kv.Key, kv.Value) {
            return
        }
    }
}


func main() {
    // 使用自定义的SimpleSortedSliceMap演示
    fmt.Println("--- Using SimpleSortedSliceMap ---")
    osm := NewSimpleSortedSliceMap[MyKey, string]()
    osm.Put(MyKey{ID: 2, Name: "Beta"}, "Value B")
    osm.Put(MyKey{ID: 1, Name: "Alpha"}, "Value A")
    osm.Put(MyKey{ID: 3, Name: "Gamma"}, "Value C")
    osm.Put(MyKey{ID: 1, Name: "Alpha"}, "Updated Value A") // 更新

    fmt.Println("Ascending order:")
    osm.Ascend(func(key MyKey, value string) bool {
        fmt.Printf("  Key: {%d, %s}, Value: %s\n", key.ID, key.Name, value)
        return true // 继续遍历
    })

    fmt.Println("\nDescending order:")
    osm.Descend(func(key MyKey, value string) bool {
        fmt.Printf("  Key: {%d, %s}, Value: %s\n", key.ID, key.Name, value)
        return true
    })

    // 实际生产中，会使用如github.com/google/btree这样的库
    // var btreeMap *btree.BTree // 伪代码，实际使用需初始化并传入比较函数
    // btreeMap.ReplaceOrInsert(btree.Item(MyKey{ID: 1, Name: "Alpha"}))
    // btreeMap.Ascend(func(item btree.Item) bool {
    //     kv := item.(PairKeyValue[MyKey, string]) // 类型断言
    //     fmt.Printf("  Key: {%d, %s}, Value: %s\n", kv.Key.ID, kv.Key.Name, kv.Value)
    //     return true
    // })
}