slice iteration order in go

Question

Ok, i think this may be an old question, but i didn't find anything over the stackoverflow. In go , the iteration order over a map is not guranteed to be reproducible. So, the way suggest is to hold the keys in a slice and sort that slice. Then iterate over that slice to retrieve the values from the map, so that we get them in order(since slice composed of keys is sorted, so will be in reproducible order). So this goes to imply that the slice need be sorted else iteration over the slice will also not give reproducible order. But when i tried the below code in playground, i always found the order maintained in iteration, then in the map iteration case, why the slice of keys need to be sorted?

func main() {
    var mySlice = make([]string, 0)
    mySlice = append(mySlice, "abcd")
    mySlice = append(mySlice, "efgh")
    mySlice = append(mySlice, "ijkl")
    mySlice = append(mySlice, "mnop")
    mySlice = append(mySlice, "qrst")
    mySlice = append(mySlice, "uvwxyz")
    for _, val := range mySlice {
        fmt.Println(val)
    }
    fmt.Println(strings.Join(mySlice, "|"))

}

Output:

abcd
efgh
ijkl
mnop
qrst
uvwxyz
abcd|efgh|ijkl|mnop|qrst|uvwxyz

Solution 1

The only reason your slice is sorted is because you're appending items in already sorted order. If you appended items in an unsorted order like this

var mySlice = make([]string, 0)
mySlice = append(mySlice, "mnop")
mySlice = append(mySlice, "efgh")
mySlice = append(mySlice, "uvwxyz")
mySlice = append(mySlice, "ijkl")
mySlice = append(mySlice, "abcd")
mySlice = append(mySlice, "qrst")

(or populated a slice by pulling keys from a map, which would be unsorted), then the order on iteration would be unsorted (consistent, yes, but consistently unsorted). So, if your objective is to use the slice to pull items from a map in sorted order, then you need to first sort the slice, unless you can guarantee the slice items were inserted in an already sorted order.

Solution 2

A slice or array will always have a fixed order, i.e. how it is laid out in memory.

The documentation you were reading was probably just telling you to sort the slice so that the map output is in sorted order.

You are correct that the iteration order of a map is undefined and hence can be different each time it is performed. If you use a slice to iterate a map then it will always come back in a reliable order, i.e. the order of the keys in the slice.

I suggest you have a read over the information about slices.

EDIT

If it helps, consider the following code to illustrate that the sorting of a slice has nothing to do with its order being fixed:

words := map[int]string{
    0: "hello",
    1: "there",
    2: "goodbye",
}
keys:=[]int{2,0,1}
for _, k := range keys {
    // Will output in order: Goodbye, hello, there
    fmt.Println("Key:", k, "Value:", words[k])
}

Comments

[Volker]

You are mixing up slice and map.

[Onkar Banerjee]

Here is a link i want to share: nathanleclaire.com/blog/2014/04/27/… It mentions to sort the slice of keys, before iterating over it. If slice order is fixed, then why need to sort it all?

[Martin Campbell]

In the article, the slice is being constructed by iterating over the map, hence the slice will be populated in a random order. He has sorted the slice so that the keys are always ordered in the same numeric ascending order. The order of entries in the slice is fixed. If you remove the sort command and add umpteen copies of the loop, you will see that the same order of elements from the map will be returned. You just don't know what this order will be because the order in which the keys will have been appended to the slice will be random.