在go语言种使用泛型实现一个有序map示例

Go  /  管理员 发布于 1年前   252

在Go中，泛型的实现依赖于接口和反射。由于Go不是一种泛型编程语言，所以它没有内置的泛型机制。

但是，我们可以通过定义一个泛型接口和使用反射来实现类似泛型的行为。

以下是一个简单的有序Map实现的例子，

它使用了接口和反射来实现泛型特性：

package main
 
import (
    "fmt"
    "reflect"
    "sort"
)
 
// KeyType 定义了可以作为键的类型
type KeyType interface{}
 
// Item 是map中的一个键值对
type Item struct {
    Key   KeyType
    Value interface{}
}
 
// By 用于排序的关键字
type By []Item
 
func (a By) Len() int           { return len(a) }
func (a By) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a By) Less(i, j int) bool { return a[i].Key.(int) < a[j].Key.(int) }
 
// OrderedMap 是一个有序的map结构
type OrderedMap struct {
    items []Item
}
 
// Set 添加或更新键值对
func (m *OrderedMap) Set(key KeyType, value interface{}) {
    for i, item := range m.items {
        if eq(item.Key, key) {
            m.items[i].Value = value
            return
        }
    }
    m.items = append(m.items, Item{key, value})
}
 
// Get 获取键对应的值
func (m *OrderedMap) Get(key KeyType) interface{} {
    for _, item := range m.items {
        if eq(item.Key, key) {
            return item.Value
        }
    }
    return nil
}
 
// eq 检查两个值是否相等
func eq(a, b KeyType) bool {
    return reflect.DeepEqual(a, b)
}
 
func main() {
    // 创建一个OrderedMap实例
    om := &OrderedMap{}
 
    // 添加键值对
    om.Set(1, "one")
    om.Set(2, "two")
    om.Set(3, "three")
 
    // 根据键获取值
    fmt.Println(om.Get(2)) // 输出: two
 
    // 对键进行排序
    sort.Stable(By(om.items))
 
    // 打印排序后的键值对
    for _, item := range om.items {
        fmt.Printf("Key: %v, Value: %v\n", item.Key, item.Value)
    }
    // 输出:
    // Key: 1, Value: one
    // Key: 2, Value: two
    // Key: 3, Value: three
}

ps:

这个例子中，OrderedMap 结构体包含一个 Item 类型的切片，代表有序的键值对集合。

Set 方法用于添加或更新键值对，Get 方法用于获取特定键对应的值。

eq 函数用于比较两个键是否相等，By 类型实现了 sort.Interface 接口，允许我们根据键对集合进行排序。

这个实现虽然功能完善，但是因为使用了反射和interface{}，可能会牺牲一定的性能。

第二种：基于泛型实现一个有序map示例，有兴趣可自行测试

package main
import (
    "fmt"
    "sort"
    "sync"
)
type OrderedMap[K comparable, V any] struct {
    keys   []K
    values map[K]V
    mutex  sync.RWMutex
    less   func(K, K) bool
}
func NewOrderedMap[K comparable, V any](less func(K, K) bool) *OrderedMap[K, V] {
    return &OrderedMap[K, V]{
        keys:   make([]K, 0),
        values: make(map[K]V),
        less:   less,
    }
}
func (om *OrderedMap[K, V]) Set(key K, value V) {
    om.mutex.Lock()
    defer om.mutex.Unlock()
    if _, exists := om.values[key]; !exists {
        om.keys = append(om.keys, key)
        sort.Slice(om.keys, func(i, j int) bool {
            return om.less(om.keys[i], om.keys[j])
        })
    }
    om.values[key] = value
}
func (om *OrderedMap[K, V]) Get(key K) (V, bool) {
    om.mutex.RLock()
    defer om.mutex.RUnlock()
    value, exists := om.values[key]
    return value, exists
}
func (om *OrderedMap[K, V]) Keys() []K {
    om.mutex.RLock()
    defer om.mutex.RUnlock()
    return om.keys
}
func (om *OrderedMap[K, V]) Range(f func(key K, value V) bool) {
    om.mutex.RLock()
    defer om.mutex.RUnlock()
    for _, key := range om.keys {
        value, exists := om.values[key]
        if !exists {
            continue
        }
        if !f(key, value) {
            break
        }
    }
}
func main() {
    om := NewOrderedMap[int, int](func(a, b int) bool {
        return a < b
    })
    var wg sync.WaitGroup
    wg.Add(2)
    go func() {
        defer wg.Done()
        om.Set(4, 2)
        om.Set(5, 1)
    }()
    go func() {
        defer wg.Done()
        om.Set(9, 3)
        om.Set(7, 4)
    }()
    wg.Wait()
    //fmt.Println("Keys in order:")
    //for _, key := range om.Keys() {
    //    value, _ := om.Get(key)
    //    fmt.Printf("%v: %v\n", key, value)
    //}
    fmt.Println("Keys in order:")
    om.Range(func(key int, value int) bool {
        fmt.Printf("%v: %v\n", key, value)
        return true
    })
}