Golang 實作一個簡單的有順序map simple ordered map implementation

Golang的map不保證順序，所以利用struct實作一個簡單有順序的map。

已經有很多神人有更好的實作，本篇僅是練習而已。

實作

有順序的map是指內部元素會依照插入順序來排列，利用一個有順序的slice欄位來紀錄key的新增順序。

下面先定義一個Map介面及常用的操作方法。定義struct型別OrderedMap實作Map及有順序的map操作方法邏輯。

orderedmap.go

package orderedmap

import "fmt"

type Map interface {
    // put element
    Put(key, value interface{})
    // get element
    Get(key interface{}) interface{}
    // get keys
    Keys() []interface{}
    // get values
    Values() []interface{}
    // remove element
    Remove(key interface{})
    // iterate elements
    Iter(func(k, v interface{}))
}

type OrderedMap struct {
    m    map[interface{}]interface{}
    keys []interface{}
}

func NewOrderedMap() OrderedMap {
    return OrderedMap{
        m:    make(map[interface{}]interface{}),
        keys: make([]interface{}, 0),
    }
}

func (om OrderedMap) String() string {
    return fmt.Sprintf("%s", om.m)
}

func (om *OrderedMap) Put(key, value interface{}) {
    om.m[key] = value

    for _, k := range om.keys {
        if k == key {
            return
        }
    }

    om.keys = append(om.keys, key)
}

func (om *OrderedMap) Get(key interface{}) interface{} {
    return om.m[key]
}

func (om *OrderedMap) Keys() []interface{} {
    return om.keys
}

func (om *OrderedMap) Values() []interface{} {
    s := make([]interface{}, 0)
    for _, key := range om.keys {
        s = append(s, om.m[key])
    }
    return s
}

func (om *OrderedMap) Remove(key interface{}) {
    m := NewOrderedMap()
    for _, k := range om.keys {
        if k != key {
            v := om.m[k]
            m.Put(k, v)
        }
    }
    om.m = m.m
    om.keys = m.keys
}

func (om *OrderedMap) Iter(do func(k, v interface{})) {
    for k, v := range om.m {
        do(k, v)
    }
}

測試

引用上面的orderedmap。

main.go

package main

import (
    "fmt"

    "abc.com/demo/orderedmap"
)

func main() {
    om := orderedmap.NewOrderedMap()

    om.Put("1", "john")
    om.Put("2", "mary")
    om.Put("2", "tony")

    fmt.Println(om) // map[1:john 2:tony]

    om.Iter(func(k, v interface{}) {
        fmt.Printf("key=%s, value=%s\n", k, v)
    })

    fmt.Println(om.Keys()...)   // 1 2
    fmt.Println(om.Values()...) // john tony

    om.Remove("2")

    fmt.Println(om.Keys()...)   // 1
    fmt.Println(om.Values()...) // john

}

測試輸出結果。

map[1:john 2:tony]
key=1, value=john
key=2, value=tony
1 2
john tony
1
john

或是直接用slice紀錄放入順序，參考「Golang 依放入順序遍歷map的值」。

• Go maps in action
• Insertion Order Iteration of Maps in Go