基于泛型实现一个有序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
    })
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
goStruct
讨论数量: 2

我直接额外弄出来一个排序的 Slice,简单求解

2周前 评论

我认为可能有以下两个小问题

Set:只增加一个key就导致整个keys重新排序,这是没有必要的,直接遍历会更快
Keys:返回keys本体是危险的,Slice是指针,这将导致外部程序修改keys的可能性

1周前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!