Sort Go map values by keys

Question

When iterating through the returned map in the code, returned by the topic function, the keys are not appearing in order.

How can I get the keys to be in order / sort the map so that the keys are in order and the values correspond?

Here is the code.

Answer 1

The Go blog: Go maps in action has an excellent explanation.

When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next. Since Go 1 the runtime randomizes map iteration order, as programmers relied on the stable iteration order of the previous implementation. If you require a stable iteration order you must maintain a separate data structure that specifies that order.

Here's my modified version of example code: http://play.golang.org/p/dvqcGPYy3-

package main

import (
    "fmt"
    "sort"
)

func main() {
    // To create a map as input
    m := make(map[int]string)
    m[1] = "a"
    m[2] = "c"
    m[0] = "b"

    // To store the keys in slice in sorted order
    var keys []int
    for k := range m {
        keys = append(keys, k)
    }
    sort.Ints(keys)

    // To perform the opertion you want
    for _, k := range keys {
        fmt.Println("Key:", k, "Value:", m[k])
    }
}

Output:

Key: 0 Value: b
Key: 1 Value: a
Key: 2 Value: c

Answer 2

While most of these answers are correct, I often find a C-style for-loop to be the most simple solution (though only if your keys are a series of ints):

m := make(map[int]string)
m[1] = "a"
m[2] = "c"
m[0] = "b"

for i := 0; i < len(m); i++ {
    fmt.Println("Key:", i, "Value:", m[i])
}

Output:

Key: 0 Value: b
Key: 1 Value: a
Key: 2 Value: c

Answer 3

According to the Go spec, the order of iteration over a map is undefined, and may vary between runs of the program. In practice, not only is it undefined, it's actually intentionally randomized. This is because it used to be predictable, and the Go language developers didn't want people relying on unspecified behavior, so they intentionally randomized it so that relying on this behavior was impossible.

What you'll have to do, then, is pull the keys into a slice, sort them, and then range over the slice like this:

var m map[keyType]valueType
keys := sliceOfKeys(m) // you'll have to implement this
for _, k := range keys {
    v := m[k]
    // k is the key and v is the value; do your computation here
}

Answer 4

If, like me, you find you want essentially the same sorting code in more than one place, or just want to keep the code complexity down, you can abstract away the sorting itself to a separate function, to which you pass the function that does the actual work you want (which would be different in each place, of course).

Given a map with key type K and value type V, represented as <K> and <V> below, the common sort function might look something like this:

/* Go apparently doesn't support/allow 'interface{}' as the value (or
/* key) of a map such that any arbitrary type can be substituted at
/* run time, so several of these nearly-identical functions might be
/* needed for different key/value type combinations. */
func sortedMap<K><T>(m map[<K>]<V>, f func(k <K>, v <V>)) {
    var keys []<K>
    for k, _ := range m {
        keys = append(keys, k)
    }
    sort.Strings(keys)  # or sort.Ints(keys), sort.Sort(...), etc., per <K>
    for _, k := range keys {
        v := m[k]
        f(k, v)
    }
}

Then call it with the input map and a function (taking k <K> v <V> as input arguments) that is called over the map elements in sorted-key order.

So, a version of the code in the answer posted by Mingu might look like:

package main

import (
    "fmt"
    "sort"
)

func sortedMapIntString(m map[int]string, f func(k int, v string)) {
    var keys []int
    for k, _ := range m {
        keys = append(keys, k)
    }
    sort.Ints(keys)
    for _, k := range keys {
        f(k, m[k])
    }
}

func main() {
    // Create a map for processing
    m := make(map[int]string)
    m[1] = "a"
    m[2] = "c"
    m[0] = "b"

    sortedMapIntString(m,
        func(k int, v string) { fmt.Println("Key:", k, "Value:", v) })
}

The sortedMapIntString() function can be re-used for any map[int]string (assuming the same sort order is desired), keeping each use to just two lines of code.

Downsides include:

• It's harder to read for people unaccustomed to using functions as first-class
• It might be slower (haven't tested it out)

Other languages have various solutions:

• If the use of <K> and <V> (to denote types for the key and value) looks a bit familiar, that code template is not terribly unlike C++ templates.
• Clojure and other languages support sorted maps as fundamental data types.
• While I don't know of any way Go makes range a first-class type such that it could be substituted with a custom ordered-range (in place of range in the original code), I think some other languages provide iterators that are powerful enough to accomplish the same thing.