🔖
Go版OrderedDictを実装した
諸事情でPythonのOrderedDictがGoにも欲しくなったので移植しました。パッと調べたところ既に先人が作ってくれていた(ordered_map)のですが、現代っ子としてはやはり interface
ではなく generics
を積極的に採用していきたっかたので車輪を差異発明しました。
更新
2022年10月26日
実装で述べた values
不要論をもとに修正し、 values
フィールドを廃止しました。
使用例
こんな感じで使用できます。
import (
"fmt"
omap "github.com/kasegao/go-orderedmap"
)
func main() {
om := omap.New[string, string]()
om.Set("h", "hoge")
om.Set("f", "fuga")
om.Set("p", "piyo")
if v, ok := om.Get("h"); ok {
fmt.Println(v) // print "hoge"
}
if e, ok := om.GetAt(1); ok {
fmt.Println(e.Key, e.Value) // print "f fuga"
}
om.DeleteAt(-1)
if _, ok := om.Get("p"); !ok {
fmt.Println("not found") // print "not found"
}
fmt.Println(om) // print "OrderedMap[h:hoge f:fuga]"
}
実装
下記のように双方向リストを使って実現しました。
type node[K comparable] struct {
key K
prev *node[K]
next *node[K]
}
type OrderedMap[K comparable, V any] struct {
root *node[K]
nodes map[K]*node[K]
values map[K]V
}
nodeにvalueを持たせれば values
を廃止できるのではないかとも考えたのですが、例えばGet()を次のようにした時に型Vがnilを取れないので怒られてしまいます。
func (om *OrderedMap[K, V]) Get(key K) (V, bool) {
if v, ok := om.nodes[key]; ok {
return v, true
}
return nil, false // <- ここで怒られる
}
これを回避するために、別途 values
という形で値を保持することにしました。
...ただ、この記事を執筆しながら再考してみると、下記のようにzero値を返すようにしてやれば解決できたなという事に気付きました。そのうち修正します。
⇒修正しました(2022年10月26日)
func (om *OrderedMap[K, V]) Get(key K) (value V, ok bool) {
if v, ok := om.values[key]; ok {
return v, true
}
return
}
換装した感想
Go言語初心者なのでお作法がよく分かっていないところがあり、強い人に手直ししてもらえると嬉しいです。
Discussion