Collect values in order, each containing a map

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
    keys := make([]int, len(m))
    i := 0
    for k := range m {
        keys[i] = k
        i++
    }
    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

All of the answers here now contain the old behavior of maps. In Go 1.12+, you can just print a map value and it will be sorted by key automatically. This has been added because it allows the testing of map values easily.

func main() {
    m := map[int]int{3: 5, 2: 4, 1: 3}
    fmt.Println(m)

    // In Go 1.12+
    // Output: map[1:3 2:4 3:5]

    // Before Go 1.12 (the order was undefined)
    // map[3:5 2:4 1:3]
}

Maps are now printed in key-sorted order to ease testing. The ordering rules are:

• When applicable, nil compares low
• ints, floats, and strings order by <
• NaN compares less than non-NaN floats
• bool compares false before true
• Complex compares real, then imaginary
• Pointers compare by machine address
• Channel values compare by machine address
• Structs compare each field in turn
• Arrays compare each element in turn
• Interface values compare first by reflect.Type describing the concrete type and then by concrete value as described in the previous rules.

When printing maps, non-reflexive key values like NaN were previously displayed as <nil>. As of this release, the correct values are printed.

Read more here.

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

In reply to James Craig Burley's answer. In order to make a clean and re-usable design, one might choose for a more object oriented approach. This way methods can be safely bound to the types of the specified map. To me this approach feels cleaner and organized.

Example:

package main

import (
    "fmt"
    "sort"
)

type myIntMap map[int]string

func (m myIntMap) sort() (index []int) {
    for k, _ := range m {
        index = append(index, k)
    }
    sort.Ints(index)
    return
}

func main() {
    m := myIntMap{
        1:  "one",
        11: "eleven",
        3:  "three",
    }
    for _, k := range m.sort() {
        fmt.Println(m[k])
    }
}

Extended playground example with multiple map types.

Important note

In all cases, the map and the sorted slice are decoupled from the moment the for loop over the map range is finished. Meaning that, if the map gets modified after the sorting logic, but before you use it, you can get into trouble. (Not thread / Go routine safe). If there is a change of parallel Map write access, you'll need to use a mutex around the writes and the sorted for loop.

mutex.Lock()
for _, k := range m.sort() {
    fmt.Println(m[k])
}
mutex.Unlock()

Answer 5

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 at each call site, 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-code template (which Go version 1 does not support as-is):

/* 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 its 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 (I haven't done performance comparisons)

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.

Answer 6

This provides you the code example on sorting map. Basically this is what they provide:

var keys []int
for k := range myMap {
    keys = append(keys, k)
}
sort.Ints(keys)

// Benchmark1-8      2863149           374 ns/op         152 B/op          5 allocs/op

and this is what I would suggest using instead:

keys := make([]int, 0, len(myMap))
for k := range myMap {
    keys = append(keys, k)
}
sort.Ints(keys)

// Benchmark2-8      5320446           230 ns/op          80 B/op          2 allocs/op

Full code can be found in this Go Playground.