How to Maintain Insertion Order When Iterating Through a Go Map?

Looping Through a Map in Insertion Order

Maps in Go do not guarantee iteration order, which can be frustrating when you want to retrieve items in the order they were inserted. While some workarounds exist, they often involve using separate slices or creating data duplication, which can lead to complexity and potential bugs.

Solution with a Key Slice

One viable solution is to maintain a slice of keys in insertion order. When adding a new pair to the map, first check if the key exists in the slice. If not, append the key to the slice. When iterating, simply use the slice to retrieve the keys in order and access the corresponding values from the map. This approach has minimal overhead since the slice only stores keys.

Example:

type Key int
type Value int

type OrderedMap struct {
    m    map[Key]Value
    keys []Key
}

func NewOrderedMap() *OrderedMap {
    return &OrderedMap{m: make(map[Key]Value)}
}

func (om *OrderedMap) Set(k Key, v Value) {
    if _, ok := om.m[k]; !ok {
        om.keys = append(om.keys, k)
    }
    om.m[k] = v
}

func (om *OrderedMap) Range() {
    for _, k := range om.keys {
        fmt.Println(om.m[k])
    }
}

Solution with a Value Wrapper Linked List

Alternatively, you can wrap values in a linked list structure. Each value wrapper contains the actual value and a pointer to the next key in the list. When adding a new pair, set the next pointer of the previous value wrapper to point to the new key. When iterating, start from the first key and follow the next pointers to retrieve the values in order.

Example:

type Key int
type Value int

type ValueWrapper struct {
    v    Value
    next *Key
}

type OrderedMap struct {
    m           map[Key]ValueWrapper
    first, last *Key
}

func NewOrderedMap() *OrderedMap {
    return &OrderedMap{m: make(map[Key]ValueWrapper)}
}

func (om *OrderedMap) Set(k Key, v Value) {
    if _, ok := om.m[k]; !ok && om.last != nil {
        pw2 := om.m[*om.last]
        om.m[*om.last] = ValueWrapper{pw2.v, &k}
    }
    pw := ValueWrapper{v: v}
    om.m[k] = pw
    if om.first == nil {
        om.first = &k
    }
    om.last = &k
}

func (om *OrderedMap) Range() {
    for k := om.first; k != nil; {
        pw := om.m[*k]
        fmt.Println(pw.v)
        k = pw.next
    }
}

Comparison

The key slice approach is simpler but less efficient for element removal as it requires linear search in the slice. The value wrapper linked list approach allows for fast element removal, making it more suitable for cases where frequent deletions are expected.

Ultimately, the best choice depends on the specific requirements of your application.

The above is the detailed content of How to Maintain Insertion Order When Iterating Through a Go Map?. For more information, please follow other related articles on the PHP Chinese website!