🔖

Go版OrderedDictを実装した

2022/10/26に公開

諸事情で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言語初心者なのでお作法がよく分かっていないところがあり、強い人に手直ししてもらえると嬉しいです。

更新

2022年10月26日

使用例

実装

換装した感想

Discussion