How can I create a first-class map iterator in Go?

Question

I am writing a function that iterates over the entries in a map. I want to be able to deal cleanly with items which are added or deleted from the map while iterating, like for k, v := range myMap { //... does, but I am processing just one key/value pair per iteration so I can't use range. I want something like:

func processItem(i iterator) bool {
     k, v, ok := i.next()
     if(!ok) {
         return false
     }
     process(v)
     return true
}

var m = make(map[string]widget)
// ...
i := makeIterator(m)
for processItem(i) {
    // code which might add/remove item from m here
}

I know that range is using a 'hiter' struct and associated functions, as defined in src/runtime/hashmap.go, to perform iteration. Is there some way to gain access to this iterator as a reified (first-class) Go object?

Is there an alternative strategy for iterating over a map which would deal well with insertions/deletions but give a first-class iterator object?

Bonus question: is there an alternative strategy for iterating over a map which could also deal with the map and iterator being serialised to disk and then restored, with iteration continuing from where it left off? (Obviously the built-in range iterator does not have this capability!)

Pointer

I outlined the new idiomatic way to do this with Go 1.23 – Calcite

Answer 1

You can't :(

The only way to iterate over a map is by using for range and you can't get an iterator object out of that.

Sterrett

Looked at the go source for the range statement. It's a tough read, but from what I can tell, it might be possible to code another keyword from into the language. It wouldn't be an iterator per se, but given m map[string]interface{} you could do for k, v := range m from "hello" { }. Of course, for any type of key. Could do for slices too, ... from 42 { } to start from index 42. Of course you could do your own iteration on a slice, but range is kinda nice. – Subsequence

Nevermind that comment. I'll leave it up for possible discussion, but given the nature of maps, iterators for them just don't make sense on a fundamental level. At least not enough sense to add a keyword to the language. – Subsequence

Answer 2

You can use channels as iterators.

Your iterator would be a function returning a channel that communicates the current iteration value to whoever receives it:

func iterator(m map[string]widget) chan iteration {
    c := make(chan iteration)
    go func() {
        for k,v := range m {
            c <- iteration{k,v}
        }
        close(c)
    }()
    return c
}

This is of course not generic, you could make it generic using interface{} and/or reflection but that shouldn't be too hard if you actually need it. Closing the channel at the end of iteration will notify the end of iteration, demonstrated later.

The iteration type is just there so you can send key and value at the same time, it would look something like this:

type iteration struct {
    key string
    value widget
}

With this you can then do this (on play):

m := map[string]widget{"foo": widget{3}, "bar": widget{4}}
i := iterator(m)

iter, ok := <- i
fmt.Println(iter, ok)
iter, ok = <- i
fmt.Println(iter, ok)
iter, ok = <- i
fmt.Println(iter, ok)

which yields

{foo {3}} true
{bar {4}} true
{ {0}} false

Mozambique

I like this. It does not quite handle deletion correctly, though, and I'm slightly concerned that it could fall foul of the internal checks hashmap.go does to try to detect concurrent access to the map from different goroutines. – Pointer

Ah, yeah I forgot about the modification part, sorry. In that case you'd probably have to model the modification in the iterator and then it would look less nice than this. – Mozambique

Answer 3

A very simple approach is to obtain a list of all the keys in the map, and package the list and the map up in an iterator struct. When we want the next key, we take the next one from the list that hasn't been deleted from the map:

type iterator struct {
    m    map[string]widget
    keys []string
}

func newIterator(m map[string]widget) *iterator {
    it := iterator{m, make([]string, len(m))}
    i := 0
    for k, _ := range m {
        it.keys[i] = k
        i++
    }
    return &it
}

func (it *iterator) next() (string, widget, bool) {
    for len(it.keys) > 0 {
        k := it.keys[0]
        it.keys = it.keys[1:]
        if _, exists := it.m[k]; exists {
            return k, it.m[k], true
        }
    }
    return "", widget{0}, false
}

See running example on play.

Pointer

Im guessing this cannot actually use the for construct since thats tied to the golang language. Good stuff otherwise. I'd recommend people look at the other solutions that make this concurrency safe – Escapee

Answer 4

Go 1.23

Use maps.Keys or maps.Values which return an iterator for any map. You can then range over the iterator, without writing any custom code beside the loop body.

var m = make(map[string]widget)
for _, v := maps.Values(m) {
    // do something with v
}

This is part of the range-over-function feature which enables native iterators in Go.

Calcite

Answer 5

You can define your own map type. Also it will be good to solve concurrency problem:

type ConcurrentMap struct {
    sync.RWMutex
    items map[string]interface{}
}

type ConcurrentMapItem struct {
    Key   string
    Value interface{}
}

func (cm *ConcurrentMap) Iter() <-chan ConcurrentMapItem {
    c := make(chan ConcurrentMapItem)

    f := func() {
        cm.Lock()
        defer cm.Unlock()

        for k, v := range cm.items {
            c <- ConcurrentMapItem{k, v}
        }
        close(c)
    }
    go f()

    return c
}

Dekker

The sync mutex will prevent panics due to concurrent map access, but it will (if used correctly) also prevent modifications to the map while iterating over it. I need to be able to modify the map while iterating. This works great (provided iteration and modification are done in the same goroutine) with an ordinary map. – Pointer